Philippe Duchon (LaBRI, Bordeaux)

Le problème du tirage de nombres aléatoires selon des lois de probabilités bien définies est à peu près aussi vieux que l’informatique; von Neumann s’y est intéressé dès le début des années 1950.

Dans la version classique, on suppose que la machine manipule des nombres réels sans restrictions et que les calculs (au moins les opérations arithmétiques) sont exacts; la primitive donnant accès à de l’aléa est typiquement supposée donner un réel uniforme entre 0 et 1. De nombreux algorithmes pour la simulation exacte des lois de probabilités usuelles sont connus dans ce modèle.

Le problème discret correspondant a été moins étudié. On considère alors que l’on a accès à de l’aléa sous la forme de bits aléatoires (“pile ou face”), et il est alors naturel de considérer que les nombres réels sont représentés en écriture binaire, a priori sans contrainte de précision. Un programme de simulation d’une loi de probabilités donnée est alors un programme qui fournit un par un une séquence de chiffres binaires aléatoires représentant un nombre réel.

Beaucoup de lois de probabilités continues classiques se prêtent à ce modèle de génération aléatoire, à commencer par la loi exponentielle pour laquelle un algorithme est déjà décrit par von Neumann. Je présenterai des exemples de “machines de Buffon continues”, pour reprendre une terminologie dûe à Flajolet, Soria et Pelletier; et j’explorerai les limites de ce qui est possible si on demande que la machine qui réalise la simulation n’a accès qu’à une quantité finie de mémoire.