Produce output with certain probability using fair coin flips

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

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