Optimal linear Bernoulli factories for small mean problems

DOI10.1007/S11009-016-9518-3zbMATH Open1379.65006arXiv1507.00843OpenAlexW2963290835MaRDI QIDQ2397969FDOQ2397969

Mark Huber

Publication date: 14 August 2017

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Stationarity detection in the initial transient problem
• Fast simulation of new coins from old
• A Bernoulli factory
• Simulating events of unknown probabilities via reverse time martingales
• Nearly Optimal Bernoulli Factories for Linear Functions

Cited In (6)

• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
• Bernoulli factory: the \(2\mathtt{p}\)-coin problem
• Generation of Bernoulli processes
• Combinatorial Bernoulli factories
• Barker's algorithm for Bayesian inference with intractable likelihoods

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)