One of the questions that I was asked on a recent onsite interview with was a probability question. It went as follows:

Given an unfair coin which flips as heads with probability $0<p<1$ as a source of randomness, come up with an algorithm that flips a fair coin, with probability of flipping a head exactly $0.5$ .

The trick here is to consider a pair of coin flips, with the set of possible results being $\{HH,HT,TH,TT\}$ . Then both $HT$ and $TH$ have probability of exactly $p(1-p)$ which means we can use these two events to simulate a fair coin flip.

And of course, as you would suspect, this is a relatively well-known problem.
The process of flipping coins with probability $p$
for heads is
mathematically referred to as a *Bernoulli process*, with the key part
being that the unfairness is consistent, that is $p$
does not change
between the flips. Using an unfair Bernoulli process to generate a fair
one is an example of *randomness extraction*. You can read up on both of
these topics on Wikipedia. The particular extractor discussed above, which is
one solution to the problem, is called the von Neumann extractor. It's
implemented here in Python using two generators. See
the post on iterators and generators
for more implementation details.

```
import random
def bernoulli_process(p):
if p > 1.0 or p < 0.0:
raise ValueError("p should be between 0.0 and 1.0.")
while True:
yield random.random() > p
def von_neumann_extractor(process):
while True:
x, y = process.next(), process.next()
if x != y:
yield x
```

For a full discussion of this problem, and the best possible solution, see the article by Michael Mitzenmacher.

## Comments