Problem 13 - A Modern Introduction to Probability and Statistics: Understanding Why and How

Question

We give you an unfair coin and you do not know \(\mathrm{P}(H)\) for this coin. Can you simulate a fair coin, and how many tosses do you need for each fair coin toss?

Step-by-Step Solution

Answer

Use von Neumann's method; expect 4 tosses per fair coin toss.

Step 1: Understand the Problem

We need to simulate a fair coin toss using an unfair coin, where the probability of heads \( \mathrm{P}(H) \) is unknown.

Step 2: Use von Neumann's Method

The von Neumann method involves using pairs of coin tosses to determine fair outcomes. If you toss the coin twice and get a head followed by a tail (HT), consider it as heads for the fair coin. If the outcome is tail followed by head (TH), consider it as tails for the fair coin. Ignore the outcomes HH and TT, and repeat until you get HT or TH.

Step 3: Analyze Tosses Needed

Each pair has a 25% chance (\(\frac{1}{4}\)) of being HT and a 25% chance of being TH, assuming each toss is independent. Therefore, the expected number of tosses needed for a fair outcome is 4 tosses.

Step 4: Conclusion on Fair Coin Simulation

By using pairs of tosses, we can simulate a fair coin from an unfair coin with an expected number of 4 tosses per fair outcome.

Key Concepts

Unfair Coin

An unfair coin is a coin where the probability of it landing on heads or tails is not equal. Typically, we assume a coin is fair, meaning \( \mathrm{P}(H) = \mathrm{P}(T) = 0.5 \). However, with an unfair coin, these probabilities are skewed, and we do not specifically know the exact probability of landing heads or tails. This uncertain nature makes it challenging to predict the outcomes accurately. These types of coins are fascinating because they introduce an element of randomness and unsureness that makes typical probability predictions unreliable. In the context of simulations, using an unfair coin requires special techniques, such as the von Neumann method, to achieve fair results.

Fair Coin

A fair coin is defined by an equal probability of landing on heads or tails with each flip. This means that \( \mathrm{P}(H) = \mathrm{P}(T) = 0.5 \). This equal probability ensures that no outcome is favored over the other, making it a model for balanced and unbiased results.
In practical terms, simulating a fair coin flip involves creating conditions where this equal probability holds true. An unfair coin can be turned into a fair coin through specific methods that balance out the probabilities over a series of flips. For example, the von Neumann method is a technique used to simulate a fair toss from an unfair coin, effectively mimicking these balanced outcomes by using certain patterns and ignoring others.

Von Neumann Method

The Von Neumann method is a clever technique designed to simulate fair outcomes using potentially unfair tools, like an unfair coin. This method works by focusing on pairs of outcomes. Here’s how it operates:

• Flip the unfair coin twice.
• If the result is head followed by tail (HT), count it as one fair 'heads'.
• If the result is tail followed by head (TH), count it as one fair 'tails'.
• Ignore outcomes like HH (head-head) and TT (tail-tail), and try again.

This technique effectively creates fair coin flips by eliminating bias. It does this by focusing only on patterns where the order of results would naturally exhibit an equal chance of being one of our desired fair outcomes. By ignoring the unbalanced sequences, this method allows the uneven odds of an unfair coin to yield the same probabilities as a fair coin would.

Expected Number of Tosses

The expected number of tosses refers to the average number of times you need to flip the coin to achieve a specific outcome, in our case, using the von Neumann method to simulate a fair toss. Given that the probabilities of getting HT or TH are each \( 0.25 \) or \( \frac{1}{4} \), and because results HH and TT are ignored, we can calculate the expected number of tosses needed:

• The chance of any specific sequence happening is derived from multiplying their individual probabilities (assuming independence).
• Since only HT and TH are counted, each occurring with probability \( \frac{1}{4} \), we expect that every two pairs of flips (four flips total) will see one pair hitting either HT or TH.

Thus, on average, four tosses are needed to simulate a fair outcome using the von Neumann method. This average expectation is vital for estimating resources and time for probabilistic simulations.