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

24

¿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 ...

usuario13675
fuente
77
Este es un punto pedante, pero en una computadora con memoria finita, cada programa que no se detiene es en última instancia periódico. Podría analizar el algoritmo como si se ejecutara en una máquina Turing, pero cualquier PRNG cuyo uso de memoria no esté limitado con el tiempo no sería muy práctico.
Peter
@Peter dices "cualquier PRNG cuyo uso de memoria no esté limitado con el tiempo no sería muy práctico". Puede que no sea práctico cuando el uso de la memoria es cuadrático o lineal con respecto al tiempo, pero ¿y si es solo logarítmico? Mira mi respuesta.
Don Hatch

Respuestas:

39

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.2128

22

Yuval Filmus
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
El enlace al chat está roto. ¿Todavía es posible ver un registro de la discusión? : / @DW
oink
@ cchan3141, lo he restaurado; Probar ahora. Sin embargo, tenga en cuenta que los comentarios son transitorios por diseño, y lo mismo ocurre con las salas de chat. Si encuentra algo allí que tenga un valor duradero para los demás, le recomiendo que sugiera una edición de la respuesta para incorporar esa información, o publique una nueva respuesta propia. ¡Gracias!
DW
7

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.

Luis Masuelli
fuente
6

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.

π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.

2128

2128

Don Hatch
fuente