Tous les générateurs de nombres pseudo-aléatoires sont-ils finalement périodiques?

24

Tous les générateurs de nombres pseudo-aléatoires sont-ils finalement périodiques? Ou sont-ils finalement périodiques?

Par périodique, je veux dire que, comme les nombres rationnels, ils génèrent finalement une sous-séquence périodique ...

Et pseudo-aléatoire signifie génération algorithmique / mathématique de nombres aléatoires ...

user13675
la source
7
C'est un point pédant à faire, mais sur un ordinateur à mémoire finie, chaque programme sans interruption est finalement périodique. Vous pouvez analyser l'algorithme comme fonctionnant sur une machine de Turing, mais tout PRNG dont l'utilisation de la mémoire est illimitée avec le temps ne serait pas très pratique.
Peter
@Peter vous dites "tout PRNG dont l'utilisation de la mémoire n'est pas limitée dans le temps ne serait pas très pratique". Cela peut ne pas être pratique lorsque l'utilisation de la mémoire est quadratique ou linéaire par rapport au temps, mais que se passe-t-il si c'est uniquement logarithmique? Voir ma réponse.
Don Hatch

Réponses:

39

Tous les générateurs pseudo-aléatoires qui ne s'appuient pas sur le hasard extérieur et utilisent une quantité limitée de mémoire sont nécessairement ultimes périodiques car ils ont un état fini. Vous pouvez les considérer comme d'énormes automates finis déterministes qui ont des états de "sortie" spéciaux dans lesquels ils donnent leur sortie. Tous les automates finis sont finalement périodiques, et donc tous les générateurs pseudo-aléatoires produisent éventuellement une sortie périodique.

Cependant, la durée de la période peut être énorme. Par exemple, un PRNG avec un état cryptographique de 128 bits peut ne tourner qu'une fois tous les bits de sortie, et donc même s'il émet un bit toutes les nanosecondes, le système solaire sera mort avant que le PRNG ne se répète.2128

Si le PRNG est autorisé à utiliser une quantité illimitée de mémoire (ce qui n'est pas réaliste), il peut, par exemple, produire l'expansion binaire de , qui, nous le savons, n'est pas finalement périodique (puisque est irrationnel).22

Yuval Filmus
la source
Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .
DW
Le lien vers le chat est rompu. Est-il toujours possible de voir un journal de la discussion? : / @DW
oink
@ cchan3141, je l'ai restauré; Essayez maintenant. Cependant, sachez que les commentaires sont transitoires par conception, et il en va de même pour les salles de chat. Si vous y trouvez quelque chose qui a une valeur durable pour les autres, je vous encourage à suggérer une modification de la réponse pour incorporer cette information, ou publier une nouvelle réponse de votre choix. Merci!
DW
7

Les PRNG sont des machines à états. S'ils sont basés uniquement sur des entrées internes (contrairement à Poker Stars RNG qui est une combinaison de matériel et de logiciels, se semant en continu à partir ... d'échantillons sonores), vous obtiendrez (C, S1, ...) où C est la valeur actuelle (ou précédente) et S1, ... pourrait être un ensemble d'états:

S'il existe des valeurs N possibles (puisque la mémoire est limitée) de C et que vous répétez N + 1 fois, vous atteindrez la même valeur pour C au moins deux fois. Si vous répétez 2N + 1 fois, vous atteindrez la même valeur pour C au moins 3 fois.

Soit T = (Ct, S1t, S2t) un certain état (valeur courante et autres états).
Soit M = # {valeurs pour S1} X {valeurs pour S2} X {...} le cardinal des combinaisons d'états possibles (là encore: puisque la mémoire est bornée).

Si vous itérez NM + 1 fois l'algorithme, vous atteindrez au moins deux fois le même état (Ct, S1t, S2t, ...), générant ainsi la même valeur de sortie et la même séquence d'état suivante que la première fois, et devenant ainsi périodique.

Luis Masuelli
la source
6

Exemple simple de séquence pseudo-aléatoire non périodique: concaténer ensemble les représentations binaires de tous les entiers positifs, dans l'ordre:

110111001011101111000...

(Ajoutez un "." Et cela s'appelle la constante binaire de Champernowne .)

Bien sûr, ce n'est pas de très haute qualité en ce qui concerne les séquences pseudo-aléatoires, mais cela démontre que c'est possible sans utiliser beaucoup de mémoire.

π2

L'exigence de mémoire illimitée n'est pas un problème pour une machine de turing, et ce n'est probablement pas un problème dans la pratique non plus, car la croissance est si lente, mais cela dépend de la raison pour laquelle vous avez l'intention d'utiliser cette chose.

2128

2128

Don Hatch
la source