By chance I came across a 2010 paper entitled On Buffon Machines and Numbers by Philippe Flajolet, Maryse Pelletier and Michèle Soria. Which relates to Bernoulli factories, a related riddle, and the recent paper by Luis Mendo I reviewed here. What the authors call a Buffon machine is a device that produces a perfect simulation of a discrete random variable out of a uniform bit generator. Just like (George Louis Leclerc, comte de) Buffon’s needle produces a Bernoulli outcome with success probability π/4. out of a real Uniform over (0,1). Turned into a sequence of Uniform random bits.
“Machines that always halt can only produce Bernoulli distributions whose parameter is a dyadic rational.”
When I first read this sentence it seemed to clash with the earlier riddle, until I realised the later started from a B(p) coin to produce a fair coin, while this paper starts with a fair coin.
The paper hence aims at a version of the Bernoulli factory problem (see Definition 2), although the term is only mentioned at the very end, with the added requirement of simplicity and conciseness translated as a finite expected number of draws and possibly an exponential tail.
It first recalls the (Forsythe–)von Neumann method of generating exponential (and other) variates out of a Uniform generator (see Section IV.2 in Devroye’s generation bible). Expanded into a general algorithm for generating discrete random variables whose pmf’s are related to permutation cardinals,
if the Bernoulli generator has probability λ. These include the Poisson and the logarithmic distributions and as a side product Bernoulli distributions with some logarithmic, exponential and trigonometric transforms of λ.
As a side remark, a Bernoulli generator with probability 1/π is derived from Ramanujan identity
as “a discrete analogue of Buffon’s original. In a neat connection with Mendo’s paper, the authors of this 2010 paper note that Euler’s constant does not appear to be achievable by a Buffon machine.
A form of Bernoulli factory with limited energy from The Riddler: being given the choice of 0<p<1, what is the minimal number n of throws such that the outcomes of n iid B(p) draws can be partitioned into six groups of equal probability? Running a brute force R code [in the train to Cambridge] and checking random partitions for different values of p and n, I found a near fit for n=6 and p around 0.42. With partition weights![(1-[1-\rho])^\gamma=1+\gamma(1-\rho)+\frac{\gamma(\gamma-1)(1-\rho)^2}{2}+\cdots](https://s0.wp.com/latex.php?latex=%281-%5B1-%5Crho%5D%29%5E%5Cgamma%3D1%2B%5Cgamma%281-%5Crho%29%2B%5Cfrac%7B%5Cgamma%28%5Cgamma-1%29%281-%5Crho%29%5E2%7D%7B2%7D%2B%5Ccdots&bg=000000&fg=B0B0B0&s=0&c=20201002)
