Some Fast Buffon Machines

Some Fast Buffon Machines

Jérémie Lumbroso, GREYC, Université de Caen

Abstract:

Buffon machine are a general framework introduced by Flajolet, Pelletier and Soria (2011) to simulate discrete probability laws (Bernoulli of $1/\pi$, geometric of $\exp(−1)$, Poisson of $3/27$…) exactly without ever making any arithmetic operations: all computations are “done probabilistically” through a sequence of coin flips.

We will briefly recall this framework, and will extend it with a few additional constructions which either optimize existing laws, or allow for the simulation of new ones. The algorithms are elegant and amusing, but may also be competitively efficient, as we may show with the discrete uniform or Poisson laws.

This a work in progress with Michèle Soria.