unbiased coin flipping algorithm

(algorithm)

Definition: To get unbiased random bits, flip a coin twice. If it comes up heads then tails, the result bit is 1. It it comes up tails then heads, the result is 0. Repeat the double flips until one of these occurs.

Generalization (I am a kind of ...)
Las Vegas algorithm.

See also pseudo-random number generator.

Author: PEB

More information

John von Neumann, Various Techniques Used in Connection With Random Digits, von Neumann's Collected Works, volume 5, pages 768-770, 1963.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 28 July 2022.
HTML page formatted Thu Jul 28 12:11:16 2022.

Cite this as:
Paul E. Black, "unbiased coin flipping algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 28 July 2022. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/unbiasedCoinFlipAlgo.html