¿Todos los generadores de números pseudoaleatorios son en última instancia periódicos?

¿Todos los generadores de números pseudoaleatorios son en última instancia periódicos? ¿O son periódicas al final?

Por periódico quiero decir que, al igual que los números racionales, al final generan una subsecuencia periódica ...

Y seudoaleatorio significa generación algorítmica / matemática de números aleatorios ...

Todos los generadores pseudoaleatorios que no dependen de la aleatoriedad externa y usan una cantidad limitada de memoria son necesariamente periódicos, ya que tienen un estado finito. Puede pensar en ellos como enormes autómatas finitos deterministas que tienen estados especiales de "salida" en los que dan su salida. Todos los autómatas finitos son eventualmente periódicos, por lo que todos los generadores pseudoaleatorios producen eventualmente resultados periódicos.

Sin embargo, la duración del período puede ser enorme. Por ejemplo, un PRNG con un estado criptográfico de 128 bits solo puede circular una vez cada bits de salida, por lo que incluso si genera un bit cada nanosegundo, el sistema solar estará muerto antes de que se repita el PRNG.$2^{128}$

$\sqrt{2}$$\sqrt{2}$

Los PRNG son máquinas de estado. Si se basan solo en la entrada interna (en contraste con Poker Stars RNG, que es una combinación de hardware y software, sembrando continuamente de ... muestras de sonido) obtendrá (C, S1, ...) donde C es el valor actual (o anterior) y S1, ... podría ser un conjunto de estados:

Si hay N valores posibles (ya que la memoria está limitada) de C e itera N + 1 veces, alcanzará el mismo valor para C al menos dos veces. Si itera 2N + 1 veces, alcanzará el mismo valor para C al menos 3 veces.

Sea T = (Ct, S1t, S2t) un cierto estado (valor actual y otros estados).
Sea M = # {valores para S1} X {valores para S2} X {...} ser el cardinal de posibles combinaciones de estados (de nuevo: dado que la memoria está limitada).

Si itera NM + 1 veces el algoritmo, alcanzará al menos dos veces el mismo estado (Ct, S1t, S2t, ...), generando así el mismo valor de salida y la misma secuencia de estado siguiente que la primera vez, y convirtiéndose así en periódico.

Ejemplo simple de secuencia pseudoaleatoria que no es periódica: concatene las representaciones binarias de todos los enteros positivos, en orden:

110111001011101111000...

(Anteponga un "." Y se llama la constante binaria Champernowne ).

Por supuesto, esto no es de muy alta calidad en lo que respecta a las secuencias pseudoaleatorias, pero demuestra que es posible sin usar mucha memoria.

$\pi$$\sqrt{2}$

El requisito de memoria ilimitada no es un problema para una máquina de Turing, y probablemente tampoco sea un problema en la práctica, ya que el crecimiento es muy lento, pero depende de para qué pretendes usarlo.

$2^{128}$

$2^{128}$