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 `i`th binary digit of the probability `p`.

Procedure: keep tossing the fair coin until we get heads, on the `k`th 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!

No comments: