Mathematician John von Neumann is credited with figuring out how to take a biased coin (whose probability of coming up heads is $p$, not necessarily equal to $0.5$) and “simulate” a fair coin. Simply flip the coin twice. If it comes up heads both times or tails both times, then flip it twice again. Eventually, you’ll get two different flips — either a heads and then a tails, or a tails and then a heads, with each of these two cases equally likely. Once you get two different flips, you can call the second of those flips the outcome of your “simulation.”
For any value of $p$ between zero and one, this procedure will always return heads half the time and tails half the time. This is pretty remarkable! But there’s a downside to von Neumann’s approach — you don’t know how long (i.e., how many flips) the simulation will last.
Suppose I want to simulate a fair coin in at most three flips. For which values of $p$ is this possible?
Extra credit: Suppose I want to simulate a fair coin in at most $N$ flips. For how many values of $p$ is this possible?
The only two possibilities are $H$ and $T$.
The sum can be represented as:
$$p + (1-p) = 1$$The only value of $p$ that will simulate a fair coin is if:
$$H = T$$This yields:
$$p = 1-p$$$$p = \frac{1}{2}$$The four possibilities are $HH$, $HT$, $TH$, and $TT$.
The sum can be represented as:
$$p^2 + 2p(1-p) + (1-p)^2 = 1$$Note that the maximum value of $p(1-p) = \frac{1}{4}$ when $p = \frac{1}{2}$.
Coin Flips are the distinct possibilities required to achieve exactly $\frac{1}{2}$.
Complement is the opposite set of coin flips with the complement of $p$.
Let $E(p) = 1 - E(p) = \frac{1}{2}$ represent how the two coin tosses simulate a fair coin.
The chart below summarizes the values that simulate a fair coin:
| Coin Flips | Complement of... | $E(p) = \frac{1}{2}$ | Equation | $p$ value |
|---|---|---|---|---|
| $HH$ | $HH$, $2HT$ | $p^2 = \frac{1}{2}$ | $2p^2 - 1 = 0$ | $p = \frac{1}{\sqrt{2}} \approx 0.7071$ |
| $HH$, $HT$ | Itself | $p^2 + p(1-p) = \frac{1}{2}$ | $2p - 1 = 0$ | $p = \frac{1}{2} = 0.5$ |
| $HH$, $2HT$ | $HH$ | $p = 1 - \frac{1}{\sqrt{2}}\approx 0.2929$ | ||
| $HH$, $TT$ | $2HT$ | $p^2 + (1-p)^2 = \frac{1}{2}$ | $4p^2 - 4p + 1 = 0$ | $p = \frac{1}{2} = 0.5$ |
| $2HT$ | $HH$, $TT$ | $p = \frac{1}{2} = 0.5$ |
For $N = 2$, there are $3$ solutions:
$0.2929$ $0.5$ $0.7071$
The eight possibilities are $HHH$, $HHT$, $HTH$, $HTT$, $THH$, $THT$, $TTH$, and $TTT$.
The sum can be represented as:
$$p^3 + 3p^2(1-p) + 3p(1-p)^2 + (1-p)^3 = 1$$Note that the maximum value of $p^2(1-p) = \frac{4}{27}$ when $p = \frac{2}{3}$.
Note that the maximum value of $p(1-p)^2 = \frac{4}{27}$ when $p = \frac{1}{3}$.
Note that the maximum value of $3p^2(1-p)$ or $3p(1-p)^2$ is $\frac{4}{9}$.
Note that the maximum value of $p^2(1-p) + p(1-p)^2 = p(1-p)= \frac{1}{4}$ when $p = \frac{1}{2}$.
The chart below summarizes the values that simulate a fair coin:
| Coin Flips | Complement of... | $E(p) = 1 - E(p)$ | Equation | $p$ value |
|---|---|---|---|---|
| $HHH$ | $HHH$, $3HHT$, $3HTT$ | $p^3 = \frac{1}{2}$ | $2p^3 - 1 = 0$ | $p = \sqrt[3]{\frac{1}{2}} \approx 0.7937$ |
| $HHH$, $HHT$ | $HHH$, $3HHT$, $2HTT$ | $p^3 + p^2(1-p) = \frac{1}{2}$ | $2p^2 - 1 = 0$ | $p = \frac{1}{\sqrt{2}} \approx 0.7071$ |
| $HHH$, $HHT$, $HTT$ | $HHH$, $2HHT$, $2HTT$ | $p^3 + p^2(1-p) + p(1-p)^2 = \frac{1}{2}$ | $2p^3 - 2p^2 + 2p - 1 = 0$ | $p \approx 0.6478$ |
| $HHH$, $HHT$, $HTT$, $TTT$ | $2HHT$, $2HTT$ | $p^3 + p^2(1-p) + p(1-p)^2 + (1-p)^3 = \frac{1}{2}$ | $4p^2 - 4p^2 + 1 = 0$ | $p = \frac{1}{2} = 0.5$ |
| $HHH$, $HHT$, $2HTT$ | Itself | $p^3 + p^2(1-p) + 2p(1-p)^2 = \frac{1}{2}$ | $4p^3 - 6p^2 + 4p - 1 = 0$ | $p = \frac{1}{2} = 0.5$ |
| $HHH$, $HHT$, $3HTT$ | $HHH$, $2HTT$ | $p \approx 0.2653$ | ||
| $HHH$, $HHT$, $TTT$ | $3HHT$, $2HTT$ | $p^3 + p^2(1-p) + (1-p)^3 = \frac{1}{2}$ | $2p^3 - 8p^2 + 6p - 1 = 0$ | $p \approx 0.2373$ or $p \approx 0.6846$ |
| $HHH$, $2HHT$ | $HHH$, $3HHT$, $HTT$ | $p^3 + 2p^2(1-p) = \frac{1}{2}$ | $2p^3 - 4p^2 + 1 = 0$ | $p \approx 0.5970$ |
| $HHH$, $2HHT$, $HTT$ | Itself | $p^3 + 2p^2(1-p) + p(1-p)^2 = \frac{1}{2}$ | $p = \frac{1}{2}$ | $p = 0.5$ |
| $HHH$, $2HHT$, $2HTT$ | $HHH$, $HHT$, $HTT$ | $p \approx 0.3522$ | ||
| $HHH$, $2HHT$, $3HTT$ | $HHH$, $HTT$ | $p \approx 0.2282$ | ||
| $HHH$, $2HHT$, $TTT$ | $3HHT$, $HTT$ | $p^3 + 2p^2(1-p) + (1-p)^3 = \frac{1}{2}$ | $4p^3 - 10p^2 + 6p - 1 = 0$ | $p = 1 - \frac{1}{\sqrt{2}} \approx 0.2929$ or $p = \frac{1}{2} = 0.5$ |
| $HHH$, $3HHT$ | Itself | $p^3 + 3p^2(1-p) = \frac{1}{2}$ | $4p^3 - 6p^2 + 1 = 0$ | $p = \frac{1}{2} = 0.5$ |
| $HHH$, $3HHT$, $HTT$ | $HHH$, $2HHT$ | $p \approx 0.4030$ | ||
| $HHH$, $3HHT$, $2HTT$ | $HHH$, $HHT$ | $p = 1 - \frac{1}{\sqrt{2}} \approx 0.2929$ | ||
| $HHH$, $3HHT$, $3HTT$ | $HHH$ | $p = 1 - \sqrt[3]{\frac{1}{2}} \approx 0.2063$ | ||
| $HHH$, $HTT$ | $HHH$, $2HHT$, $3HTT$ | $p^3 + p(1-p)^2 = \frac{1}{2}$ | $4p^3 - 4p^2 + 2p - 1 = 0$ | $p \approx 0.7718$ |
| $HHH$, $HTT$, $TTT$ | $2HHT$, $3HTT$ | $p^3 + p(1-p)^2 + (1-p)^3 = \frac{1}{2}$ | $2p^3 +2p^2 - 4p + 1 = 0$ | $p \approx 0.3154$ or $p \approx 0.7627$ |
| $HHH$, $2HTT$ | $HHH$, $HHT$, $3HTT$ | $p^3 + p^2(1-p) = \frac{1}{2}$ | $6p^3 - 8p^2 + 4p - 1 = 0$ | $p \approx 0.7347$ |
| $HHH$, $2HTT$, $TTT$ | $HHT$, $3HTT$ | $p^3 + 2p(1-p)^2 + (1-p)^3= \frac{1}{2}$ | $4p^3 - 2p^2 - 2p + 1 = 0$ | $p = \frac{1}{\sqrt{2}} \approx 0.7071$ or $p = \frac{1}{2} = 0.5$ |
| $HHH$, $3HTT$ | Itself | $p^3 + 3p(1-p)^2 = \frac{1}{2}$ | $8p^3 - 12p^2 + 6p - 1 = 0$ | $p = \frac{1}{2} = 0.5$ |
| $HHH$, $TTT$ | $3HHT$, $3HTT$ | $p^3 + (1-p)^3 = \frac{1}{2}$ | $6p^2 - 6p + 1 = 0$ | $p = \frac{1}{2} + \frac{1}{2\sqrt{3}} \approx 0.7887$ |
| $HHT$, $3HTT$ | $HHH$, $2HTT$, $TTT$ | $p = 1 - \frac{1}{\sqrt{2}} \approx 0.2929$ or $p = \frac{1}{2} = 0.5$ | ||
| $2HHT$, $2HTT$ | $HHH$, $HHT$, $HTT$, $TTT$ | $p = \frac{1}{2} = 0.5$ | ||
| $2HHT$, $3HTT$ | $HHH$, $HTT$, $TTT$ | $p \approx 0.2373$ or $p \approx 0.6846$ | ||
| $3HHT$, $HTT$ | $HHH$, $2HHT$, $TTT$ | $p = \frac{1}{\sqrt{2}} \approx 0.7071$ or $p = \frac{1}{2} = 0.5$ | ||
| $3HHT$, $2HTT$ | $HHH$, $HHT$, $TTT$ | $p \approx 0.3154$ or $p \approx 0.7627$ | ||
| $3HHT$, $3HTT$ | $HHH$, $TTT$ | $p = \frac{1}{2} - \frac{1}{2\sqrt{3}} \approx 0.2113$ |
For $N = 3$, there are $19$ solutions:
$0.2063$ $0.2113$ $0.2282$ $0.2373$ $0.2653$ $0.2929$
$0.3154$ $0.3522$ $0.4030$ $0.5$ $0.5970$ $0.6478$ $0.6846$
$0.7071$ $0.7347$ $0.7627$ $0.7718$ $0.7887$ $0.7937$
Thus far we have:
| $N$ | Number of $p$ |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 19 |
For $N$ coin flips, there are $N+1$ possiblities for $2^N$ outcomes. The number of sets that can be created by combining those possibilities and outcomes is:
$$Total = \prod_{k = 0}^{N} \bigg({N \choose k} + 1\bigg)$$This is by definition A129824, which is a safe upper limit for the answer. However, not all yield viable solutions to simulate a fair coin. Here are some exclusions.
The upper limit seems to be safely divided by $2$ to A055612.
My guess is the answer is something like A135749.