Suponha que eu esteja usando um gerador de números pseudo-aleatórios lineares congruentes (PRNG). Dada uma semente $x_0$ , o fator multiplicador (a), o fator de deslocamento (c) e o fator de módulo (m), como posso determinar o período do meu PRNG? Eu o determino por algoritmos de detecção de experimentação / padrão ou existe uma fórmula direta para calcular seu período?

Embora minha pergunta seja especificamente sobre o método congruencial linear, estou aberto a saber mais sobre como os períodos são calculados na prática para outros PRNGs também.

Se você se restringir ao ciclo completo de LCG PRNG s, a resposta é fácil, por definição é simplesmente $m$ .

Para encontrar o período de um LCN PRNG de ciclo não completo para uma determinada semente, basta contar o número de iterações do PRNG até gerar o valor da semente mais uma vez.

Na página da wikipedia mencionada :

Duração do período

O período de um LCG geral é no máximo $m$ e, para algumas opções, muito menos que isso. Desde que $c$ seja diferente de zero, o LCG terá um período completo para todos os valores de sementes se e somente se :

• $c$ e$m$ sãorelativamente primos,
• $a - 1$ é divisível por todos osfatores primosde$m$
• $a - 1$ é um múltiplo de 4 se$m$ for um múltiplo de 4.

$c$$m$$a$ .

Historicamente, más escolhas levaram a implementações ineficazes de LCGs. Um exemplo particularmente ilustrativo disso é o RANDU, que foi amplamente utilizado no início da década de 1970 e leva a muitos resultados que estão sendo questionados no momento devido ao uso desse pobre LCG.

Por que você deseja usar um gerador de ciclo completo

Se você não se restringe ao ciclo completo de PRNGs de LCG, está correndo um risco enorme .

Se você não sabe que um determinado LCG é um ciclo completo, pode acabar com um gerador com um número arbitrário de seqüências mutuamente distintas, algumas das quais podem ser embaraçosamente pequenas e com uma aleatoriedade assustadora, possivelmente ainda pior do que o infame RANDU gerador .

Você realmente não precisa verificar todos os valores possíveis para garantir que ele gere uma sequência que seja longa o suficiente para o seu aplicativo.

Leitura adicional

Para um excelente iniciador em geradores de números pseudo-aleatórios, recomendo fortemente que você leia o capítulo Receitas Numéricas sobre Números Aleatórios.