Can You Make An Unfair Coin Fair?

Riddler Classic

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?

Solution

Case N = 1

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}$$

Case N = 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$

Case N = 3

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$

Answer

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$

Extra Credit

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.

• 'None of the outcomes' and 'all of the outcomes' will always have values of $0$ and $1$, respectively.
• As mentioned for $N = 2$ and $N = 3$ above, there will be combinations that have maximum values less than $\frac{1}{2}$.
• Any outcome with $N$ *tails* without having $N$ *heads* in the set can be excluded, as the equivalent where $N$ *heads* without having $N$ *tails* has already yielded the identical $p$.
• $0.5$ is an automatic, and often the only solution, for any set containing exactly $2^{N-1}$ out of the $2^N$ outcomes.

The upper limit seems to be safely divided by $2$ to A055612.

My guess is the answer is something like A135749.

Rohan Lewis

2020.11.09