Formal proof of fair coin simulation from biased coin

independenceprobability

Von Neumann's trick to simulate a fair coin from a biased coin is well-known:

  1. Toss the biased coin twice;
  2. If you get Head-Tail, return 1;
  3. If you get Tail-Head, return 0;
  4. Otherwise, go to 1.

It is known that this produces 1 or 0 with probability $1/2$ each, regardless of the probability $p$ of getting Head using the biased coin. The proof goes as follows:

The probabilities to obtain $0$ or $1$ during the first round (first two tosses) are the same, namely $p(1-p)$. With probability $1-2p(1-p)$, the algorithm starts over and since there is no memory, the probability to get a $1$ if the first round was not successful is the same as the initial probability to get a $1$. So if $r$ denotes this probability,
$r = p(1-p) + (1-2p(1-p)) r$,
whence $r = 1/2$.

My question is: How to formalize this proof? In particular, my problem is a formal justification of the fact that the probability after a first unsuccessful round remains the initial one.

In formal term, the previous proof can be as follows: Let $E$ be the event "the algorithm returns $1$" and HH, HT, TH, and TT be the events "the first two tosses are Head-Head", etc. Then by the law of total probabilities,
$$P[E] = P[E | HH]P[HH] + P[E|HT]P[HT]+P[E|TH]P[TH]+P[E|TT]P[TT].$$
Clearly, $P[E|HT]=1$, $P[E|TH]=0$ and $P[HH] = p^2$, $P[HT]=P[TH]=p(1-p)$ and $P[TT] = (1-p)^2$. The missing step is then: How to justify that $P[E|HH] = P[E|TT] = P[E]$? In other words, how to prove that $E$ is independent from HH and from TT?

Best Answer

Consider a Markov chain with the following states : a "no conclusion" state, a "TH" state and a "HT" state. Start the Markov chain at the "no conclusion state". Essentially, the idea is the following : we now flip two coins, and if they land as HT then we go to the HT state, if they land as TH , we go to the TH state, and if they land otherwise, we go back to the no conclusion state. Also, we make HT and TH absorbing states. From the following description, it is clear that the algorithm is simulated correctly in the random variable, and the result of the algorithm is $0$ or $1$ depending upon whether the Markov chain lands up at HT or TH. Let us write $NC$ for "no conclusion".

We have the following matrix in that case : $$ \begin{bmatrix} 1 - 2p(1-p)& p(1-p)& p(1-p) \\ 0& 1 &0 \\ 0 & 0 & 1 \end{bmatrix} = P $$

which is the transition matrix of the Markov chain. All we have to do is calculate the limit of $e_1P^n$ where $e_1 = (1,0,0)$. This amounts to the first row of $P^n$, or more precisely where it goes as $n \to \infty$. Let us make a claim by induction, which I leave you to verify.

Consider the matrix $$ Q = \begin{bmatrix} x & y & z \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$ Then, $$Q^n = \begin{bmatrix} x^n &(\sum_{i=0}^{n-1} x^n)y&(\sum_{i=0}^{n-1} x^n)z \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ and the first row of $Q^n$ is therefore $(x^n, \frac{(x^n-1)y}{x-1} , \frac{(x^n - 1)z}{x-1})$.

With this claim in the bag, we apply it for $x=1-2p(1-p) , y=z=p(1-p)$. Note that $0<x,y,z < 1$, and hence $P^n$ as $n\to \infty$ has a limit, which is $(0,\frac y{1-x}, \frac z{1-x})$. Substituting the values of $x,y,z$ gives the limiting distribution as $(0,\frac 12, \frac 12)$, as desired.

Related Question