"Introduction to Algorithm" C.2-6
Describe a procedure that takes as input two integers a and b such that $0 < a < b$ and, using fair coin flips, produces as output heads with probability $a / b$ and tails with probability $(b - a) /b$. Give a bound on the expected number of coin flips, which should be O(1) (Hint: Represent a/b in binary.)
My guess is that we can use head to represent bit 0 and tail for bit 1. Then by flipping $m = \lceil \log_2 b \rceil$ times, we obtain a $m$ bit binary based number $x$. If $ x \ge b $, then we just drop x and do the experiment again, until we can an $ x < b$. This x has probility $P\{ x < a\} = \frac a b$ and $P\{ a \le x < a\} = \frac {b - a} b$
But I'm not quite sure if my solution is what the question asks. Am I right?
Edit,
I think Michael and TonyK gave the correct algorithm, but Michael explained the reason behind the algorithm.
The 3 questions he asked:
- show that this process requires c coin flips, in expectation, for some constant c;
The expectation of c, the number of flips, as TonyK pointed out, is 2.
- show that you yell "NO!" with probability 2/3;
P(yell "NO!") = P("the coin comes up tails on an odd toss") = $ \sum_{k=1}^\infty (\frac 1 2)^ k = \frac 2 3$
- explain how you'd generalize to other rational numbers, with the same constant c
It's the algorithm given by TonyK. We can restate it like this
Represent a/b in binary. Define $f(Head) = 0$, and $f(Tail) = 1$. If
f(nth flip's result) = "nth bit of a/b"
then terminate. If the last flip is Head, we yell "Yes", otherwise "No".
We have $ P \{Yes\} = \sum_{i\in I}(1/2)^i = \frac a b $ where I represent the set of index where the binary expression of a/b is 1.