Suppose that we want to generate the outcome of the flip of a fair coin, but that all we have at our disposal is a biased coin that lands on heads with some unknown probability p that need not be equal to 1 2 . Consider the following procedure for accomplishing our task: 1. Flip the coin. 2. Flip the coin again. 3. If both flips land on heads or both land on tails, return to step 1. 4. Let the result of the last flip be the result of the experiment.

(a) Show that the result is equally likely to be either heads or tails.

(b) Could we use a simpler procedure that continues to flip the coin until the last two flips are different and then lets the result be the outcome of the final flip?

From the information, we want to generate the outcome of the flip of a fair coin, but that all we have at our disposal is a biased coin that lands on heads with some unknown probability p that need not be equal to 1 2 .

We need to consider the following procedure: 1. Flip the coin. 2. Flip the coin again. 3. If both flips land on heads or both land on tails, return to step 1. 4.

We have to show that the result is equally likely to be either heads or tails.

Lets consider the flipping procedure.

From this formulation we can see that the outcomes of our procedure follow a conditional distribution:

$P\{$the procedure gives $H\}$$=P\left\{\right(T,H\left)\right|(T,H)or(H,T)\}$

$=\frac{P\left\{\right(T,H\left)\right\}}{P\left\{\right(T,H)or(H,T\left)\right\}}$

$=\frac{(1-p)p}{\left[\right(1-p)p+p(1-p\left)\right]}$

role="math" localid="1647080421100" $=\frac{1}{2}$

Similarly, the procedure gives tails with probability $\frac{1}{2}$

The probability to get either head or tail is$\frac{1}{2}$.

From the information, we want to generate the outcome of the flip of a fair coin, but that all we have at our disposal is a biased coin that lands on heads with some unknown probability p that need not be equal to 1 2 .

We need to consider the following procedure: 1. Flip the coin. 2. Flip the coin again. 3. If both flips land on heads or both land on tails, return to step 1. 4.

We have to determine could we use a simpler procedure that continues to flip the coin until the last two flips are different and then lets the result be the outcome of the final flip.

For any $0<p<1$, we will surely find both heads and tails eventually.

Thus method (b) gives $H$if and only if the first flip comes out $T$, which happens with probability $1-p$.

The method gives $T$if and only if the first flip is $H$, this happens with probability $p$.

Hence method (b) does not give fair coin flip results.

The difficulty in this problem is figuring out why our arguments in (a) do not work in the case of method (b).

In the above formulation of (a) we consider a fixed pair of coin flips (the first two flips), while in method (b) we take a randomly selected pair of coin flips, those where we first see a change in the outcomes.

This innocent-looking difference essentially modifies the probabilities of the outcomes $(H,T)and(T,H)$. Our arguments in (a), applied on case (b), would look like this:

$P\left\{\text{the procedure gives}H\right\}=P\left\{\right(T,H)\mid (T,H)\text{or}(H,T\left)\right\}$

$=\frac{P\left\{\right(T,H\left)\right\}}{P\left\{\right(T,H\left)\text{or}\right(H,T\left)\right\}}$

$=\frac{(1-p)}{\left[\right(1-p)+p]}$

$=1-p$

Similarly, the probability of outcome$Tisp$

Tails is the result if and only if the first throw is heads,

then the first different result is tails.

Therefore,

$P\left(\text{heads}\right)=1-p$