Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin. Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin.


*

*$P(\text{H}) = p$.

*$P(\text{T}) = 1 - p = q$.


I came up with the following two-roll outcomes:


*

*$P(\text{HH}) = p^2$.

*$P(\text{HT}) = pq$. Let the event $\text{HT}$ be $A$.

*$P(\text{TH}) = qp$. Let the event $\text{TH}$ be $B$.

*$P(\text{TT}) = q^2$.


If $\text{HH}$ or $\text{TT}$ is hit we repeat the toss until $A$ or $B$. So
\begin{align}
P(A) & = pq + (p^2 + q^2)pq + (p^2 + q^2)^2pq + \ldots \\
& = pq(1 + (p^2 + q^2) + (p^2 + q^2)^2 + \ldots) \\
& = pq\left(\frac{1}{1 - (p^2 + q^2)}\right) \\
& = \frac{p(1 - p)}{2pq} = \frac{p(1 - p)}{2p(1 - p)} = \frac 12.
\end{align}
Now we want to solve for a different number other than 1/2, i.e., 1/3 or 3/4
where some solution is done in a fixed amount of N flips. How do we find a formula for this?
 A: Your solution does not have a guaranteed fixed bound $N$ on the number of biased coin flips required. The expected number of flips is finite, and the procedure runs forever with probability $0$ (so it can't happen), but for any arbitrarily large $N$ there is a small probability that your procedure will require more than $N$ flips. So if that is ok with you, then here is how you get any target probability $p_1$. You use your procedure as a subroutine so that you can get a stream of fair coin tosses. Then, for a given target probability $p_1$ that you can iteratively compute the binary expansion for, you flip your fair coin until you get heads. If it takes $N$ fair coin flips until you get heads, then you declare event $A$ if the $N$th binary digit in the expansion of $p_1$ is $1$, and you declare event $B$ if the $N$th binary digit in the expansion is $0$. This procedure has a finite expected number of flips, and the probability that you get infinitely many flips is $0$, although again, for any arbitrarily large $N$ there is a small probability that the procedure will require more than $N$ flips of your original biased coin.
