Nombres pseudo-aléatoires

Une séquence pseudo-aléatoire (Pseudo Random Sequence en anglais) est une suite de nombres entiers x0, x1, x2, ... prenant ses valeurs dans l'ensemble M={0, 1, 2, ..., m-1}. Le terme xn (n>0) est le résultat d'un calcul (à définir) sur le ou les termes précédents. Le premier terme x0 est appelé le germe (seed en anglais). Algorithme général de récurrence Choisir x0 dans M Poser xn+1 = f(xn), pour n>0 où f est une application adéquate de M dans M. Une suite construite comme indiqué dans l'algorithme ci-dessus contient toujours un cycle de nombres se répétant à partir d'un certain endroit. Pour éviter de devoir employer plusieurs fois le même nombre au cours d'une simulation, on cherchera à rendre la longueur de ce cycle, appelée période, aussi grande que possible.

Les opérations à faire pour calculer les termes de la séquence, ainsi les différents paramètres de départ forment ce qu'on appelle un générateur de nombres pseudo-aléatoires.

Remarquons que si on ne change pas le germe, on obtiendra toujours la même séquence. Cela peut se révéler utile, en particulier en simulation. Si l'on veut avoir des séquences différentes, on peut, par exemple, prendre comme germe les décimales de l'heure exacte où le programme a été démarré ou encore sur l'intervalle de temps entre deux événements (ex. appuyer sur deux touches du clavier).

D. H. Lehmer donnait cette définition: «Une suite aléatoire est une vague notion couvrant l'idée d'une suite dans laquelle chaque terme est imprévisible pour un non-initié, et dont les éléments satisfont un certain nombre de tests statistiques traditionnels, dépendant éventuellement de l'usage auquel est destinée la suite.»

Qualités requises d'un générateur

Qu'attend-on réellement d'un générateur de nombres pseudo-aléatoires? La réponse à cette question conditionne la méthode à choisir, car dans ce domaine comme ailleurs, tout est affaire de compromis. En général on privilégie quatre critères:

• la vitesse: il faut que le calcul du nombre pseudo-aléatoire suivant soit rapide. Il n'est en effet pas rare de devoir générer des millions de nombres.
• la simplicité: une méthode très compliquée sera très difficile à programmer et surtout à tester. En général, on dit même en forme de boutade que plus l'algorithme est compliqué moins la séquence sera aléatoire.
• la méthode ne doit pas souffrir de faille grave: on en reparlera plus loin mais l'histoire des générateurs pseudo-aléatoires est pleine d'algorithmes qui se « coincent » lorsqu'ils arrivent sur un nombre particulier.
• les nombres produits ne doivent pas faire apparaître de suite logique, quelle que soit la façon de les regarder. Ce critère est le plus difficile à quantifier car il dépend fortement de l'application. Par exemple, imaginons qu'on veuille utiliser un générateur pour simuler un lancer de dés. On va vouloir absolument que tous les nombres de 1 à 6 aient exactement les mêmes chances d'apparaître. Mais si c'est pour jouer au 421, on va vouloir en plus que toutes les suites de deux et trois nombres consécutifs aient aussi exactement les mêmes chances d'arriver. Si la séquence 421 a moins de chances de se produire que 666, certains ne vont pas hésiter à prétendre que les dés sont pipés!

Référence

• Produire des nombres « au hasard », par Pierre Larbier, novembre 1994

Didier Müller, 2.1.03