Posts Tagged ‘coin flips’

Coin Perfection

Saturday, March 28th, 2009

Say you want to flip a perfect coin, but the only coins available are imperfect. First, let’s consider the case where we don’t know the details of the available coins, and would prefer not to measure them.

The simplest strategy is to flip a bunch of coins and determine whether the total number of heads is even or odd. As long as there’s a reasonable number of both heads and tails, the probability of an even number of heads will be close to one half.

Here is a measure of “coin perfection” which behaves additively with respect to the parity algorithm:

G(p)=log|2p1|

I.e., if you have two coins with probabilities of heads p and q, and r is the probability that flipping both coins gives the same result, then

G(r)=G(p)+G(r)

since e G(r) =|2r1| =|2(pq+(1p)(1q))1| =|2pq+22p2q+2pq1| =|4pq2p2q+1| =|(2p1)(2q1)| =e G(p)e G(q)

In particular, G(0)=G(1)=0 and G(1/2)= as one would expect; flipping a deterministic coin gets you no closer to perfection, and flipping a single perfect coin makes the parity perfectly random regardless of the other coins.

If we know the exact probability of heads p, we can do better than this and produce a perfect coin in a finite expected number of flips. By information theory the best we can hope for is 1/H(p) where

H(p)=plgp(1p)lg(1p)

is the entropy of the coin. Unfortunately determining the exact minimum appears rather complicated, so I’m not going to try to finish the analysis right now.