Générateur de nombres aléatoires - Définition

Introduction

Un générateur de nombres aléatoires, random number generator (RNG) en anglais, est un dispositif capable de produire une séquence de nombres dont on ne peut pas « facilement » tirer des propriétés déterministes, de façon à ce que cette séquence puisse être appelée : suite de nombres aléatoires.

Des méthodes pour obtenir des nombres aléatoires existent depuis très longtemps et sont utilisées dans les jeux de hasard : dés, roulette, tirage au sort, mélange des cartes, etc. Elles peuvent toutefois souffrir (et souffrent généralement) de biais. Actuellement, les meilleures méthodes, censées produire des suites véritablement aléatoires, sont des méthodes physiques qui profitent du caractère apparemment aléatoire des phénomènes quantiques.

Ces générateurs ont une utilité dans de nombreux domaines. Outre les jeux, on peut citer :

• la simulation
• l’analyse
• l'échantillonnage
• la prise de décision
• la sécurité informatique (cryptologie)

La nécessité d'obtenir des données aléatoires est présente dans bien d'autres domaines. Certains domaines peuvent se contenter de données pseudo-aléatoires et utilisent des générateurs qui s'approchent plus ou moins d'un aléa parfait.

Première approche du problème

L'aléatoire : une notion difficile

Produire des nombres aléatoires pose une double difficulté : la production en elle-même bien sûr, mais surtout savoir caractériser le hasard. Et ce deuxième point est encore aujourd'hui un véritable problème ! En effet, même pour les mathématiciens, le caractère aléatoire est une notion difficile à appréhender. Comment donner une définition satisfaisante ? Est-il raisonnable de le définir en donnant une liste infinie de tout ce que l'aléatoire n'est pas ?

Une définition célèbre, due à Cournot, est intéressante en pratique :

« Le hasard, c'est la rencontre de deux séries causales indépendantes. »

Cette définition est utilisable pour construire de bons générateurs de nombres aléatoire, par le croisement d'un générateur de nombres (ayant de « bonnes » propriétés, notamment la possibilité de générer tous les nombres parmi lesquels on veut faire le tirage) avec un générateur de stop indépendant.

Le bon choix du phénomène

Puisque l'on ne peut pas définir l'aléatoire, on va profiter du fait que certains phénomènes sont intrinsèquement aléatoires ; et les exploiter pour former les nombres que nous cherchons. Le problème est que ces phénomènes ne sont souvent aléatoires qu'en apparence.

Par exemple : lors du lancement d'un dé, il est possible de prédire quelle sera la face supérieure (grâce aux lois de la physique qui s'appliquent au dé, en l'occurrence : la gravitation, le principe fondamental de la dynamique, l'action réaction...). En contrepartie, les problèmes d'incertitude sur les conditions initiales et la forte dépendance du problème à ces conditions rend le trajet du dé imprévisible. Imprévisible mais non pas aléatoire. On notera bien la différence. On est en fait ici dans le domaine de la théorie du chaos.

Les problèmes de biais

Que le phénomène soit imprévisible plutôt qu'aléatoire ne pose pas un problème pour la suite si tant est que les conditions initiales sont, elles, aléatoires, mais ce n'est pas toujours le cas. Par exemple, dans le cas du pile ou face, on a tendance à mettre une face au-dessus plus souvent que l'autre. Or il se trouve que la face qui était au-dessus au début a 20% de chance de plus que l'autre d'être la face obtenue. Le phénomène présente donc un biais, dans le sens où, dans une certaine mesure, on peut prédire le résultat que l'on va obtenir.