Comme nous l'avons vu dans le préambule à ce cours, le hasard est une notion relativement difficile à définir.
La nécessité de produire de longues séries de nombres simulant le hasard, c'est à dire aussi imprévisibles que possible, tout en ayant d'autres qualités, comme une répartition aussi uniforme que possible est une préoccupation permanente des informaticiens et cela depuis le début de cette science.
En général, ces séries sont utilisées pour des programmes de simulation consistant bien souvent à vérifier des lois statistiques ou à déterminer expérimentalement des probabilités dont le calcul est difficile. Il y a donc un impératif de coût, les nombres 'aléatoires' que nous appelerons plus justement 'pseudo-aléatoires' doivent être produits par des procédés simples n'impliquant pas des temps de calculs trop longs.
L'utilisation d'algorithmes précis permet en outre la reproductibilité, ce qui peut être intéressant quand on veut comparer deux lois différentes avec la même série aléatoire. Il existe donc des méthodes orientées vers des algorithmes déterministes et d'autres mélangeant les techniques en faisant appel à des données physiques imprévisibles comme le contenu de certains registres volatiles de l'ordinateur.
Voici pour commencer les portraits de quelques mathématiciens ayant largement contribué à la solution de ce problème.

Galerie des portraits

John Von Neumann (1903-1957/H-USA) Derrick Henry Lehmer (1905-1991/USA) Donald Ervin Knuth (1938-.../USA)

Citations

"Quiconque considère des méthodes arithmétiques pour produire des nombres aléatoires est, bien sûr, en train de commettre un péché. " (John Von Neumann).
"Les générateurs de nombres aléatoires ne doivent pas être choisis au hasard." (D. Knuth)

Générateurs congruentiels linéaires

Il s'agit de l'algorithme le plus utilisé pour produire des nombres aléatoires depuis qu'il a été inventé en 1948 par D.H Lehmer.
Ce sont les suites récurrentes :
xn+1 = ( a * xn + b) mod c
Elles dépendent des constantes a,b et c ainsi que du terme initial x0 ('seed').
Dans tous les cas les nombres générés (sauf éventuellement le premier) sont compris entre 0 et c-1.

Premiers essais (peu concluants)

Pour les valeurs (25,16,256,12) tous les nombres générés sont pairs...
Pour les valeurs (25,16,256,11) tous les nombres générés sont impairs...
Pour les valeurs (25,16,256,10) c'est encore pire, la suite est stationnaire...

Suivons maintenant les conseils de Knuth

Pour ne pas retrouver les défauts graves rencontrés ci-dessus, il faut regarder cette suite d'un peu plus près. Si on choisit b non nul , il est toujours possible d'obtenir une période de longueur c (donc pas de risque de bloquage puisqu'on va retrouver tous les nombres entre 0 et c-1 dans la suite).
D. Knuth établit une liste de critères que doivent remplir a,b et c pour cela :
  1. b et c doivent être premiers entre eux
  2. a-1 doit être un multiple de p, pour tout p nombre premier diviseur de c
  3. a-1 doit être un multiple de 4 si c est un multiple de 4
  4. si c est une puissance de 2, le bit de poids faible des nombres produits vaut alternativement 0 et 1
Bon, pour notre second essai, soyons plus prudents et respectons scrupuleusement les critères précédents :
a=31415821 b=1 c=100000000 x0=0

Regardons maintenant les chiffres des unités de la suite générée. C'est Robert Sedgewick qui donne cet exemple.

Encore quelques exemples célèbres et biaisés

Le premier 'RANDU' était le générateur proposé par IBM pour sa série 370, le second était intégré à Turbo-Pascal, le troisième était le générateur d'UNIX.

Alors que faire ?

Il existe de 'bons' générateurs utilisant la technique GCL, citons par exemple, parmi d'autres, le 'standard minimal' de Park et Miller'.

Générateurs à congruence additive

C'est une généralisation des suites de Fibonnaci, chaque terme étant obtenu par une addition de deux termes pris parmi les k précédents. On dit aussi suites de Fibonnaci 'lacunaires'.
La méthode nécessite le stockage permanent de k nombres.
Naturellement on combine avec une congruence, donc :
xn=xn-1+xn-k (mod c)
La méthode est rapide surtout quand c est une puissance de 2.
Mitchell et Moore, après une étude théorique poussée, ont proposé le générateur suivant :
xn+1 = ( xn-24 + xn-55 ) mod m
Cette suite passe avec succès de nombreux critères de qualité.

Le nombre π

Une équipe de physiciens conduits par Ephraïm Fischbach du Collède des Sciences de l'université Purdue de West Lafayette (Indiana), a réalisé une étude comparative comparant l'aspect aléatoire des décimales du nombre π avec les séries produites par 30 générateurs populaires classiques.
Leur conclusion est que π est un bon générateur, source acceptable de hasard, mais pas toujours le meilleur.

Une liste (non exhaustive) des algorithmes modernes

Simulation de 'tirs' aléatoires

Nous avons vu que les méthodes dites de 'Monte-Carlo' utilisent des 'cribles' à base de générateurs de points de l'espace [0,1]n ayant pour coordonnées des variables dont les types représentent (ou essaient de représenter) les nombres réels ('float', 'double').
Or dès qu'on a une suite aléatoire d'entiers (un) répartie uniformément dans l'intervalle [0,c] la suite xn=un/c nous donne une solution. Plus c est grand et plus la précision sera grande. Comme on sait produire de telles suites pour c arbitrairement grand, on peut atteindre toute précision en décimales donnée à l'avance.
La plupart des langages fournissent de tels générateurs (random.random() en python, Math.random() en Java, etc...
On peut revoir, par exemple sur cette page, des programmes de démonstration pour les langages Python et C.
On peut se faire une idée très rapidement de la qualité de ces générateurs en visualisant le tir aléatoire par un nuage de points sur une surface ou dans un volume donné.
Voici une applet javascript qui test le simulateur Math.random().
Appuyer sur le bouton '+100' pour déclencher 100 tirs aléatoires.
Appuyer sur 'Recommencer' pour tout remettre à zéro.

Tirs uniformes sur une figure non rectangulaire

Supposons que nous voulions déclencher un tir uniforme sur le disque de rayon 1 inscrit dans un carré de côté 2.
On peut bien entendu déclencher un tir uniforme sur le carré et 'ignorer' les tirs qui sont hors du cercle (revoir par exemple cette page).
Cependant, pour plus d'efficacité, on peut vouloir déclencher un tir dont on sûr a priori qu'il sera dans le disque.
Une possibilité consiste à tirer une abscisse aléatoire dans l'intervalle [-1,+1] par exemple X=1-2*random.random() en python, puis à tirer ensuite un Y aléatoire uniforme dans l'intervalle [-√(1-X²),+√(1-X²)].
C'est un mauvais choix car on favorise une densité de points plus grande sur les cordes x=X lorsque X est près de -1 ou de +1.
Voir par exemple l'applet suivante fondée sur ce principe :

Le passage en coordonnées polaires, crée un autre défaut. Il favorise une densité de points élevée sur les cercles de petit rayon, donc une densité plus élevée au voisinage de l'origine.
C'est parce qu'avec notre modèle P(ρ≤R)=R, alors que dans la réalité pour une distribution uniforme des points sur le disque P(ρ≤R)=R².

Il est pourtant possible de générer un tir aléatoire uniforme sur un disque.
Compte tenu de la remarque précédente, il suffit pour cela de générer un angle θ uniforme sur [0,2π[ ainsi qu'un réel ρ uniforme sur [0,1], le point aléatoire étant M(√ρcos(θ),√ρsin(θ)).
L'évènement √ρ≤R étant alors équivalent à ρ≤R².
Vous pouvez, ci-dessous, observer cette simulation.