Problem 12

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Making a weighted coin

Due: January 25
Points: 3

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$$.