Nombres pseudo-aléatoires et simulation

1.1. Nombres pseudo-aléatoires et simulation#

Pour mettre en oeuvre des algorithmes probabilistes il est nécessaire de travailler avec des réalisations de variables aléatoires. On verra qu’il est possible d’obtenir des réalisation de toute loi à partir de réalisations indépendantes de la loi uniforme sur \([0,1]\). Obtenir des réalisations indépendantes de la loi uniforme sur \([0,1]\) (produire du vrai hasard) est impossible sur les machines déterministes actuelles. Cependant on peut construire des algorithmes qui produisent des suites de nombres vérifiants de bonnes propriétés statistiques:

adéquation à la loi uniforme, par exemple par un test de Kolmogorov-Smirnov
indépendance entre les nombres générés (en fait test de non corrélation)
tests sur des problèmes classiques de probabilités: pour avoir une idée vous pouvez consulter les pages suivantes:

Un générateur de nombres pseudo-aléatoires est un algorithme déterminisite qui vérifie de bonnes propriétés théoriques et qui génère des nombres, appelés pseudo-aléatoires, qui possèdent de bonnes propriétés statistiques. Cet algorithme déterministe (généralement une récurrence) a un état propre qui doit être initialisé. L’état initial est appelée la graine du générateur (ou seed en anglais).

Tip

Pour bien utiliser un générateur de nombres pseudo-aléatoires il faut l’initialiser (fixer la graine) une seule fois en début de programme si c’est un programme sequentiel. Si votre programme est multithread (parallèle) il faut faire attention et choisir un générateur adequat.

Pour illustrer ce que peut être un générateur de nombres pseudo-aléatoires, voici un algorithme simple, largement utilisé il y a plus de 30 ans et qui est par exemple codé dans la fonction rand du langage C. Il s’agit d’un algorithme itératif d’équations linéaires dans \(\mathbf{Z}/{m \mathbf{Z}}\) (equations de congruence), plus précisement pour des entiers positifs \(a\), \(b\) et \(m\) bien choisis

(1.1)#\[\begin{split} \begin{cases} y_0 \in \{0, \dots, m-1\}, & \text{(graine)} \\ y_{n+1} = a y_n + b \mod m & \forall n \ge 0. \end{cases} \end{split}\]

Les nombres pseudo-aléatoires générés par cet algorithme sont obtenus en posant

(1.2)#\[ x_n = y_n / m \quad \text{i.e.} \quad x_n \in \{k / m, \, k=0,\dots,m-1\} \subset [0,1[. \]

Par exemple pour la fonction rand du langage C, les paramètres sont \(a = 1\,103\,515\,245\), \(b = 12345\) et \(m = 2^{31}\) et pour la fonction rand48 du système UNIX les paramètres sont \(a = 25\,214\,903\,917\), \(b = 11\) et \(m = 2^{48}\).

Plus généralement un générateur est la composition de deux fonctions \(g \circ f\):

fonction de transition: \(f: \mathcal{S} \to \mathcal{S}\) où \(\mathcal{S}\) est l’espace d’état du générateur. Par exemple \(\mathcal{S} = \mathbf{Z}/{m\mathbf{Z}}\) pour l’algorithme rand avec une fonction \(f\) linéaire (1.1).
fonction de sortie: \(g:\mathcal{S} \to \mathcal{O} \subset [0,1[\) où \(\mathcal{O}\) est l’espace de sortie. Pour l’algorithme rand cette transformation (1.2) est très simple.

De nombreux algorithmes existent pour améliorer la qualité ou la vitesse de ces générateurs. Citons les plus utilisés:

Mersenne Twister la fonction de transition est une transformation compliquée dans un espace matriciel, la fonction de sortie est aussi simple que (1.2).
Philox l’état est simplement le numéro de l’itération \(n\) (une fonction de transition très simple!) mais la fonction de sortie est complexe, similaire à des fonctions de chiffrement par bloc utilisées en cryptographie. Ce générateur “récent” est particulièrement intéressant et utilisé sur GPU.
PCG64: générateur par défaut dans numpy depuis la version 1.17. La fonction de transition est classique (une récurrence linéaire dans \(\mathbf{Z}/{m \mathbf{Z}}\)) et la fonction de sortie est une fonction de permutation bien choisie. Vous pouvez consulter https://www.pcg-random.org/index.html pour une description par l’auteur de l’algorithme.