The End

Solution

The idea has two parts: 1. use the biased coin to simulate a fair coin; 2. use fair coin flips to choose a winner with probability exactly \(\alpha\). First, extract fair bits from the unfair coin. Toss the biased coin twice. - If the outcome is \(HT\), output \(0\). - If the outcome is \(TH\), output \(1\). - If the outcome is \(HH\) or \(TT\), ignore both tosses and try again. This is the classical von Neumann trick. The key point is \[ \Pr(HT)=p(1-p), \qquad \Pr(TH)=(1-p)p, \] so \[ \Pr(HT)=\Pr(TH). \] Therefore, conditional on seeing one of these two mixed outcomes, the output is equally likely to be \(0\) or \(1\). So each produced bit is a fair coin flip. Also, one trial succeeds with probability \[ \Pr(HT \text{ or } TH)=2p(1-p)>0, \] so eventually a fair bit is produced with probability \(1\). Repeating this procedure gives an i.i.d. sequence of fair bits \[ U_1,U_2,U_3,\dots \] using only the biased coin. Now write \(\alpha\) in binary: \[ \alpha = 0.a_1a_2a_3\cdots \] where each \(a_i \in \{0,1\}\). For dyadic rationals, choose the binary expansion that does not end in repeating \(1\)'s. For example, write \[ \frac12 = 0.1000\cdots \] rather than \[ 0.0111\cdots. \] Now interpret the fair bits \(U_1,U_2,\dots\) as the binary expansion of a random number \[ U = 0.U_1U_2U_3\cdots. \] Because the bits are i.i.d. fair, \(U\) is uniform on \([0,1]\). The game is: compare the binary digits of \(U\) and \(\alpha\) one by one. - If at the first place where they differ, we have \[ U_k < a_k, \] then Lisa wins. - If at the first place where they differ, we have \[ U_k > a_k, \] then Simon wins. - If the first \(k\) digits agree, continue. Equivalently, Lisa wins exactly when \[ U < \alpha. \] Since \(U\) is uniform on \([0,1]\), \[ \Pr(\text{Lisa wins})=\Pr(U<\alpha)=\alpha. \] That gives the required winning probability exactly. Why does the game end in finitely many tosses with probability \(1\)? The only way the comparison could continue forever is if \[ U_1=a_1,\quad U_2=a_2,\quad U_3=a_3,\ \dots \] that is, if the random fair-bit sequence exactly matches the binary expansion of \(\alpha\). But the probability of matching an infinite prescribed fair-bit sequence is \[ \prod_{n=1}^{\infty}\frac12 = 0. \] So with probability \(1\), at some finite stage a first differing digit appears, and the winner is declared. Since each fair bit is itself obtained after finitely many biased tosses with probability \(1\), the total number of biased tosses is finite with probability \(1\). So the full game is: Take the binary expansion \[ \alpha = 0.a_1a_2a_3\cdots \] (with the non-terminating-by-\(1\)'s convention). Generate fair bits \(U_1,U_2,\dots\) from the biased coin by the rule \[ HT \mapsto 0,\qquad TH \mapsto 1,\qquad HH,TT \mapsto \text{retry}. \] Compare \(U_1,U_2,\dots\) to \(a_1,a_2,\dots\) until the first index \(k\) with \(U_k \ne a_k\). - If \(U_k < a_k\), Lisa wins. - If \(U_k > a_k\), Simon wins. Then \[ \Pr(\text{Lisa wins})=\alpha, \] and the game ends after finitely many tosses with probability \(1\).