¿Cómo puedo determinar el período de mi generador de números pseudoaleatorios?

14

Supongamos que estoy usando un generador de números pseudoaleatorio congruencia lineal (PRNG). Dada una semilla , el factor de multiplicación (a), el factor de desplazamiento (c) y el factor de módulo (m), ¿cómo puedo determinar el período de mi PRNG? ¿Lo determino mediante algoritmos de experimentación / detección de patrones, o existe una fórmula directa para calcular su período? x0

Aunque mi pregunta es específicamente sobre el método congruencial lineal, estoy abierto a saber más sobre cómo se calculan los períodos en la práctica para otros PRNG también.

random-number-generation Paul
fuente
Relevante: en.wikipedia.org/wiki/…
Por cierto, si está utilizando LFSR, entonces el período es máximo si el polinomio de retroalimentación es primitivo . En tal caso, el período AFAIK (no me cite; demasiado vago para desenterrar mis notas del curso) es donde el polinomio de retroalimentación p ( x ) ∈ F q [ x ] de grado n , y q es el tamaño de El campo de coeficientes. qnortepag(X)∈Fq[X]norteq
2
Los algoritmos de detección de ciclos de Floyd, así como los algoritmos de detección de ciclos de Brent, son formas eficientes de detectar ciclos. Ambos devolverán algunos L múltiples del período, y una vez que tenga eso, puede factorizar L y ver cuál es el factor más pequeño que es un período.
xdavidliu

Respuestas:

12

Si se limita al ciclo completo de LCG PRNG s, entonces la respuesta es fácil, por definición es simplemente metro .

Para encontrar el período de un LCG PRNG de ciclo no completo para una semilla dada, solo necesita contar el número de iteraciones de la PRNG hasta que genere el valor de semilla una vez más.

Desde la página de Wikipedia a la que se hace referencia :

Duración del período

El período de un LCG general es a lo sumo metro , y para algunas elecciones de mucho menos que eso. Siempre que C no sea cero, el LCG tendrá un período completo para todos los valores de semilla si y solo si :

Cmetroun

Históricamente, las malas elecciones habían llevado a implementaciones ineficaces de LCG. Un ejemplo particularmente ilustrativo de esto es RANDU, que se usó ampliamente a principios de la década de 1970 y conduce a muchos resultados que actualmente se cuestionan debido al uso de este pobre LCG.

¿Por qué quieres usar un generador de ciclo completo?

Si no se limita a los PRNG de LCG de ciclo completo, entonces está asumiendo un gran riesgo .

Si no sabe que un LCG dado es un ciclo completo, entonces podría terminar con un generador con un número arbitrario de secuencias mutuamente distintas, algunas de las cuales podrían ser vergonzosamente pequeñas y tener una aleatoriedad espantosa, posiblemente incluso peor que el infame generador RANDU .

Realmente no desea tener que verificar cada valor inicial posible para asegurarse de que genera una secuencia que sea lo suficientemente larga para su aplicación.

Otras lecturas

Para una excelente introducción a los generadores de números pseudoaleatorios, le recomiendo encarecidamente que lea el capítulo Recetas numéricas sobre números aleatorios.

Mark Booth
fuente
Eso es cierto, pero no me estoy limitando a LCG PRNG de período completo ... Tengo curiosidad por las malas elecciones de a, c y m, de modo que las secuencias aleatorias que no alcanzan el período completo. Me gustaría poder saber con anticipación, dados algunos a, c y m, cuál será el período inevitablemente. Sé que está limitado por m, pero me preguntaba si podemos hacerlo mejor que eso y obtener el período exacto.
Paul
No creo que esto esté dividiendo pelos por un tecnicismo en absoluto: la pregunta era "cómo determinar el período de un LCG con parámetros arbitrarios", mientras que esta respuesta dice "no use LCG arbitrarios, siempre use LCG de período completo, y suponiendo que lo haga , la respuesta a su pregunta sería el período máximo posible, por definición ". El argumento para usar LCF de período completo presentado en esta respuesta es perfectamente convincente, pero el problema es que no es en absoluto lo que se hizo la pregunta.
xdavidliu
Lo siento @xdavidliu pero no veo cómo tu nuevo comentario me ayuda a mejorar mi respuesta. Me llamó la atención que en realidad no respondí la pregunta, edité mi respuesta para solucionarlo, y luego se lo hice saber de una manera que pensé que podría hacerlo sonreír (si es un fanático de Futurama). No veo que sea necesario decir nada más.
Mark Booth
Tenga en cuenta que en el intercambio de la pila, los comentarios no están destinados a discusiones extendidas, para eso use Computational Science Chat . Los comentarios son para ayudar a mejorar las preguntas y respuestas, y son una distracción, por lo que tratamos de mantenerlos al mínimo. Los comentarios deben considerarse efímeros, cualquier comentario que ya no ayude activamente a mejorar una pregunta o respuesta puede eliminarse en cualquier momento para ordenar una publicación.
Mark Booth