Generate even odds from an unfair coin.

Additional material

[ Editor: a generalization, posted to rec.puzzles: ]

Problem: Given a coin with probability P of heads (and 1-P of tails),
         give a method of generating events of probability R that
         uses a finite number of tosses with probability one.

Most of the answer has been posted in one place or another.

   Step 1: Convert the coin to an unbiased coin by von Neumann's trick.
           Ignore HH and TT, assign HT to H and TH to T.

   Step 2: Expand R in base 2. If the first (converted) H is on
           a 1 in R, call it a success. If the first H is on a
           0, call it a failure.

New problem:  speed up the above when P is near 1 or 0. There are
              at least two non-equivalent methods.

-- Tony Warnock <ttw@beta.lanl.gov>

J R Partington <pmt6jrp@gps.leeds.ac.uk> writes:

Martin Gardner in one of his books points out that with an unfair coin
you can easily simulate a fair coin (and hence get any other probability
you like) by taking two tosses, treating ht as head, th as tail, and
ignoring hh and tt. If the coin is very lopsided this may take quite a
long time (because e.g. you might have to wait a long time for a tail.)
But is this the best way in terms of expected number of tosses?

John Tromp replies:

Not quite; here is a slightly improved procedure:

  i=n=0
  do
    parity = (i & 1)     /* & is bitwise and */
    i += toss()          /* 0 or 1 with arbitrary but fixed probability */
    n += 1
  while i & ~n == 0       /* ~ is bitwise complement */
  return parity

What this does is taking a walk through Pascal's triangle of binomial
coeficients modulo 2, which can be pictured as

                          1
                         1 1
                        1 0 1
                       1 1 1 1
                      1 0 0 0 1
                     1 1 0 0 1 1
                    1 0 1 0 1 0 1
                   1 1 1 1 1 1 1 1
                  ...

It starts at the top and steps down-left for heads and down-right for
tails.  The walk ends when it hits a zero. There were exactly two ways
of getting there, having the same number of heads and tails on the way,
but differing in their order, and in particular in the parity of heads
before the last toss.  Since these two paths have equal probability,
it's ok to take this parity as the outcome of the simulated fair coin
flip. Note that some 0s cannot be reached at all, like the 2 0s in the
6th row.

Above procedure has expected stopping time ~3.40 if there was actually
no bias in toss().

An even better procedure, that stops if the above would stop anyway
after the next toss:

  i=n=0
  do
    parity = (i & 1)     /* & is bitwise and */
    n += 1
    if (i & ~n == 0) && ((i+1) & ~n == 0)
    then return parity
    i += toss()          /* 0 or 1 with arbitrary but fixed probability */
  while (i & ~n == 0)    /* ~ is bitwise complement */
  return parity

This has expected stopping time ~3.10 if there was actually no bias in
toss(). It is conjectured to be optimal for reasonable amounts of bias.

Reference:

``Unbiased coin tossing with a biased coin'',
W. Hoeffding and G. Simons,
The Annals of Mathematical Statistics,
Vol. 41, No. 2, pp. 341--352, 1970.

-- John Tromp <tromp@cwi.nl>

In article <11331@charon.cwi.nl>, tromp@cwi.nl (John Tromp) writes:
>     if (i & ~n == 0) && ((i+1) & ~n == 0)
                  ^                    ^
I assume you mean

    if (i & ~n != 0) && ((i+1) & ~n != 0)

It's good, but not quite optimal. If you have already tossed

HHHHHHHH TTTT H

then (correct me if I'm wrong) the procedure continues

     if tossed       return
         T              1
         HT             0
         HH             1

The evidence is that H is more likely than T (as it has come up more
often) so it would be better to continue

     if tossed       return
         H              1
         TH             0
         TT             1

which saves the second toss if the first is H.

My guess is that you won't find a provably optimal strategy at all.

-- Marcus Moore <mgm10@cl.cam.ac.uk>