13
$\begingroup$

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)?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Fixee
    May 18, 2012 at 5:57
  • $\begingroup$ Depends. Do you know how biased the biased coin is? $\endgroup$
    – Gerry Myerson
    May 18, 2012 at 6:02
  • 1
    $\begingroup$ Somewhat tangentially, the big problem with Neumann-style debiasers is that they assume the coin tosses to be independent. In the real world, biased randomness sources are often also autocorrelated, and it's possible for a Neumann debiaser to actually make such a source more biased. $\endgroup$
    – Ilmari Karonen
    Feb 3, 2015 at 17:34

2 Answers 2

Reset to default
14
$\begingroup$

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)

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Did
    May 18, 2012 at 6:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – ShreevatsaR
    Jul 19, 2012 at 10:42
2
$\begingroup$

Yes.

If the coin has a bias $0<p<1$ then the information you get from tossing the coin is

$$ \operatorname{E}(p):=-p\log_2(p) - (1-p)\log_2(1-p). $$

For each coin toss as input you receive $\operatorname{E}(p)$ entropy but only return on average $p(1-p)$ entropy in the output so you must be losing something.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .