2013/08/07 by Mark Huber · 1 voice · 3 citations
Computer Science · Mathematics · #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference #math.PR
paper · pdf · doi:10.1017/s0963548315000371
openalex publication_date 2016/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract Suppose that X 1 , X 2 , . . . are independent identically distributed Bernoulli random variables with mean p . A Bernoulli factory for a function f takes as input X 1 , X 2 , . . . and outputs a random variable that is Bernoulli with mean f ( p ). A fast algorithm is a function that only depends on the values of X 1 , . . ., X T , where T is a stopping time with small mean. When f ( p ) is a real analytic function the problem reduces to being able to draw from linear functions Cp for a constant C > 1. Also it is necessary that Cp ⩽ 1 − ε for known ε > 0. Previous methods for this problem required extensive modification of the algorithm for every value of C and ε. These methods did not have explicit bounds on 𝔼[T] as a function of C and ε. This paper presents the first Bernoulli factory for f ( p ) = Cp with bounds on 𝔼[T] as a function of the input parameters. In fact, sup p ∈[0,(1−ε)/ C ] 𝔼[T] ≤ 9.5ε −1 C . In addition, this method is very simple to implement. Furthermore, a lower bound on the average running time of any Cp Bernoulli factory is shown. For ε ⩽ 1/2, sup p ∈[0,(1−ε)/ C ] 𝔼[T] ≥0.004 C ε −1 , so the new method is optimal up to a constant in the running time.