Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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$.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.