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)=1The only value of p that will simulate a fair coin is if:
H=TThis yields:
p=1−pp=12The four possibilities are HH, HT, TH, and TT.
The sum can be represented as:
p2+2p(1−p)+(1−p)2=1Note that the maximum value of p(1−p)=14 when p=12.
Coin Flips are the distinct possibilities required to achieve exactly 12.
Complement is the opposite set of coin flips with the complement of p.
Let E(p)=1−E(p)=12 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)=12 | Equation | p value |
---|---|---|---|---|
HH | HH, 2HT | p2=12 | 2p2−1=0 | p=1√2≈0.7071 |
HH, HT | Itself | p2+p(1−p)=12 | 2p−1=0 | p=12=0.5 |
HH, 2HT | HH | p=1−1√2≈0.2929 | ||
HH, TT | 2HT | p2+(1−p)2=12 | 4p2−4p+1=0 | p=12=0.5 |
2HT | HH, TT | p=12=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:
p3+3p2(1−p)+3p(1−p)2+(1−p)3=1Note that the maximum value of p2(1−p)=427 when p=23.
Note that the maximum value of p(1−p)2=427 when p=13.
Note that the maximum value of 3p2(1−p) or 3p(1−p)2 is 49.
Note that the maximum value of p2(1−p)+p(1−p)2=p(1−p)=14 when p=12.
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 | p3=12 | 2p3−1=0 | p=3√12≈0.7937 |
HHH, HHT | HHH, 3HHT, 2HTT | p3+p2(1−p)=12 | 2p2−1=0 | p=1√2≈0.7071 |
HHH, HHT, HTT | HHH, 2HHT, 2HTT | p3+p2(1−p)+p(1−p)2=12 | 2p3−2p2+2p−1=0 | p≈0.6478 |
HHH, HHT, HTT, TTT | 2HHT, 2HTT | p3+p2(1−p)+p(1−p)2+(1−p)3=12 | 4p2−4p2+1=0 | p=12=0.5 |
HHH, HHT, 2HTT | Itself | p3+p2(1−p)+2p(1−p)2=12 | 4p3−6p2+4p−1=0 | p=12=0.5 |
HHH, HHT, 3HTT | HHH, 2HTT | p≈0.2653 | ||
HHH, HHT, TTT | 3HHT, 2HTT | p3+p2(1−p)+(1−p)3=12 | 2p3−8p2+6p−1=0 | p≈0.2373 or p≈0.6846 |
HHH, 2HHT | HHH, 3HHT, HTT | p3+2p2(1−p)=12 | 2p3−4p2+1=0 | p≈0.5970 |
HHH, 2HHT, HTT | Itself | p3+2p2(1−p)+p(1−p)2=12 | p=12 | p=0.5 |
HHH, 2HHT, 2HTT | HHH, HHT, HTT | p≈0.3522 | ||
HHH, 2HHT, 3HTT | HHH, HTT | p≈0.2282 | ||
HHH, 2HHT, TTT | 3HHT, HTT | p3+2p2(1−p)+(1−p)3=12 | 4p3−10p2+6p−1=0 | p=1−1√2≈0.2929 or p=12=0.5 |
HHH, 3HHT | Itself | p3+3p2(1−p)=12 | 4p3−6p2+1=0 | p=12=0.5 |
HHH, 3HHT, HTT | HHH, 2HHT | p≈0.4030 | ||
HHH, 3HHT, 2HTT | HHH, HHT | p=1−1√2≈0.2929 | ||
HHH, 3HHT, 3HTT | HHH | p=1−3√12≈0.2063 | ||
HHH, HTT | HHH, 2HHT, 3HTT | p3+p(1−p)2=12 | 4p3−4p2+2p−1=0 | p≈0.7718 |
HHH, HTT, TTT | 2HHT, 3HTT | p3+p(1−p)2+(1−p)3=12 | 2p3+2p2−4p+1=0 | p≈0.3154 or p≈0.7627 |
HHH, 2HTT | HHH, HHT, 3HTT | p3+p2(1−p)=12 | 6p3−8p2+4p−1=0 | p≈0.7347 |
HHH, 2HTT, TTT | HHT, 3HTT | p3+2p(1−p)2+(1−p)3=12 | 4p3−2p2−2p+1=0 | p=1√2≈0.7071 or p=12=0.5 |
HHH, 3HTT | Itself | p3+3p(1−p)2=12 | 8p3−12p2+6p−1=0 | p=12=0.5 |
HHH, TTT | 3HHT, 3HTT | p3+(1−p)3=12 | 6p2−6p+1=0 | p=12+12√3≈0.7887 |
HHT, 3HTT | HHH, 2HTT, TTT | p=1−1√2≈0.2929 or p=12=0.5 | ||
2HHT, 2HTT | HHH, HHT, HTT, TTT | p=12=0.5 | ||
2HHT, 3HTT | HHH, HTT, TTT | p≈0.2373 or p≈0.6846 | ||
3HHT, HTT | HHH, 2HHT, TTT | p=1√2≈0.7071 or p=12=0.5 | ||
3HHT, 2HTT | HHH, HHT, TTT | p≈0.3154 or p≈0.7627 | ||
3HHT, 3HTT | HHH, TTT | p=12−12√3≈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 2N outcomes. The number of sets that can be created by combining those possibilities and outcomes is:
Total=N∏k=0((Nk)+1)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.