Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure:

Toss the coin twice. If the results match, start over, forgetting both results. If the results differ, use the first result, forgetting the second.

Are there ways of doing this (can we tweak this procedure) to reduce the number of expected flips needed (for a realization of heads or tails)?

share|improve this question
1  
What is the expectation for von Neumann's method? Clearly it depends on the bias, and it's infinite of the coin always lands heads. –  Fixee May 18 '12 at 5:57
    
Depends. Do you know how biased the biased coin is? –  Gerry Myerson May 18 '12 at 6:02
add comment

1 Answer

up vote 7 down vote accepted

I think it depends on knowing the exact bias of the coin. For a simple example, if you know the coin comes up heads exactly one-third of the time (in the long run), then you can flip the coin twice, call it heads if you get heads once, tails if you get tails twice, do-over if you get heads twice. You get a decision 8 times out of 9, leading to a lower number of expected flips than for the von Neumann solution.

EDIT: There's a very nice discussion of the problem, especially the case where you don't know the bias of the coin, at http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf [link updated 19/07/12]

MORE EDIT: There's a fair bit of literature on this problem. Here's a sampling of what's out there:

MR0723740 (85f:60020) Stout, Quentin F.; Warren, Bette; Tree algorithms for unbiased coin tossing with a biased coin, Ann. Probab. 12 (1984), no. 1, 212–222.

MR1763468 (2001f:65009) Juels, Ari; Jakobsson, Markus; Shriver, Elizabeth; Hillyer, Bruce K.; How to turn loaded dice into fair coins, IEEE Trans. Inform. Theory 46 (2000), no. 3, 911–921. 65C10 (94A60)

MR1763481 (2001a:65006) Ryabko, Boris Ya.; Matchikina, Elena; Fast and efficient construction of an unbiased random sequence, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1090–1093. 65C10 (65C05)

MR1763482 (2001d:68177) Näslund, Mats; Russell, Alexander; Extraction of optimally unbiased bits from a biased source, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1093–1103. 68Q99

MR2245123 (2007d:94019) Cicalese, Ferdinando; Gargano, Luisa; Vaccaro, Ugo; A note on approximation of uniform distributions from variable-to-fixed length codes, IEEE Trans. Inform. Theory 52 (2006), no. 8, 3772–3777. 94A29 (94A45)

MR2300366 (2008b:65010) Pae, Sung-il; Loui, Michael C.; Randomizing functions: simulation of a discrete probability distribution using a source of unknown distribution, IEEE Trans. Inform. Theory 52 (2006), no. 11, 4965–4976. 65C10 (68W20)

share|improve this answer
    
The nice discussion you mention is indeed accessible and it provides the relevant references, among which the paper Iterating von Neumann’s Procedure by Yuval Peres in The Annals of Statistics. –  Did May 18 '12 at 6:27
    
It may be worth mentioning here that the theoretical best we can do (a lower bound on the number of flips needed), which the best solutions get closer to, is $1/H(p,q)$ flips to get each decision on average, where $p$ is the probability of heads, $q = 1-p$ is that of tails, and the entropy function $H(p,q)=p\lg\frac1p+q\lg\frac1q$ (here $\lg$ is logarithm to base $2$). For an unbiased coin, $p=q=1/2$, so $H(1/2,1/2) = 1/2\lg2+1/2\lg2=1$, which is consistent. For $p=1/3,q=2/3$, the lower bound is about $1.089$ flips per bit, and the solution in the first para achieves $9/8=1.125$ flips per bit. –  ShreevatsaR Jul 19 '12 at 10:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.