Todos os geradores de números pseudo-aleatórios são periódicos?

Todos os geradores de números pseudo-aleatórios são periódicos? Ou eles são periódicos no final das contas?

Por periódico, quero dizer que, como números racionais, eles acabam gerando uma subsequência periódica ...

E pseudo-aleatório significa geração algorítmica / matemática de números aleatórios ...

Todos os geradores pseudo-aleatórios que não confiam na aleatoriedade externa e usam uma quantidade limitada de memória são necessariamente periódicos, uma vez que possuem um estado finito. Você pode pensar neles como enormes autômatos finitos determinísticos que possuem estados especiais de "saída" nos quais eles fornecem sua saída. Todos os autômatos finitos são eventualmente periódicos e, portanto, todos os geradores pseudo-aleatórios produzem saída eventualmente periódica.

No entanto, a duração do período pode ser enorme. Por exemplo, um PRNG com um estado criptográfico de 128 bits só pode dar um ciclo uma vez a cada bits de saída e, mesmo que a saída de um bit a cada nanossegundo, o sistema solar esteja morto antes que o PRNG se repita.$2^{128}$

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

PRNGs são máquinas de estado. Se eles são baseados apenas na entrada interna (em contraste com o Poker Stars RNG, que é uma combinação de hardware e software, semeando-se continuamente a partir de ... amostras de som), você verá (C, S1, ...) onde C é o valor atual (ou anterior) e S1, ... pode ser um conjunto de estados:

Se houver N valores possíveis (desde que a memória esteja limitada) de C e você iterar N + 1 vezes, atingirá o mesmo valor para C pelo menos duas vezes. Se você repetir 2N + 1 vezes, atingirá o mesmo valor para C pelo menos 3 vezes.

Seja T = (Ct, S1t, S2t) um certo estado (valor atual e outros estados).
Seja M = # {valores para S1} X {valores para S2} X {...} seja o cardeal das combinações de estados possíveis (novamente: uma vez que a memória é limitada).

Se você iterar NM + 1 vezes o algoritmo, atingirá pelo menos duas vezes o mesmo estado (Ct, S1t, S2t, ...), gerando o mesmo valor de saída e a mesma sequência de estado seguinte da primeira vez, e tornando-se periódico.

Exemplo simples de sequência pseudo-aleatória que não é periódica: concatene as representações binárias de todos os números inteiros positivos, em ordem:

110111001011101111000...

(Coloque um "." E é chamado de constante binária de Champernowne .)

É claro que isso não é de alta qualidade no que diz respeito a sequências pseudo-aleatórias, mas demonstra que é possível sem usar muita memória.

$\pi$$\sqrt{2}$

O requisito de memória ilimitada não é um problema para uma máquina de turing, e provavelmente também não é um problema na prática, já que o crescimento é muito lento, mas depende do que você pretende usar.

$2^{128}$

$2^{128}$