This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
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)\), for any constant \(p\).