A coin is enough

You have a coin that comes out heads with probability p(0,1)p \in (0, 1). But you don't need it; you need to generate an event with probability q[0,1]q \in [0, 1]. (You know p,qp, 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 qq. 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,qp, q.

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

Note by Ivan Koswara
2 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Are p and q both rational?

Julian Poon - 2 years, 3 months ago

Log in to reply

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

Ivan Koswara - 2 years, 3 months ago

Log in to reply

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

Divide the line into 2 by placing a marking at pp. 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 qq, terminate the algorithm. Otherwise, repeat the above steps by dividing the section you have taken into 2 smaller sections of length ratio pp1\frac{p}{p-1}, with the section corresponding to ratio pp 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 qq that you terminated on the left of marking qq and probability 1q1-q that you terminated on the right of marking qq.

Julian Poon - 2 years, 3 months ago

Log in to reply

@Julian Poon 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.)

Ivan Koswara - 2 years, 3 months ago

Log in to reply

@Ivan Koswara Opps, I forgot that part of the solution :P

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

For the case of p<1pp < 1-p, we have that

n=1npnE[q]=n=1n1inain=1n(1p)n\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,1p<1p, 1-p < 1, both sides converge and we have E[q] \mathbf{E} [q] is finite.

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

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

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

It's kind of amazing, how for the case of a fair coin, we can generate a probability of 0.5\sqrt{0.5} with only an expected of 2 throws

Julian Poon - 2 years, 3 months ago

Log in to reply

@Julian Poon That's correct.

Ivan Koswara - 2 years, 3 months ago

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

Log in to reply

The other Brilliant problem that you proposed is here!

Plinio SD - 1 year, 11 months ago

Log in to reply

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

Ivan Koswara - 1 year, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...