# 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 years, 3 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

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?

- 2 years, 3 months ago

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

- 2 years, 3 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$.

- 2 years, 3 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.)

- 2 years, 3 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

- 2 years, 3 months ago

That's correct.

- 2 years, 3 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 - 2 years, 3 months ago

The other Brilliant problem that you proposed is here!

- 1 year, 11 months ago

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

- 1 year, 11 months ago