Optimal linear Bernoulli factories for small mean problems

DOI10.1007/S11009-016-9518-3MaRDI QIDQ2397969zbMATH OpenOpenAlexFDO

Authors Mark Huber

Publication date 14 August 2017

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.00843

zbMATH Keywords

random walkrandomized algorithmPoisson processregenerative processesBernoulli factory (BF)near perfect simulation

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Abstract: Suppose a coin with unknown probability $p$ of heads can be flipped as often as desired. A Bernoulli factory for a function $f$ is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability $f(p)$ of heads. Applications include near perfect sampling from the stationary distribution of regenerative processes. When $f$ is analytic, the problem can be reduced to a Bernoulli factory of the form $f(p)=Cp$ for constant $C$. Presented here is a new algorithm where for small values of $Cp$, requires roughly only $C$ coin flips to generate a $Cp$ coin. From information theory considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For $Cp$ large, the new algorithm can also be used to build a new Bernoulli factory that uses only 80% of the expected coin flips of the older method, and applies to the more general problem of a multivariate Bernoulli factory, where there are $k$ coins, the $k$th coin has unknown probability $p_k$ of heads, and the goal is to simulate a coin flip with probability $C_1{p}_1+cdots+C_k{p}_k$ of heads.

Recommendations

• Nearly optimal Bernoulli factories for linear functions
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• A Bernoulli factory
• Generation of Bernoulli processes
• Simulating events of unknown probabilities via reverse time martingales

Cites work

• scientific article; zbMATH DE number 3626409 (Why is no real title available?)
• A Bernoulli factory
• Fast simulation of new coins from old
• Nearly optimal Bernoulli factories for linear functions
• Simulating events of unknown probabilities via reverse time martingales
• Stationarity detection in the initial transient problem

Cited in

(10)

• Bernoulli factory: the \(2\mathtt{p}\)-coin problem
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• Simulating events of unknown probabilities via reverse time martingales
• Nearly optimal Bernoulli factories for linear functions
• Bernoulli Factories for Flow-Based Polytopes
• Generation of Bernoulli processes
• An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
• Combinatorial Bernoulli factories
• Barker's algorithm for Bayesian inference with intractable likelihoods
• Multiparameter Bernoulli factories

This page was built for publication: Optimal linear Bernoulli factories for small mean problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397969)