## Friday, September 04, 2015

### Simulating any biased coin with a fair coin

I recently discovered this cutie on the web.
1. Using a fair coin, you can simulate a coin with any desired bias.
2. The expected number of tosses you need to do this is just two!
Preliminaries: let's count heads as 1, tails as 0, and we'll write the desired probability of heads in our simulated biased coin as the binary fraction p = 0.p_1p_2p_3... where p_i is the ith binary digit of the probability p.

Procedure: keep tossing the fair coin until we get heads, on the kth toss.  Return p_k as the result and stop.

Proof this works: the probability of seeing a "head" (i.e., a 1) in this process is P(head) = sum_(1<=k)p_k/2^k which is exactly p by definition.

Expected number of tosses: the expected number of tosses is E(k) = sum_(1<=k)k/2^k.  Now, we can rewrite this two different ways.  One way, we can do a "change of variable" from k to k+1, giving E(k) = sum_(0<=k)(k+1)/2^(k+1).  Let's call this form, A.  Another way, we can take the original equation and add a harmless zero term to the front of the sum, giving E(k) = sum_(0<=k)k/2^k.  Let's call this form, B.  Now, since E(k) = A = B we must have
E(k) = 2A - B
qquad = 2sum_(0<=k)(k+1)/2^(k+1) - sum_(0<=k)k/2^k
qquad = sum_(0<=k)(k+1)/2^k - sum_(0<=k)k/2^k
qquad = sum_(0<=k)(k + 1 - k)/2^k
qquad = sum_(0<=k)1/2^k
qquad = 2.

I find it delightful that the expected number of tosses is independent of the target probability!