Common Bernoulli factory algorithms
Author awllee
1 Star
Updated Last
2 Years Ago
Started In
August 2018


Build Status Build status Coverage Status

This package provides some Bernoulli factory algorithms, and a constrained, unbiased estimation algorithm.

Given a function g such that g() returns a Bernoulli(p) variate, and a function f mapping [0,1] -> [0,1] a Bernoulli factory algorithm should use calls to g produce a Bernoulli(f(p)) variate. Not all functions f admit an algorithm (Keane & O'Brien, 1994), and some algorithms require additional information.

Currently implemented

Command Description
f(p) = exp(-λp), λ >= 0 expMinus(g, λ)
f(p) = p⁠^a, a >= 0 power(g, a)
f(p) = C*p / (1+C*p), C > 0 logistic(g, C)
f(p) = C*p, ϵ ∈ (0, 1-C*p) linear(g, C, ϵ)
f(p) = C/p, ϵ ∈ (0, p-C) inverse(g, C, ϵ)
f(p1, p2) = C1*p1 / (C1*p1 + C2*p2) twocoin(g1, g2, C1, C2)

Constrained, unbiased estimation

Also implemented is a variant of signed estimation, signedEstimate(μ, φ, a, b, δ, c, n):

Let X ~ μ and real-valued φ satisfy

a <= inf_x φ(x) < b < δ <= E[φ(X)] < sup_x φ(x) <= c,

with known (a, b, δ, c). If simulation from μ and evaluation of φ is feasible, one can simulate W satisfying

  1. E[W] = E[φ(X)]
  2. Pr(b <= W <= max{2b-a,c}) = 1

The random variable W is the product of two independent random variables, X and Z, and the positive integer parameter n specifies a number of averages to use to define X.

Algorithms used

expMinus is an obvious extension of the approach described in Wastlund (1999) for λ=1.

power is from Mendo (2016).

logistic is from Huber (2017).

linear is from Huber (2016), and for a large range of parameter settings appears to use the least expected flips of all algorithms for this problem.

inverse is described in Lee, Doucet & Łatuszyński (2014).

twocoin is described in Gonçalves, Łatuszyński & Roberts (2017).

signedEstimate is described in Appendix C of Lee, Doucet & Łatuszyński (2014).


All Bernoulli factory algorithms return a tuple (X, flips) where X is true or false and flips is the number of calls of g() by the algorithms.

signedEstimate returns a tuple (X, flips, calls) where X is true or false, flips is the number of Bernoulli factory flips and calls is the number of calls of μ() by the algorithms. calls is typically much larger thatn flips


Gonçalves, F.B., Łatuszyński, K.G. and Roberts, G.O., 2017. Exact Monte Carlo likelihood-based inference for jump-diffusion processes. arXiv:1707.00332

Huber, M., 2016. Nearly optimal Bernoulli factories for linear functions. Combinatorics, Probability and Computing, 25(4), pp.577-591.

Huber, M., 2017. Optimal linear Bernoulli factories for small mean problems. Methodology and Computing in Applied Probability, 19(2), pp.631-645.

Keane, M.S. and O'Brien, G.L., 1994. A Bernoulli factory. ACM Transactions on Modeling and Computer Simulation (TOMACS), 4(2), pp.213-219.

Lee, A., Doucet, A. and Łatuszyński, K., 2014. Perfect simulation using atomic regeneration with application to Sequential Monte Carlo. arXiv:1407.5770

Mendo, L., 2016. An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series. arXiv:1612.08923

Wästlund, J., 1999. Functions arising by coin flipping. Technical Report, KTH, Stockholm.

Used By Packages

No packages found.