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

24

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

user13675
fonte
7
Esse é um ponto pedante, mas em um computador com memória finita, todo programa sem interrupção é, em última análise, periódico. Você pode analisar o algoritmo como rodando em uma máquina de Turing, mas qualquer PRNG cujo uso de memória seja ilimitado com o tempo não seria muito prático.
Peter
@ Peter diz que "qualquer PRNG cujo uso de memória seja ilimitado com o tempo não seria muito prático". Pode não ser prático quando o uso da memória é quadrático ou linear em relação ao tempo, mas e se for apenas logarítmico? Veja minha resposta.
Don Hatch

Respostas:

39

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

22

Yuval Filmus
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
DW
O link para o bate-papo está quebrado. Ainda é possível ver um log da discussão? : / @DW
oink
@ cchan3141, eu restaurei; tente agora. No entanto, lembre-se de que os comentários têm caráter transitório e o mesmo vale para as salas de bate-papo. Se você encontrar algo que tenha um valor duradouro para outras pessoas, sugiro que você edite a resposta para incorporar essas informações ou publique uma nova resposta. Obrigado!
DW
7

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.

Luis Masuelli
fonte
6

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.

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

2128

2128

Don Hatch
fonte