Processing math: 100%

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+(1p)=1

The only value of p that will simulate a fair coin is if:

H=T

This yields:

p=1pp=12

Case N = 2

The four possibilities are HH, HT, TH, and TT.

The sum can be represented as:

p2+2p(1p)+(1p)2=1

Note that the maximum value of p(1p)=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)=1E(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 2p21=0 p=120.7071
HH, HT Itself p2+p(1p)=12 2p1=0 p=12=0.5
HH, 2HT HH p=1120.2929
HH, TT 2HT p2+(1p)2=12 4p24p+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

Case N = 3

The eight possibilities are HHH, HHT, HTH, HTT, THH, THT, TTH, and TTT.

The sum can be represented as:

p3+3p2(1p)+3p(1p)2+(1p)3=1

Note that the maximum value of p2(1p)=427 when p=23.

Note that the maximum value of p(1p)2=427 when p=13.

Note that the maximum value of 3p2(1p) or 3p(1p)2 is 49.

Note that the maximum value of p2(1p)+p(1p)2=p(1p)=14 when p=12.

The chart below summarizes the values that simulate a fair coin:

Coin Flips Complement of... E(p)=1E(p) Equation p value
HHH HHH, 3HHT, 3HTT p3=12 2p31=0 p=3120.7937
HHH, HHT HHH, 3HHT, 2HTT p3+p2(1p)=12 2p21=0 p=120.7071
HHH, HHT, HTT HHH, 2HHT, 2HTT p3+p2(1p)+p(1p)2=12 2p32p2+2p1=0 p0.6478
HHH, HHT, HTT, TTT 2HHT, 2HTT p3+p2(1p)+p(1p)2+(1p)3=12 4p24p2+1=0 p=12=0.5
HHH, HHT, 2HTT Itself p3+p2(1p)+2p(1p)2=12 4p36p2+4p1=0 p=12=0.5
HHH, HHT, 3HTT HHH, 2HTT p0.2653
HHH, HHT, TTT 3HHT, 2HTT p3+p2(1p)+(1p)3=12 2p38p2+6p1=0 p0.2373 or p0.6846
HHH, 2HHT HHH, 3HHT, HTT p3+2p2(1p)=12 2p34p2+1=0 p0.5970
HHH, 2HHT, HTT Itself p3+2p2(1p)+p(1p)2=12 p=12 p=0.5
HHH, 2HHT, 2HTT HHH, HHT, HTT p0.3522
HHH, 2HHT, 3HTT HHH, HTT p0.2282
HHH, 2HHT, TTT 3HHT, HTT p3+2p2(1p)+(1p)3=12 4p310p2+6p1=0 p=1120.2929 or p=12=0.5
HHH, 3HHT Itself p3+3p2(1p)=12 4p36p2+1=0 p=12=0.5
HHH, 3HHT, HTT HHH, 2HHT p0.4030
HHH, 3HHT, 2HTT HHH, HHT p=1120.2929
HHH, 3HHT, 3HTT HHH p=13120.2063
HHH, HTT HHH, 2HHT, 3HTT p3+p(1p)2=12 4p34p2+2p1=0 p0.7718
HHH, HTT, TTT 2HHT, 3HTT p3+p(1p)2+(1p)3=12 2p3+2p24p+1=0 p0.3154 or p0.7627
HHH, 2HTT HHH, HHT, 3HTT p3+p2(1p)=12 6p38p2+4p1=0 p0.7347
HHH, 2HTT, TTT HHT, 3HTT p3+2p(1p)2+(1p)3=12 4p32p22p+1=0 p=120.7071 or p=12=0.5
HHH, 3HTT Itself p3+3p(1p)2=12 8p312p2+6p1=0 p=12=0.5
HHH, TTT 3HHT, 3HTT p3+(1p)3=12 6p26p+1=0 p=12+1230.7887
HHT, 3HTT HHH, 2HTT, TTT p=1120.2929 or p=12=0.5
2HHT, 2HTT HHH, HHT, HTT, TTT p=12=0.5
2HHT, 3HTT HHH, HTT, TTT p0.2373 or p0.6846
3HHT, HTT HHH, 2HHT, TTT p=120.7071 or p=12=0.5
3HHT, 2HTT HHH, HHT, TTT p0.3154 or p0.7627
3HHT, 3HTT HHH, TTT p=121230.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 2N outcomes. The number of sets that can be created by combining those possibilities and outcomes is:

Total=Nk=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.

  • '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 12.
  • 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 2N1 out of the 2N 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