On Buffon Machines and Numbers

Abstract

Buffon's needle experiment is well-known: take a plane on which parallel lines at unit distance one from the next have been marked, throw a needle of unit length at random, and, finally, declare the experiment a success if the needle intersects one of the lines. Basic calculus implies that the probability of success is 2/pi~0.63661, so that the experiment can be regarded as an analog (i.e., continuous) device that stochastically “computes” 2/pi. Generalizing the experiment and simplifying the computational framework, we ask ourselves which probability distributions can be produced perfectly, from a discrete source of unbiased coin flips. We describe and analyse a few simple Buffon machines that can generate geometric, Poisson, and logarithmic-series distributions. We provide human-accessible Buffon machines, which require a dozen coin flips or less, on average, and produce experiments whose probabilities are expressible in terms of numbers such as pi exp(-1), log2, sqrt2557421, cos(1/4), zeta(5). More generally, we develop a collection of constructions based on simple probabilistic mechanisms that enable one to create Buffon experiments involving compositions of exponentials and logarithms, polylogarithms, direct and inverse trigonometric functions, algebraic and hypergeometric functions, as well as functions defined by integrals, such as the Gaussian error function.