Which unfair coin best simulates a fair coin, when you know p?

joseph p kisenwether apmt stnt <jpk2581@hertz.njit.edu> wrote:
>If you use a coin with probability 1/sqrt(2) of coming up heads, you
>can just flip it twice, and have a 1/2 probability of getting two
>heads.

And this is optimal and unique.  Let p be the probability for heads,
q=1-p, and p>1/2 .  Let N be the expected number of flips.  If you never
get a result on the first flip, N >= 2 .  Thus tails must give a result.
If the second flip does not give a result, then N >= 1*q + 3*p >= 2 .
There are now three cases:

HH gives no result:

N >= 1*q + 2*pq + 3*p^2 = p^2 - p + 3 >= 1.75

[ Editor: 1*q + 2*pq + 3*p^2 = 1 + p + p^2, not p^2 - p + 3; for
p > 1/2 this still gives N > 1.75. ]

HT gives no result:

N >= 1*q + 2*p^2 + 3*pq = 1 + 2*p - p^2 >= 1.75

Both give results:

P(HT) <= 1/4 so the only way to make 1/2 is P(HH) .  Then
N = 1 + 1/sqrt(2) .

-- Dave Ring <Cdude@phys.tamu.edu>

karr@cs.cornell.edu (David Karr) writes:
>There was a question recently that supposed you were given an unfair
>coin (with some known probability p of turning up heads), and asked
>what protocol of flips would simulate a fair coin (produce the
>"success" outcome with probability 1/2) in the least expected number
>of flips.

Even if p is unknown, you can simulate a fair coin:

Flip the coin twice.  If the same face shows both times, make two new
flips etc. until the two faces are different.  Then let the first of the
two faces determine the result.

There is no upper limit to the number of throws, since you might throw
doubles indefinitely.  However, you can compute the average number of
throws as a function of p.

The chance of getting the result in two throws is 2*p*(1-p).  Hence the
average number of throws A = 4*p*(1-p)+(1-2*p*(1-p))*(A+2) which we
solve as A = 1/(p*(1-p)).  To minimize A, we must maximize p*(1-p),
which happens when p=0.5 giving A=4.  Since we could not choose p=0.5,
we can not get an optimal coin for this strategy.  Anyway, for known p
we might be able to find better strategies.

Someone already mentioned p=sqrt(0.5) and requiring two "head"s to get a
"yes".  While the maximum number of throws is 2, the average number of
throws is less than that, since a "tail" in the first throw decides the
issue for "no".  Hence we get A = (1-sqrt(0.5))+2*sqrt(0.5) =
1+sqrt(0.5) = 1.707...

We can try to generalize this strategy by saying that a "tail" in the
first throw generates a "no", and a "head" requires more throws, but
leaving the way this is handled open.  If we set the maximum number of
throws to be two, a simple case analysis yields no better average than
1+sqrt(0.5).  If we say that, in case of a head in first throw, two (or
more) extra throws are always needed, a simple investigation shows that
the average must be >=2.  So we are left with the cases where a head
will yield a result in one or more extra throws.  As we already have
handled the case where exactly one extra throw is needed in all cases,
we only have to consider the case where one result in the second throw
yields a final result, but the other result requires yet more throws.
By case analysis we find that the average is >=1.75.  Hence, the
solution where p=sqrt(0.5) is optimal.

-- Torben AEgidius Mogensen <torbenm@diku.dk>