# 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
1 year, 2 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Are p and q both rational?

- 1 year, 2 months ago

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

- 1 year, 2 months 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$$.

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

- 1 year, 2 months 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

- 1 year, 2 months ago

That's correct.

- 1 year, 2 months 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 - 1 year, 2 months ago

The other Brilliant problem that you proposed is here!

- 10 months ago

Yup, that's the problem. Which apparently I proposed myself.

- 10 months ago