A coin can generate 1/5 chance?

Overview

The expected number of coin tosses required is 2, giving $a+b = 2+1 = \boxed{3}$ .

More surprisingly, we can replace 1/5 with any probability $p$ , rational or otherwise, that is not a dyadic fraction (has denominator that is a power of 2), and the answer is still 2. (For dyadic fractions, the answer is less than 2.)

In the following, let $p$ be the probability of success we want that is not a dyadic fraction.

---

Solution

The strategy is surprisingly simple. We do the following algorithm:

1. Assign $x \gets p$ .
2. Toss a coin and double $x$ .
3. If $x < 1$ and the result is tails, return failure (and stop the algorithm).
4. If $x \ge 1$ and the result is heads, return success (and stop the algorithm).
5. If $x \ge 1$ , subtract 1 from $x$ .
6. Go to step 2.

Note that every iteration tosses exactly one coin and exits half of the time. (On which step the iteration can potentially exit depends on $x$ , but in either case it exits when the coin tosses a certain way and repeats if it tosses the other way, so it's half chance anyway.) If $E$ is the expected number of coin tosses in this strategy, then $E = 1 + \frac{1}{2} \cdot E$ : we need one coin toss for the iteration, and half of the time we need to redo the iteration. Thus $E = 2$ ; the expected number of coin tosses is 2.

To prove that we can't do better than 2 coin tosses, notice that since $p$ is not a dyadic fraction, we cannot put an upper bound on the number of coin tosses required. (If we can say that we return a result after $n$ coin tosses, then consider the $2^n$ possible outcomes, all equally likely. Each of them is assigned to success or failure depending on its prefix. Thus the probability of getting a success is an integer divided by $2^n$ , which means the probability is a dyadic fraction, contradiction.) Thus after any number of tosses, at least one of the outcomes must require additional tosses.

After $n$ tosses, at least one of the $2^n$ outcomes must require additional tosses, which means the probability that we obtain a result in $n$ tosses is at most $\frac{2^n - 1}{2^n}$ . After 1 toss, at most 1/2 chance we manage to obtain a result. After 2 tosses, it's 3/4; this means 1/4 of the time, we need at least 2 coin tosses. After 3 tosses, it's 7/8; this means 1/8 of the time, we need at least 3 coin tosses. Repeat this ad infinitum and sum over everything, so the expected number of tosses is at least

$\displaystyle \sum_{n=1}^\infty \frac{1}{2^n} \cdot n = 2.$

Since we reach the lower bound, we know our strategy is optimal. Thus the expected number of coin tosses is $2 = \frac{2}{1}$ , giving $a = 2, b = 1, a+b = \boxed{3}$ .

---

Motivation for the strategy

First, we will show how to improve on that given strategy in the problem, as an inspiration for an optimal strategy.

Let's consider the expected number of tosses in the given strategy. If this number is $E$ , then the expectation satisfies $E = 3 + \frac{3}{8} \cdot E$ : we need 3 coin tosses, and 3/8 of the time we need to repeat it. This is how we obtain $E = \frac{24}{5}$ .

It's easy to show that from those 8 possibilities, if we pick 1 as a success, 4 as failures, and the remaining 3 to mean re-tossing, we have a 1/5 chance of success. This doesn't depend on which combinations that mean success/failure/re-toss, just how many . Thus, we can tweak things around. Let's assign all four THH, THT, TTH, TTT as failures instead. With this, we can see that a first toss of tails immediately indicates a failure, so we can actually skip the remaining two tosses.

We can try computing the same thing. This time, $E = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 3 + \frac{3}{8} \cdot E$ : half of the time we only need 1 toss (the tails), the other half of the time we need 3 tosses. The 3/8 of the time of re-toss remains the same. This gives $E = \frac{16}{5}$ , a significant improvement.

We also notice that an initial toss of HT is an immediate re-toss; we can do that, too. The equation becomes

$E = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot (2+E) + \frac{1}{8} \cdot 3 + \frac{1}{8} \cdot (3+E)$

The first term is for tails in the first toss, the second term is for two tosses HT, the third term is for HHH, the fourth term is for HHT. This gives $E = \frac{14}{5}$ . Getting pretty close, but still some way from our claim of 2. How can we improve on this?

One big problem lies on the contribution of $\frac{3}{8} E$ in the right hand side. Can we simplify it? Yes, we can, if we go further to four tosses. We have 16 possibilities; we can set 3 of them to be successes, 12 to be failures, and that leaves a single result for a re-toss. That's a probability of only 1/16 to re-toss.

To be more precise:

• An initial toss of T or HT is immediate failure. (This covers 12 cases: THHH, THHT, THTH, THTT, TTHH, TTHT, TTTH, TTTT, HTHH, HTHT, HTTH, HTTT.)
• An initial toss of HHH or HHTH is immediate success. (This covers 3 cases: HHHH, HHHT, HHTH.)
• The remaining HHTT is a re-toss.

This gives

$E = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{16} \cdot 4 + \frac{1}{16} \cdot (4+E)$

This simplifies to our desired $E = 2$ .

To the general strategy. Represent $p$ in binary. Because $p$ is not a dyadic fraction, this representation is infinite, so we don't need to care about the double representation $0.01111 \ldots _2 = 0.10000 \ldots _2$ and such. Now, our coin tosses will represent a number $q$ in binary as well, obtained bit by bit, by letting heads to be 0 and tails to be 1. Whenever we can decide with certainty that $q < p$ (success) or $q \ge p$ (failure), we immediately stop tossing and return the result.

The strategy above is actually an adaptation of this. Since $p = \frac{1}{5} = 0.001100110011 \ldots _2$ , we have:

• A starting toss of T ( $q = 0.1 \ldots _2$ ) or HT ( $q = 0.01 \ldots _2$ ) indicates that $q \ge p$ , guaranteed (since $q = \ge 0.01 _2 = \frac{1}{4} > \frac{1}{5} = p$ ), so we can immediately return failure.
• A starting toss of HHH ( $q = 0.000 \ldots _2$ ) or HHTH ( $q = 0.0010 \ldots _2$ ) indicates that $q < p$ , guaranteed (since $q < 0.0011 = \frac{3}{16} < \frac{1}{5} = p$ ), so we can immediately return success.
• A starting toss of HHTT ( $q = 0.0011 \ldots _2$ ) doesn't do anything, since we return back to the original state: T or HT after this is failure, HHH or HHTH after this is success, and HHTT is another re-toss. This indicates the fuzziness: all we know is that $0.0011_2 \le q = 0.0011 \ldots _2 < 0.01_2$ , or $\frac{3}{16} \le q < \frac{1}{4}$ . Since $\frac{1}{5}$ lies in here, we don't know if $q < p$ or $q \ge p$ .

Now, this strategy actually already works. But we can simplify it a bit to obtain the form as presented above: double the probability and take only the fractional part, to represent us going further and further right of the binary point. Now, "if the corresponding bit of $p$ is 0 but we obtain tails (1), return failure" can be rephrased as "if $p$ , after doubled, is less than 1, but we obtain tails (1), return failure", and similarly "if the corresponding bit of $p$ is 1 but we obtain heads (0), return success" can be rephrased as "if $p$ , after doubled, is not less than 1, but we obtain heads (0), return success". This gives the exact algorithm described above.