Section : Simulation, modèles et réalité
Précédent : Générateurs pseudo-aléatoires
Suivant : Complexité et hasard

Suites uniformes

Au vu de la suite de réels retournée par un générateur particulier, comment décider que ce générateur convient ? Le seul moyen pratique d'estimer une probabilité est de l'exprimer comme une limite de fréquences expérimentales.

Définition 2.2   Une suite $(x_n),$ $n\in\mathbb{N}$, à valeurs dans $[0,1]$ est dite $k$-uniforme si pour tout rectangle

$$D= ]a_1,b_1]\times\cdots\times ]a_k,b_k], \; 0\leq a_i<b_i\leq 1 \,, \;i=1,\ldots ,k \,,$$

$$\lim_{n\rightarrow \infty}\frac{1}{n} \sum\limits^{n-1}_{i=0}$$   1$$_D((x_{ki}, x_{ki+1},\ldots , x_{k(i+1)-1})) =(b_1-a_1)\cdots (b_k-a_k) \;.$$

La notation 1$_D$ désigne la fonction indicatrice de l'ensemble $D$.

   1$$_D(y) = \left\{ \begin{array}{cl} 1 &si\; y\in D,\\ 0 &sinon. \end{array}\right.$$

Le vecteur $(x_{ki}, x_{ki+1},\ldots , x_{k(i+1)-1})$ est le $i$-ème $k$-uplet d'éléments consécutifs de la suite. La somme $\sum\limits^{n-1}_{i=0}$1$_D((x_{ki}, x_{ki+1},\ldots , x_{k(i+1)-1}))$ est le nombre de $k$-uplets d'éléments consécutifs de la suite qui appartiennent à $D$, parmi les $n$ premiers.

La définition ci-dessus dit donc que parmi les $k$-uplets d'éléments consécutifs de la suite, la proportion de ceux qui tombent dans un rectangle donné doit tendre vers le volume de ce rectangle (en dimension $k$). Cette définition est passablement utopique. En particulier elle entraîne que la probabilité que Random tombe sur un point donné est nulle. Comme qu'il n'y a qu'une quantité dénombrable de rationnels dans $[0,1]$, la probabilité de tomber sur un rationnel est également nulle. Or l'ordinateur ne connaît que les décimaux, et même seulement un nombre fini d'entre eux, donc la fonction Random ne peut retourner que des rationnels. Qu'à cela ne tienne, si on sait construire une suite uniforme de chiffres entre 0 et $9$, on pourra en déduire des réels au hasard dans $[0,1]$, approchés à la $k$-ème décimale, en considérant des $k$-uplets consécutifs de chiffres de la suite initiale. C'est le principe des "tables de nombres au hasard" que l'on trouve encore dans certains livres. La même remarque vaut bien sûr en base 2. Il suffirait donc de savoir définir ce qu'est une suite de bits au hasard. Voici la définition de $k$-uniformité pour les suites de booléens.

Définition 2.3   Une suite $x=(x_n)$ de booléens dans $\{0,1\}$, est dite $k$-uniforme si pour tout $(\varepsilon _1,\ldots ,\varepsilon_k)\in \{0,1\}^k$ :

$$\lim\limits_{n\rightarrow\infty}\frac{1}{n}\sum\limits^{n-1}_{i=0}$$   1$$_{\{(\varepsilon_1,\ldots ,\varepsilon_k)\}} ((x_{ki},x_{ki+1},\ldots ,x_{k(i+1)-1}))=\frac{1}{2^k} \;.$$

Ce que l'on attend en fait de la suite des appels de Random , c'est qu'elle soit $k$-uniforme, pour tout entier $k$ (on dit $\infty$-uniforme). C'est évidemment illusoire, car l'infini n'existe pas pour un ordinateur. Tout ce que l'on peut faire, c'est vérifier que rien d'invraisemblable ne se produit pour la suite finie observée. C'est précisément l'objet des tests statistiques que de distinguer le plausible de ce qui est trop peu vraisemblable, et des quantités de tests ont été imaginés pour mettre les générateurs à l'épreuve.

"Définition" Un $N-$uplet de nombres dans $[0,1]$ sera dit pseudo-aléatoire s'il passe avec succès une série de tests statistiques, chacun étant destiné à vérifier une conséquence de la $k$-uniformité. Le nombre de ces tests ainsi que l'entier $k$ sont fonction croissante de l'exigence de l'utilisateur.

Parmi les différentes formalisations du hasard qui ont pu être proposées, la notion de suite $\infty$-uniforme est la seule utilisable en pratique : elle est la seule que l'on puisse tester pour un générateur donné et elle suffit à justifier toutes les applications des générateurs pseudo-aléatoires. Les générateurs livrés avec les compilateurs courants sont issus d'une longue expérimentation statistique, et n'ont survécu au temps que parce qu'ils ont donné satisfaction à de nombreux utilisateurs, ce qui n'empêche pas de rester vigilant.

Comment sont-ils programmés ? Même les suites récurrentes les plus simples peuvent être chaotiques et donc constituer des exemples de suites apparemment aléatoires. Et ce, même si le sens intuitif de "aléatoire" (impossible à prévoir) est contradictoire avec la définition d'une suite récurrente (chaque terme fonction connue du précédent). Pour un ordinateur, il n'existe qu'un nombre fini de valeurs. Les valeurs de Random sont toujours calculées à partir d'entiers répartis dans $\{0,1,\ldots ,M\!-\!1\}$ où $M$ est un grand nombre (de l'ordre $10^8$ au moins pour les générateurs usuels). Pour retourner un réel dans $[0,1]$, il suffit de diviser par $M$. En pratique, un nombre fini de valeurs peuvent seules être atteintes, et elles le sont avec une probabilité positive. Ceci contredit les postulats de définition de Random mais ne constitue pas un inconvénient majeur dans la mesure où $M$ est très grand. Pour obtenir un autre type de réalisations, comme par exemple des entiers uniformes sur $\{0,\ldots,k\}$ ou des booléens (pile ou face), passer par les appels de Random est inutile, il vaut mieux partir du générateur sur $\{0,\ldots,M\!-\!1\}$ sans diviser au préalable par $M$. Ceci est pris en compte par la plupart des langages courants.

La valeur retournée par un générateur est une fonction de la valeur précédente ou des valeurs obtenues précédemment. Dans le premier cas la suite calculée est une suite récurrente. Une "graine" $u_0$ étant choisie dans $\{0,\ldots,M\!-\!1\}$, les valeurs successives de la suite sont définies par $u_{n+1}=g(u_n)$, où $g$ est une fonction de $\{0,\ldots,M\!-\!1\}$ dans lui-même, suffisamment simple pour être calculée rapidement.

On se heurte alors à un problème important : toute suite récurrente sur un ensemble fini est périodique. La suite de valeurs retournée par Random bouclera forcément. Peut-on considérer comme aléatoire une suite périodique ? Oui peut-être, si la période est suffisamment élevée par rapport au nombre de termes que l'on utilise. La prudence s'impose en tout cas et il faut se méfier de l'idée intuitive que plus le passage de $u_n$ à $u_{n+1}$ sera compliqué, plus leurs valeurs seront indépendantes et meilleur sera le générateur.

Les générateurs les plus simples sont les générateurs par congruence. Ils sont de la forme suivante :

$$g(u)\;=\;(A u+C)\;$$modulo $$M \;.$$

Divers résultats mathématiques permettent de justifier les "bons" choix de $A$, $C$ et $M$. Ils sont tombés en désuétude du fait de l'apparition de nouveaux générateurs plus performants. Le générateur suivant était très répandu et donnait en général satisfaction. Il peut encore servir comme dépannage.

$$g(u)\;=\;16807 \,u\;$$ modulo $$\,2147483647\;.$$

Tout générateur nécessite une initialisation. Pour une même valeur de la graine $u_0$, c'est la même suite de valeurs qui sera calculée à chaque fois. Pour obtenir des résultats différents d'une exécution à l'autre, il est nécessaire de changer la graine au début de chaque exécution. Selon les langages, cette initialisation peut être laissée au choix de l'utilisateur, ou être réalisée à partir du compteur de temps (fonction randomize en Turbo Pascal, seed en C...). L'instruction de randomisation doit figurer une seule fois, en début de programme principal.

Section : Simulation, modèles et réalité
Précédent : Générateurs pseudo-aléatoires
Suivant : Complexité et hasard