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

Bernoulli factory (BF)near perfect simulationPoisson processrandom walkrandomized algorithmregenerative processes

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.

Review text

The paper presents several algorithms producing Bernoulli factories (linear BF, logistic BF, high power logistic BF, multivariate BF, their variants, etc.) for the function \(f(p)=Cp\) for some constant \(C\). To that purpose the author uses Poisson processes and random walks. He is also interested in the mean time needed for accomplishing the suggested algorithms and shows that it is up to 80 times better than the algorithms proposed earlier. No information about the variability of the suggested algorithms is given.

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

• A Bernoulli factory
• Fast simulation of new coins from old
• scientific article; zbMATH DE number 3626409 (Why is no real title available?)
• 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

(11)

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

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)