Tree algorithms for unbiased coin tossing with a biased coin

DOI10.1214/AOP/1176993384MaRDI QIDQ791971zbMATH OpenOpenAlexFDO

Authors Q. F. Stout, Bette Warren

Publication date 1984

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aop/1176993384

zbMATH Keywords

optimal algorithmcoin tossingtree algorithms

Mathematics Subject Classification ID

Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40)

Recommendations

• Optimal random number generation from a biased coin
• Generation of discrete distributions from biased coins
• Efficient generation of fair dice with few biased coins
• Optimal coin flipping
• How to turn loaded dice into fair coins

Cited in

(12)

• How to turn loaded dice into fair coins
• Optimal random number generation from a biased coin
• Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
• An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
• Optimal coin flipping
• Exact output rate of Peres's algorithm for random number generation
• Sharp entropy bounds for discrete statistical simulation
• An instance-based algorithm for deciding the bias of a coin
• Efficient simulations by a biased coin
• From biased coin to any discrete distribution
• An optimal algorithm for simulation of true die by symmetric coin
• An efficient method for generating a discrete uniform distribution using a biased random source

This page was built for publication: Tree algorithms for unbiased coin tossing with a biased coin

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