You have a coin that comes out heads with probability \(p \in (0, 1)\). But you don't need it; you need to generate an event with probability \(q \in [0, 1]\). (You know \(p, q\).) But you don't have any other source of randomness, so you have to use your coin.

You want to devise a strategy (an algorithm) that uses the coin to decide whether your event happens or not. You toss the coin; depending on that result and the previous results, you can either toss again, declare success, or declare failure.

Your strategy should declare success with probability exactly \(q\). And since you don't want to wait until the heat death of the universe, you should at least have some guarantee that this will finish.

- Prove that there exists a strategy with finite expected number of tosses.
- (open) Find the minimum expected number of tosses (by using the best strategy possible) in terms of \(p, q\).

This is inspired from another Brilliant problem (I forgot which one, though), where \(p = \frac{1}{2}, q = \frac{1}{5}\). I have a solution for part 2 for \(p = \frac{1}{2}\), but other values of \(p\), I don't know.

## Comments

Sort by:

TopNewestAre p and q both rational? – Julian Poon · 1 week, 6 days ago

Log in to reply

– Ivan Koswara · 1 week, 5 days ago

Not necessarily. In fact, my solution for \(p = \frac{1}{2}\) works no matter whether \(q\) is rational or not.Log in to reply

Algorithm: Consider a number line representing the reals from 0 to 1. On that line, place a marking on point \(q\).

Divide the line into 2 by placing a marking at \(p\). Now throw the coin. If it lands on heads, take the left section of the line. If it lands on tails, take the right section of the line:

If the section you have taken does not contain the marking on \(q\), terminate the algorithm. Otherwise, repeat the above steps by dividing the section you have taken into 2 smaller sections of length ratio \(\frac{p}{p-1}\), with the section corresponding to ratio \(p\) to the left. Thereafter, toss the coin again and follow the same rules to indicate when to terminate:

Continue this algorithm until you terminate. There is a probability \(q\) that you terminated on the left of marking \(q\) and probability \(1-q\) that you terminated on the right of marking \(q\). – Julian Poon · 1 week ago

Log in to reply

– Ivan Koswara · 1 week ago

Proving that it terminates is easy; I don't see you proving that it has a finite expected number of tosses, though. (But yes, that algorithm does terminate in finite expected number of tosses.)Log in to reply

The expected number of throws to terminate for probability \(q\) is \(\displaystyle \mathbf{E} [q]=\sum _{ n=1 }^{ \infty }{ n\prod _{ 1\le i\le n } a_{ i } } \) for some sequence \(a_{ i }\in \left\{ p,1-p \right\} \). Without loss of generality, assume \(p\le 1-p\).

For the case of \(p < 1-p\), we have that

\[\sum _{ n=1 }^{ \infty } np^{ n }\le \mathbf{E} [q]=\sum _{ n=1 }^{ \infty }{ n\prod _{ 1\le i\le n } a_{ i } } \le \sum _{ n=1 }^{ \infty } n(1-p)^{ n }\]

Since \(p, 1-p < 1\), both sides converge and we have \( \mathbf{E} [q]\) is finite.

For the case of \(p=1-p=\frac{1}{2}\), we have that

\[ \mathbf{E} [q]=\sum _{ n=1 }^{ \infty } \frac { n }{ 2^{ n } } =2\]

Hence, \( \mathbf{E} [q]\) is finite.

It's kind of amazing, how for the case of a fair coin, we can generate a probability of \(\sqrt{0.5}\) with only an expected of 2 throws – Julian Poon · 5 days, 17 hours ago

Log in to reply

– Ivan Koswara · 5 days, 10 hours ago

That's correct.Log in to reply

This is not precisely your question, but I explored a version of this question for a class years ago. Here's some of the work. – Eli Ross Staff · 1 week, 1 day ago

Log in to reply