MENU

An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series

Mendo, Luis

STOCHASTIC PROCESSES AND THEIR APPLICATIONS
2019
VL / 129 - BP / 4366 - EP / 4384
abstract
Given a sequence of independent Bernoulli variables with unknown parameter p, and a function f expressed as a power series with non-negative coefficients that sum to at most 1, an algorithm is presented that produces a Bernoulli variable with parameter f (p). In particular, the algorithm can simulate f (p) = p(a), a is an element of (0, 1). For functions with a derivative growing at least as f (p)/p for p -> 0, the average number of inputs required by the algorithm is asymptotically optimal among all simulations that are fast in the sense of Nacu and Peres. A non-randomized version of the algorithm is also given. Some extensions are discussed. (C) 2018 Elsevier B.V. All rights reserved.

AccesS level

Green accepted

MENTIONS DATA