This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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.