Philippe Flajolet (INRIA, Rocquencourt)

Une expérience bien connue due à Buffon produit un procédé probabiliste continu, une sorte de “calculateur analogique”, dont la probabilité de succès met en jeu le fameux nombre π. Est-il possible de composer des procédés probabilistes simples et discrets, fondés uniquement sur des tirages à pile ou face, pour atteindre le même résultat? Une des motivations est la réalisation de simulateurs de Boltzmann pour de grands modèles combinatoires discrets. Nous examinerons des constructions qui permettent d’atteindre des constantes telles que π, e−1, log2, √3, cos(1/4), ζ(5) et réaliser une grande variété de fonctions (exponentielles, trigonométriques, algébriques, logarithmiques, hypergéométriques, etc). On en déduira notamment des générateurs purement discrets de la loi de Poisson et de la loi logarithmique. L’un des générateurs associés au nombre Pi nécessite moins de sept tirages de pièces en moyenne et l’expérience peut être facilement réalisée par un humain.

(Ce travail est joint avec Maryse Pelletier et Michèle Soria, LIP6, Paris).