Section : Simulation, modèles et réalité
Précédent : Modèles
Suivant : Suites uniformes

## Générateurs pseudo-aléatoires

Tous les langages (ou presque) disposent d'un générateur pseudo-aléatoire. Les syntaxes varient : `ran`, `grand`, `rand`, `Random` ... Ce sont des fonctions, qui au dire des manuels d'utilisation, "retournent des nombres au hasard". Ce que l'on entend par "nombres au hasard" dépend d'abord du type des nombres (booléens, entiers, réels). Nous conviendrons de noter `Random` la fonction qui "retourne un réel au hasard dans ". Ceci recouvre en fait deux propriétés distinctes, que nous admettrons comme postulats.

Postulats.

1. Pour tout , , `Random` .
2. Les appels successifs de `Random` sont des expériences aléatoires indépendantes.

Interprétation.

Dans le langage courant "au hasard" ne signifie pas seulement aléatoire mais aussi uniformément réparti. Choisir au hasard, c'est donner les mêmes chances à tous les résultats possibles (équiprobabilité). On attend d'un réel "au hasard" dans qu'il tombe entre et avec probabilité , de même qu'entre et . Deux intervalles inclus dans ont la même probabilité d'être atteints s'ils ont même longueur, et cette probabilité est la longueur des intervalles. Les postulats ci-dessus ont une autre conséquence. Si on considère des couples successifs d'appels de Random comme des coordonnées de points du plan, ces points sont des "points au hasard" dans . Le sens précis étant que ces points sont indépendants et :

(`Random` , `Random` )

La probabilité qu'un point dont les deux coordonnées sont des appels de `Random` tombe dans un rectangle est la surface de ce rectangle. Ceci peut évidemment être étendu en dimension quelconque. Des triplets d'appels de `Random` successifs sont les coordonnées de "points au hasard" dans le cube en dimension 3, etc...

Proposition 2.1 Pour tout , soient appels successifs de `Random` . Les postulats 1) et 2) entraînent que pour tout rectangle

La probabilité pour `Random` de tomber sur n'importe quelle valeur particulière est nulle :

`Random`

car

`Random` `Random`

En conséquence,

Il y a un paradoxe à admettre à la fois que `Random` peut prendre une infinité de valeurs distinctes et que la probabilité de tomber sur une valeur particulière est nulle. Nous verrons en pratique la situation est légèrement différente, sans que cela remette en cause les postulats de définition de `Random`.

Une fois admis les deux postulats, toute analyse d'algorithmes contenant `Random` est une démonstration mathématique qui ne doit contenir aucun à-peu-près.

Exemple 1 : (Int désigne la partie entière).

Int

La variable aléatoire prend les valeurs 0, 1 ou 2.

|  | Int et Int |
|  | et |

On montre de même que et .

Remarque : Contrairement aux apparences, l'algorithme ci-dessus ne retourne pas de valeurs entre et . En théorie, la probabilité que `Random` retourne la valeur 1 est nulle. En pratique, les générateurs sont le plus souvent codés de manière à ne retourner ni 0 ni 1.

Exemple 2 : Lancer de dé.

Int `Random`

Pour tout ,

|  | Int( `Random` |
|  | `Random` |
|  | `Random` |

Il ne faut pas déduire de cet exemple que Int `Random` est la bonne manière de tirer un entier au hasard entre 0 et . Les générateurs courants permettent différents types de sorties : réelles uniformes sur l'intervalle , mais aussi booléennes, entières, et même complexes.

Les générateurs permettent de simuler des suites d'expériences aléatoires indépendantes, et donc de calculer de façon approchée des probabilités par application de la loi des grands nombres.

`
Répéter fois
expérience
Si réalisé alors
finSi
finRépéter
`

La variable est la fréquence expérimentale de l'évènement au cours des expériences.

Exemple :

`
Répéter fois
Random (* Lancer d'un dé *)
Si alors
finSi
finRépéter
`

En sortie de cet algorithme, contient un nombre d'autant plus proche de que est grand. Plus le nombre d'expériences est grand, plus précis est le résultat.

Section : Simulation, modèles et réalité
Précédent : Modèles
Suivant : Suites uniformes