- Using a fair coin, you can simulate a coin with any desired bias.
- 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:

Post a Comment