Fair Binary Sequence from Unbalanced Coin

Solution & Explanation

The problem at hand is to generate a fair sequence of zeros and ones using an unfair coin. The solution relies on a method known as the von Neumann extractor or von Neumann corrector. This technique is designed to convert a biased sequence of binary outcomes into an unbiased sequence.

Understanding the Problem

The coin in question does not have equal probabilities for heads and tails. Let's denote the probability of heads as $p$ and tails as $1 - p$. The goal is to generate a sequence where the probability of obtaining a 0 or a 1 is equal, i.e., both occur with a probability of 0.5.

The von Neumann Method

The von Neumann method works by analyzing pairs of coin flips. Here's how it works:

1. Flip the Coin Twice:

   • Record the outcome of the first flip as $F_1$.
   • Record the outcome of the second flip as $F_2$.

2. Evaluate the Pair:

   • If the outcomes are different (i.e., $F_1 = \text{heads}$ and $F_2 = \text{tails}$, or $F_1 = \text{tails}$ and $F_2 = \text{heads}$), use this pair to generate a fair bit.
   • Specifically, assign:
     • $F_1 = \text{heads}, F_2 = \text{tails}$ to 1.
     • $F_1 = \text{tails}, F_2 = \text{heads}$ to 0.

3. Ignore Identical Pairs:

   • If both flips are the same (i.e., $F_1 = F_2$), disregard the pair and repeat the process.

Why It Works

• Equal Probability for HT and TH:

  • The probability of obtaining heads followed by tails (HT) is $p(1-p)$.
  • The probability of obtaining tails followed by heads (TH) is $(1-p)p$.
  • Both scenarios have the same probability, $p(1-p)$, ensuring that the output is unbiased.

• Rejection of HH and TT:

  • Pairs like HH and TT are discarded. This is because they do not contribute to bias correction. Ignoring them ensures that only unbiased pairs contribute to the sequence.

Efficiency Considerations

• Discarding Rate:

  • On average, 75% of the pairs will be discarded. This is because there are four possible outcomes for two flips (HH, HT, TH, TT), and only HT and TH are used.

• Expected Output Rate:

  • While this method is efficient in terms of bias correction, it is less so in terms of speed. Expect to generate one unbiased bit for every four flips on average.

Conclusion

By using the von Neumann method, we effectively transform an unfair coin into a fair binary sequence generator. This approach is elegant and robust, relying on simple probability principles to ensure that the generated sequence is uniformly distributed, regardless of the initial bias of the coin.