# Formal proof of fair coin simulation from biased coin

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?

• i guess measure theory. i mean, you need to define the probability of everything. "probability" itself isn't a rigorous word. Sep 11, 2019 at 13:00
• Do you know measure theory and random variables? This has to do with convergence of random variables. Sep 11, 2019 at 13:23
• @астонвіллаолофмэллбэрг While being very far from a specialist, I do have some knowledge of measure theory but I do not see the link with convergence. As a side comment, my aim is to give the most elementary while formally correct proof for some non-math students. Thus if the justification requires too much measure theory, I'll probably skip it. Sep 11, 2019 at 13:50
• In presenting the von Neumann trick to people reasonably unfamiliar with math, it's useful to spend a few words on the assumed independence of the outcomes of all tosses. Sep 11, 2019 at 14:09
• How about Markov chains, in that case? I plan to show that the algorithm is simulated by a Markov chain, whose properties I can then exploit to show the result. Sep 11, 2019 at 14:37

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, 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.