# Simulating a Biased Coin with a Fair Coin

DevFeed: [Simulating a Biased Coin with a Fair Coin](<https://devfeed.tech/articles/simulating-a-biased-coin-with-a-fair-coin-40344.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/02/12/simulating-a-biased-coin-with-a-fair-coin/>)

Published: 2014-02-12T10:00:51Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Python](<https://devfeed.tech/topics/python.md>), [Mathematics](<https://devfeed.tech/topics/mathematics.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [calculus](<https://devfeed.tech/tags/calculus.md>), [coins](<https://devfeed.tech/tags/coins.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [convergent-series](<https://devfeed.tech/tags/convergent-series.md>), [floating-point](<https://devfeed.tech/tags/floating-point.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>)

## AI overview

This guest article presents a Python algorithm for simulating a biased coin using a fair coin. It reads the intended probability's binary expansion and compares each bit with an independent fair random bit, returning when they differ. The method produces probability exactly equal to the intended bias, including for irrational probabilities, and has constant expected running time when the probability's bits are efficiently computable.

## Source excerpt

This is a guest post by my friend and colleague Adam Lelkes. Adam's interests are in algebra and theoretical computer science. This gem came up because Adam gave a talk on probabilistic computation in which he discussed this technique. Problem: simulate a biased coin using a fair coin. Solution: (in Python) def biasedCoin(binaryDigitStream, fairCoin): for d in binaryDigitStream: if fairCoin() != d: return d Discussion: This function takes two arguments, an iterator representing the binary expansion of the intended probability of getting 1 (let us denote it as $ p$) and another function that returns 1 or 0 with equal probability.