Qu'est-ce qu'une graine dans un générateur de nombres aléatoires?

J'ai essayé une recherche google habituelle, etc., mais la plupart des réponses que je trouve sont quelque peu ambiguës ou spécifiques à une langue / bibliothèque, telles que Python ou C ++, stdlib.hetc.

Par exemple, beaucoup disent que la graine est un point de départ du générateur de nombres aléatoires et la même graine produit toujours le même nombre aléatoire. Qu'est-ce que ça veut dire? Cela signifie-t-il que le nombre de sorties est une fonction déterministe d'une graine spécifique, et le caractère aléatoire vient de la valeur de la graine? Mais si c'est le cas, alors en fournissant la graine, n'est-ce pas nous, les programmeurs, qui créons l'aléatoire au lieu de laisser la machine le faire?

Aussi, que signifie un point de départ dans ce contexte? Est-ce une manière non rigoureuse de dire un élément $x\in\mathfrak{X}$ du domaine d'une carte $f:\mathfrak{X}\rightarrow\mathfrak{Y}$ ? Ou est-ce que je me trompe?

La plupart des générateurs de nombres pseudo-aléatoires (PRNG) sont construits sur des algorithmes impliquant une sorte de méthode récursive à partir d'une valeur de base qui est déterminée par une entrée appelée "graine". Le PRNG par défaut dans la plupart des logiciels statistiques (R, Python, Stata, etc.) est l' algorithme Mersenne Twister MT19937, qui est présenté dans Matsumoto et Nishimura (1998) . Il s'agit d'un algorithme compliqué, il serait donc préférable de lire l'article sur celui-ci si vous voulez savoir comment cela fonctionne en détail. Dans cet algorithme particulier, il existe une relation de récurrence de degré , et ta semence d'entrée est un ensemble initial de vecteurs x 0 , x 1 , . . . $n$ . L'algorithme utilise une relation de récurrence linéaire qui génère:$\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}$

où et r et A sont des objets qui peuvent être spécifiés comme paramètres dans l'algorithme. Puisque la graine donne l'ensemble initial de vecteurs (et étant donné d'autres paramètres fixes pour l'algorithme), la série de nombres pseudo-aléatoires générés par l'algorithme est fixe. Si vous changez la graine, vous changez les vecteurs initiaux, ce qui change les nombres pseudo-aléatoires générés par l'algorithme. C'est, bien sûr, la fonction de la graine.$1 \leqslant m \leqslant n$$r$$\mathbf{A}$

Maintenant, il est important de noter que ce n'est qu'un exemple, en utilisant l'algorithme MT19937. Il existe de nombreux PRNG qui peuvent être utilisés dans les logiciels statistiques, et ils impliquent chacun des méthodes récursives différentes, et donc la graine signifie une chose différente (en termes techniques) dans chacun d'eux. Vous pouvez trouver une bibliothèque de PRNG Rdans cette documentation , qui répertorie les algorithmes disponibles et les articles qui décrivent ces algorithmes.

Le but de la graine est de permettre à l'utilisateur de "verrouiller" le générateur de nombres pseudo-aléatoires, pour permettre une analyse reproductible. Certains analystes aiment définir la valeur de départ à l'aide d'un véritable générateur de nombres aléatoires (TRNG) qui utilise des entrées matérielles pour générer un numéro de départ initial, puis le signaler comme un numéro verrouillé. Si la graine est définie et rapportée par l'utilisateur d'origine, un auditeur peut répéter l'analyse et obtenir la même séquence de nombres pseudo-aléatoires que l'utilisateur d'origine. Si la graine n'est pas définie, l'algorithme utilisera généralement une sorte de graine par défaut (par exemple, à partir de l'horloge système), et il ne sera généralement pas possible de répliquer la randomisation.

Premièrement, il n'y a pas de véritable hasard dans les "nombres aléatoires" générés par ordinateur. Tous les générateurs pseudo- aléatoires utilisent des méthodes déterministes. (Peut-être que les ordinateurs quantiques changeront cela.)

La tâche difficile consiste à créer des algorithmes qui produisent une sortie qui ne peut pas être distinguée de manière significative des données provenant d'une source vraiment aléatoire.

Vous avez raison de dire que définir une graine vous démarre à un point de départ connu particulier dans une longue liste de nombres pseudo-aléatoires. Pour les générateurs implémentés dans R, Python, etc., la liste est extrêmement longue. Assez longtemps pour que même le plus grand projet de simulation possible ne dépasse pas la «période» du générateur pour que les valeurs commencent à se recycler.

Dans de nombreuses applications ordinaires, les gens ne fixent pas de graine. Ensuite, une graine imprévisible est sélectionnée automatiquement (par exemple, à partir des microsecondes sur l'horloge du système d'exploitation). Les générateurs pseudo-aléatoires d'usage général ont été soumis à des batteries de tests, constitués en grande partie de problèmes qui se sont révélés difficiles à simuler avec des générateurs insatisfaisants antérieurs.

Habituellement, la sortie d'un générateur se compose de valeurs qui ne sont pas, à des fins pratiques, distinguables de nombres choisis vraiment au hasard sous la forme d'une distribution uniforme sur Ensuite, ces nombres pseudo-aléatoires sont manipulés afin de correspondre à ce que l'on obtiendrait en échantillonnant au hasard à partir d'autres distributions telles que binomiale, Poisson, normale, exponentielle, etc.$(0,1).$

Un test d'un générateur consiste à voir si ses paires successives dans les «observations» simulées comme semblent réellement remplir le carré de l'unité au hasard. (Fait deux fois ci-dessous.) L'aspect légèrement marbré est le résultat d'une variabilité inhérente. Il serait très suspect d'obtenir une intrigue qui semblait parfaitement uniformément grise. [Dans certaines résolutions, il peut y avoir un motif moiré régulier; veuillez modifier le grossissement vers le haut ou vers le bas pour vous débarrasser de cet effet bidon s'il se produit.]$\mathsf{Unif}(0,1)$

set.seed(1776);  m = 50000
par(mfrow=c(1,2))
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
par(mfrow=c(1,1))

Il est parfois utile de définir une graine. Certaines de ces utilisations sont les suivantes:

1. Lors de la programmation et du débogage, il est pratique d'avoir une sortie prévisible. De nombreux programmeurs mettent une set.seedinstruction au début d'un programme jusqu'à ce que l'écriture et le débogage soient terminés.

2. Lors de l'enseignement de la simulation. Si je veux montrer aux élèves que je peux simuler des jets d'un dé juste en utilisant la samplefonction dans R, je pourrais tricher, exécuter de nombreuses simulations et choisir celle qui se rapproche le plus d'une valeur théorique cible. Mais cela donnerait une impression irréaliste du fonctionnement réel de la simulation.

   Si je mets une graine au départ, la simulation obtiendra le même résultat à chaque fois. Les étudiants peuvent relire leur copie de mon programme pour s'assurer qu'elle donne les résultats escomptés. Ensuite, ils peuvent exécuter leurs propres simulations, soit avec leurs propres graines, soit en laissant le programme choisir son propre point de départ.

   Par exemple, la probabilité d'obtenir la 10 totale lors du laminage de deux dés est juste

   $$3/36 = 1/12 = 0.08333333.$$ $$2\sqrt{(1/12)(11/12)/10^6} = 0.00055.$$

   set.seed(703);  m = 10^6
   s = replicate( m, sum(sample(1:6, 2, rep=T)) )
   mean(s == 10)
   [1] 0.083456         # aprx 1/12 = 0.0833
   2*sd(s == 10)/sqrt(m)
   [1] 0.0005531408     # aprx 95% marg of sim err.
   

3. Lors du partage d'analyses statistiques impliquant une simulation. De nos jours, de nombreuses analyses statistiques impliquent une certaine simulation, par exemple un test de permutation ou un échantillonneur de Gibbs. En affichant la graine, vous permettez aux personnes qui lisent l'analyse de reproduire exactement les résultats, si elles le souhaitent.

4. Lors de la rédaction d'articles académiques impliquant la randomisation. Les articles académiques passent généralement par plusieurs cycles d'examen par les pairs. Un tracé peut utiliser, par exemple, des points à gigue aléatoire pour réduire le surplacement. Si les analyses doivent être légèrement modifiées en réponse aux commentaires des examinateurs, il est bon qu'un tremblement particulier non lié ne change pas entre les rondes de révision, ce qui peut être déconcertant pour les examinateurs particulièrement exigeants, alors vous définissez une graine avant de trembler.

TL; DR;

Une graine vous permet généralement de reproduire la séquence de nombres aléatoires. En ce sens, il ne s'agit pas de vrais nombres aléatoires mais de "nombres pseudo aléatoires", d'où un générateur PNR (PNRG). Ce sont une vraie aide dans la vraie vie!

Un peu plus de détails:

Pratiquement tous les générateurs de nombres "aléatoires" implémentés dans les langages informatiques sont des générateurs de nombres pseudo aléatoires. En effet, étant donné une valeur de départ (===> la graine), ils fourniront toujours la même séquence de résultats pseudo aléatoires. Un bon générateur produira une séquence qui ne peut être distinguée - en termes statistiques - d'une véritable séquence aléatoire (lancer un vrai dé, une vraie pièce, etc.).

Dans de nombreux cas de simulation, vous voulez vivre une véritable expérience "aléatoire". Cependant, vous souhaitez également pouvoir reproduire vos résultats. Pourquoi? Eh bien, au moins les régulateurs s'intéressent à cette chose particulière.

Il y a beaucoup à plonger. Les gens analysent même la «meilleure» graine aléatoire. À mon avis, cela invalide leur modèle car ils ne peuvent pas gérer un "vrai" comportement aléatoire - ou leur PRNG n'est pas adapté à leur mise en œuvre. La plupart du temps, ils ne font tout simplement pas assez de simulations, mais ils prennent du temps.

Imaginez maintenant un «vrai» RNG. On pourrait implémenter cela sur la base d'une sorte d'aléatoire dans la machine. Si vous ne prenez qu'une graine aléatoire (par exemple, le temps maintenant), vous créez une sorte de point de départ aléatoire, mais le caractère aléatoire de la séquence dépend toujours de l'algorithme pour déterminer les nombres suivants. Ceci est plus important que le point de départ dans la plupart des cas car la distribution des résultats détermine le "résultat" réel. Si votre séquence devait être vraiment aléatoire, comment mettriez-vous cela en œuvre? Les tics d'horloge d'un ordinateur peuvent être considérés comme déterministes et sinon, ils afficheront probablement beaucoup d'autocorrélation. Alors que peux-tu faire? Le meilleur pari jusqu'à présent est de mettre en œuvre un PNRG solide.

L'informatique quantique? Je ne suis pas sûr que ce sera réglé.