Fetching the paper…

Reading the bibliography…

2011

A Practical Implementation of the Bernoulli Factory

Thomas, A. C., Blanchet, Jose H.

Original
PDF
Post on X

Understand

The Bernoulli Factory is an algorithm that takes as input a series of i.i.d.

Bernoulli random variables with an unknown but fixed success probability $p$, and outputs a corresponding series of Bernoulli random variables with success probability $f(p)$, where the function $f$ is known and defined on the interval $[0,1]$.
While several practical uses of the method have been proposed in Monte Carlo applications, these require an implementation framework that is flexible, general and efficient.
We present such a framework for functions that are either strictly linear, concave, or convex on the unit interval using a series of envelope functions defined through a cascade, and show that this method not only greatly reduces the number of input bits needed in practice compared to other currently proposed solutions for more specific problems, and is easy to specify for simple forms, but can easily be coupled to asymptotically efficient methods to allow for theoretically strong results.

A Practical Implementation of the Bernoulli Factory · Around

Built on

Various Techniques Used in Connection with Random Digits
von Neumann, J · 1951
Earlier work this paper cites.
Stationary Detection in the Initial Transient Problem
Asmussen, S · 1992
Earlier work this paper cites.
A Bernoulli Factory
Keane, M · 1994
Earlier work this paper cites.
An Interruptable Algorithm for Perfect Sampling via Markov Chains
Fill, J · 1998
Earlier work this paper cites.

Similar

A Mixture Representation of (pi) with Applications in Markov Chain Monte Carlo and Perfect Sampling
Hobert, J. P · 2004
Cited alongside, same era.
Exact Sampling, Regeneration and Minorization Conditions
Blanchet, J. H · 2005
Cited alongside, same era.
Fast Simulation of New Coins from Old
Nacu, S · 2005
Cited alongside, same era.
Using a Markov Chain to Construct a Tractable Approximation of an Intractable Probability Distribution
Hobert, J · 2006
Cited alongside, same era.

Then

Exact Simulation and Error-Controlled Sampling via Regeneration and a Bernoulli Factory
Blanchet, J. H · 2007
Later among the works it cites.
Simulating Events of Unknown Probabilities via Reverse Time Martingales
Original
Latuszynski, K · 2011
Closest in time.
Exact Sampling for Intractable Probability Distributions via a Bernoulli Factory
Flegal, J · 2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…