×

# A coin is enough

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.

1. Prove that there exists a strategy with finite expected number of tosses.
2. (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.

Note by Ivan Koswara
2 months, 3 weeks ago

Sort by:

Are p and q both rational?

- 2 months, 2 weeks ago

Not necessarily. In fact, my solution for $$p = \frac{1}{2}$$ works no matter whether $$q$$ is rational or not.

- 2 months, 2 weeks ago

I haven't had time to think about the second part of the problem, but here's my solution to the first part:

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

- 2 months, 2 weeks 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.)

- 2 months, 2 weeks ago

Opps, I forgot that part of the solution :P

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

- 2 months, 1 week ago

That's correct.

- 2 months, 1 week ago

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.

Staff - 2 months, 2 weeks ago