Abstract: The well-know needle experiment of Buffon can be regarded as an analog (i.e., continuous) device that stochastically "computes" the number 2/pi ~ 0.63661, which is the experiment's probability of success. Generalizing the experiment and simplifying the computational framework, we consider probability distributions, which can be produced perfectly, from a discrete source of unbiased coin flips. We describe and analyse a few simple Buffon machines that 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 of success are expressible in terms of numbers such as, exp(-1), log 2, sqrt(3), cos(1/4), aeta(5). Generally, we develop a collection of constructions based on simple probabilistic mechanisms that enable one to design 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.
Recommendations
Cited in
(10)- From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
- Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy
- Efficient random sampling of binary and unary-binary trees via holonomic equations
- An analytic approach to the asymptotic variance of trie statistics and related structures
- Sampling exactly from the normal distribution
- Non-redundant random generation algorithms for weighted context-free grammars
- Formulae and asymptotics for coefficients of algebraic functions
- Statistical estimation of some irrational numbers using an extension of Buffon's needle experiment
- Does a Program Yield the Right Distribution?
- Simulating a coin with irrational bias using rational arithmetic
This page was built for publication: On Buffon machines and numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5365035)
