# Problem 20

# Making a weighted coin

**Due**: February 2

**Points**: 2

Given a perfectly fair coin (heads or tails each with probability exactly \(\frac{1}{2}\)), and a probability \(p\) with \(0\le p\le 1\), give an algorithm to simulate the tossing of the *weighted* coin that comes up heads with probability \(p\) and tails with probability \(1-p\).

Specifically, assume that you are given the *infinite binary expansion* of \(p\). In other words, assume \(p\) is written in base 2 as

\[p = 0.b_1b_2b_3b_4\ldots\]

where each \(b_i\) is either 0 or 1. Your algorithm can examine as many of the bits in this binary expansion of \(p\) as it needs, in order. Of course, examining more bits will make your algorithm slower, and there are potentially an infinite number of bits in the expansion of \(p\), so you can't examine all of them!

Show that the *expected number* of fair coin flips your algorithm requires is \(O(1)\), no matter what \(p\) is.