# Produce output with certain probability using fair coin flips

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

• I am certain your idea is correct. But do your $m$-bit numbers start from $0$ or $1$? I am just checking trivial things like $b$ or $b+1$, $>$ or $\geq$, and so on... – Srivatsan Sep 9 '11 at 22:25
• Oh in my mind m starts from 1. Also, if my solution is correct, then the expected number of flips is $\frac {m \times 2 ^ m} b$ – ablmf Sep 9 '11 at 22:29
• Yes, I was coming to that. Let me assume that you can take care of the indices correctly. There is a more fundamental worry actually. In the expected number of flips, the $b$ term is between $2^{m-1}$ and $2^m$, so that the $2^m/b$ factor is always between $1$ and $2$. So the expected number of flips is between $m$ and $2m$. Alas, that is not $O(1)$. By $O(1)$, the question wants you to find a method that will make expected $c$ tosses for some absolute constant $c$. (To be concrete, let's say $c$ is like 100, or something like that. $c$ cannot be $\log b$ though.) – Srivatsan Sep 9 '11 at 22:35
• That wasn't too helpful maybe. But imagine this special case: $a = 1$, $b = 2^m$. So, your algorithm will toss $m$ coins. It will declare 0 if all the coins turn up heads. If at least one coin turns up tails, it declares 1. But should you necessarily toss all the $m$ coins all at once? Is there a more sensible thing to do? Can I maybe toss one coin at a time, and hope to get a better bound? – Srivatsan Sep 9 '11 at 22:43

Express $a/b$ in binary. Then at the $n$th throw, continue if the throw matches bit $n$ of $a/b$; otherwise terminate, with outcome "heads" if the $n$th throw was $0$ and "tails" if the $n$th throw was $1$.

At each throw, the probability of terminating is $1/2$. So the expected number of throws is $$\sum_{r=1}^\infty \frac{r}{2^r} = 2$$ We can do a bit better if the binary expansion terminates, because we can halt the procedure after the last non-zero bit (the probability of subsequently throwing an infinite sequence of zeroes is $0$).

• Or you could continue if the $n^{\rm th}$ throw doesn't match, then call "heads" if the throw was $1$ and "tails" if the throw was $0$. – robjohn Sep 9 '11 at 23:58
• If the expansion were finite, you could also terminate with $011111\dots$ instead of $100000\dots$ – robjohn Sep 10 '11 at 0:00

The simplest nontrivial case is $a = 1, b = 3$ -- so we want to flip fair coins, observe whether they come up heads or tails, and at some point yell out "YES!" or "NO!". We want to yell out "YES!" with probability $1/3$, and we want this to terminate in an amount of time which has finite expectation.

So say that we get a tail on the first toss. Then we will yell out "NO!"; this means that half the time we yell "NO!" after one flip. Half the time we have not yet said anything; in two-thirds of this one-half of the time we want to yell out "YES!", and the rest of the time we want to yell out "NO!"

So if we get (a tail on the first toss and) a head on the second toss we want to yell out "YES!". Now we've yelled "NO!" in one toss with probability $1/2$, and "YES!" in two tosses $1/4$ of the time. To get one-third "YES!" we have to yell "YES!" $1/3$ of the remaining $1/4$ of the time.

But we already know how to do that... yell out "NO!" if the coin comes up tails on the third toss, "YES!" if it comes up heads on the fourth toss, and so on.

So in this case you flip the coins repeatedly, and wait until the coin comes up tails on an odd toss -- in which case you yell "NO!" -- or heads on an even toss -- in which case you yell "YES!". I leave it to you to:

• show that this process requires $c$ coin flips, in expectation, for some constant $c$;
• show that you yell "NO!" with probability $2/3$;
• explain how you'd generalize to other rational numbers, with the same constant $c$.

Here is my thought of understanding Michael and TonyK's solutions.

• $0 \lt a \lt b$, which means $0 \lt {\frac ab} \lt 1$, so $\frac ab$ can be represent by infinite binary fraction with form $0.b_1b_2...b_{j-1}b_jb_{j+1}b_{j+2}$(adds trailing $0$s, when $\frac ab$ is finite binary fraction). flipping a coin infinite times can represent binary fraction between $0$ and $1$, as $0.{flip_1}{flip_2}...{flip_i}...$, one by one correspondingly. Now, the probability of the flipping fraction $0.{flip_1}{flip_2}...{flip_i}...$ less than fraction $\frac ab$ is $\frac ab$, and greater than fraction $\frac ab$ is $\frac {b-a} {b}$ , for continuous uniform probability distribution.
• However, flipping a coin infinite times is impossible and what we want is the relation whether that infinite string $0.{flip_1}{flip_2}...{flip_i}...$ is less or greater than $\frac ab$. we can predict the less or greater than relation when the first unmatched throw occurred , because any $0.b_1b_2...b_{j-1}\mathbf0x_{j+1}x_{j+2}...$ is less than $0.b_1b_2...b_{j-1}\mathbf1b_{j+1}b_{j+2}...$ when $b_j = 1$ and any $0.b_1b_2...b_{j-1}\mathbf1x_{j+1}x_{j+2}...$ is greater than $0.b_1b_2...b_{j-1}\mathbf0b_{j+1}b_{j+2}....$ when $b_j = 0$.

Basically, what Michael says is it like this:

We express a/b using say 64 binary digits.

Now, flip 64 coins. Represent the outcome of this as a binary using head=1 and tail=0.

The best approximation of the problem is:

• If this number is larger than the 64 bit binary representation of a/b then say "HEADS".
• If this number is smaller than the 64 bit binary representation of a/b then say "TAILS".

Hope I am right.