The Bernoulli factory

A few months ago, Latuszyński, Kosmidis, Papaspiliopoulos and Roberts arXived a paper I should have noticed earlier as its topic is very much related to our paper with Randal Douc on the vanilla Rao-Blackwellisation scheme. It is motivated by the Bernoulli factory problem, which aims at (unbiasedly) estimating f(p) from an iid sequence of Bernoulli B(p). (The paper only considers functions f valued in [0,1]. In our case, the function is f(p)=1/p.) It appears that this problem has been studied for quite a while, in particular by Yuval Peres. Being in a train to Marseille (thanks to Eyjafjallajökull!), I do not have access to those earlier papers of Peres’, but Latuszyński et al. mentions that there are conditions on f such that it is sufficient to generate a Bernoulli event with probability

$f_0(p) = \min (2p, 1-2\epsilon)$

where $\varepsilon>0$ is arbitrary. In particular, constructing an unbiased estimator of

$f_0(p) = \min ( 2p, 1 )$

does not seem to be achievable (Nacu and Peres, 2005). (The way it is rephrased in Latuszyński et al. does not seem correct, though, as they state that f(p)=2p cannot be estimated in an unbiased manner, missing the constraint that the estimator must belong to [0,1], I think.)

The paper by Latuszyński et al. develops an original scheme to achieve simulation from B(f(p)) through the simulation of two bounding sequences that are respectively super- and submartingales and that both converge to f(p). (But their simulation scheme does not have to wait for the two sequences to coalesce.) This idea presumably (?) stemmed from the experience of the authors, in particular Gareth Roberts, in perfect sampling, since the most advanced perfect samplers made intensive use of this sandwiching idea of Kendall and Møller (2000, Advances in Applied Probability). The whole thing is also related to the famous Series B paper of Beskos et al. (2006). The method of Latuszyński et al. then builds the upper and lower processes via a truncated series decomposion of f(p), whose availability induces constraints on f.

The first application illustrated in Latuszyński et al. is the unbiased estimation of a transform f(p) that has a known series expansion

$f(p) = \sum_{i=1}^\infty (1-)^k a_k p^k$

with

$1\le a_1\le a_2 \le \cdots$

In that case, we could use the scheme of our paper with Randal, estimating $p^k$ by

$\hat p^k = X_1\ldots X_k.$

The probability of using at least n simulations is then $p^n$ , while the scheme of Latuszyński et al. leads to a probability of $a_n p^n$ . (Note however that the direct approach above allows to handle any series decomposition, alternating or not, with no constraint on the $a_i$ ‘s.)

What I find exciting about this Bernoulli factory problem is that the well-known issue of the absence of unbiased estimators for most transforms of a parameter p (Lehmann and Casella, 1998) vanishes when an unlimited number of iid simulations with mean p is available. Here are the slides of the talk given by Omiros last week at the Big’ MC seminar:

This entry was posted on April 23, 2010 at 12:24 am and is filed under R, Statistics with tags Bernouilli factory, control variates, MCMC, Metropolis-Hastings, Monte Carlo methods, Rao-Blackwellisation, simulation, slides. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “The Bernoulli factory”

workshop in Columbia [day 3] « Xi'an's Og Says:
September 27, 2011 at 12:12 am

[…] is a problem when f is non linear. This reminded me (and others) of the Bernoulli factory and of the similar trick we use in the vanilla Rao-Blackwellisation paper with Randal Douc. […]

Reply
Another Bernoulli factory « Xi'an's Og Says:
February 11, 2011 at 7:03 am

[…] of it only yesterday and find it quite interesting in that it links the Bernoulli factory method I discussed a while ago and my ultimate perfect sampling paper with Jim Hobert. In this 2004 paper in Annals of Applied […]

Reply

Xi'an's Og