Improving Von Neumann's Unfair Coin Solution

Solution 1:

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)

Solution 2:

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.