Search code examples
randomprobability

Generating uniform random bits using a source of biased bits

We have a source of biased random bits, namely a source that produces 0 with probability p, or 1 with probability 1 - p.

How can we use this source to build a generator that produces 0 or 1 with equal probability?

Solution

  • You throw the biased coin two times. There are four possible outcomes:

    • 01 - Pick the number 0 as the return value.
    • 10 - Pick the number 1 as the return value.
    • 00 - Start again throwing two coins.
    • 11 - Start again throwing two coins.

    When you calculate the probability for getting 01 or 10, you will see it's the same. That way the sequence 01 and 10 appear with the same probability, regardless of the value p.