APM: On Buffon Machines and Numbers

jameschoate at austin.rr.com jameschoate at austin.rr.com
Wed Jul 1 06:12:58 PDT 2009

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, and 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 (these are in particular required to transform continuous Boltzmann samplers of classical combinatorial structures into purely discrete random generators). Say that a number is Buffon if it is the probability of success of a probabilistic experiment based on discrete coin flippings. 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, sqrt(3), 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. 


 -- -- -- --
Venimus, Vidimus, Dolavimus

James Choate
jameschoate at austin.rr.com
james.choate at twcable.com

Adapt, Adopt, Improvise
 -- -- -- --

More information about the Austin mailing list