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.

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