A simple probability puzzle • Adapting's Blog

The puzzle goes like this:

With just a fair coin, can you generate a 1/3 chance event?

Believe it or not, this puzzle actually comes from trying to address a real world application, but one that is unlike anything you would expect. You can read about it here.

There may be more, but we thought of two practical solutions.

1. The straightforward or engineering way

All we can work with is heads (H) and tails (T), but that’s actually a lot. If you think about it, all of our modern technology is based on combinations of two symbols, we call them 0 and 1, binary digits.

Let’s see how this would play out by considering some particular events.

The chance of getting H is 1/2.
The chance of getting HH is 1/4.
The chance of getting HHH is 1/8.

In summary, for any particular event made out of $k$ tosses, the probability is $\frac{1}{2^k}$ . Thus we can group up some of these events to get as close as we can to $\frac{1}{3}$ . Let’s use the letter $s$ to designate the step: $s = \frac{1}{2^k}$ ; this determines the precision, or how good our approximation can be. The maximal error we can make would be if our value of interest laid exactly in the middle of a step. Naming the error $\epsilon$ we have:

\epsilon \leq \frac{s}{2} = \frac{1}{2^{k+1}};

meaning: as we make more tosses, we will be able to make up events that get closer in probability to our target value. Let’s see some examples.

One toss. We can pick H as our event, which has probability 1/2. The error is $\epsilon = |1/2 - 1/3| = 1/6 < 1/4$ .
Two tosses. We can pick HH as our event, which has probability 1/4. The error is $\epsilon = |1/4 - 1/3| = 1/12 < 1/8$ .
Three tosses. We can pick the group made of HHH, HHT and HTH. Three events with 1/8 probability meaning the group has 3/8. The error is $\epsilon = |3/8 - 1/3| = 1/24 < 1/16$ .

To know how many events you need to group up, which we designate with $n$ , you just have to divide the target value by your step and round up:

n = \text{round}\left(\frac{1/3}{1/2^k} \right) =\text{round}\left(\frac{2^{k}}{3}\right).

For me three tosses is already good enough. The probability we get is $3/8 = 0.375$ which is reasonably close to the $1/3 = 0.33333...$ target. Note that $3/8$ is almost like $3/9$ . The next we could get would be $5/16$ which is close to $6/18$ , then $11/32$ which is close to $11/33$ . But we don’t want to be tossing coins forever, so we need to strike a balance between cost (time) and precision.

One way to proceed is to set a tolerance, $\epsilon_t$ , the maximum amount of error you are going to admit, which implies an upper bound on $\epsilon$ , and use that to workout your number of tosses.

k = \lceil \log_2 \left( \frac{1}{\epsilon_t} \right) \rceil - 1.

In my case I just thought that an error of $1/8=0.125$ (k=2) felt like too much, while $1/16=0.0625$ (k=3) felt more reasonable; and actually for the case of aiming for $1/3$ the error is, as we said, $1/24 \simeq 0.0417$ (I think I’m okay with $\epsilon < 0.05$ ). If you want more precision you can get to $k=4$ , where the error is almost $0.02$ ; at that point, it’s probably not worth it bothering with finer adjustments.

2. The precise or mathematical way

So the above works, but it always has an error, and some people, particularly mathematicians, prefer things to be exact. Can we do better? Yes!

The key is that for having a 1/3 probability, we would need 3 equally likely events, but when we toss a coin twice, we get 4. How can we get rid of one of them? Let’s say we want to get rid of TT, what we can do is, whenever TT happens, we repeat the two tosses. This means TT is no longer a possible event, because whenever we get that, we repeat the toss and replace it.

Let’s do the math. First we can see that the probability of getting TT repeatedly over $m$ attempts (each attempt is made of two tosses, $m=k/2$ ) is $\frac{1}{4^{m}}$ which (quickly) goes to 0 as $m$ grows. Thus, the probability mass of that option vanishes, and given the symmetry of the configuration, we expect that probability to distribute evenly among the remaining alternatives. Let’s check that just in case.

The probability of ending with HH was originally $1/4$ . But now, if we get a TT (which also has $1/4$ chance), we make another attempt, and thus we get another opportunity for HH, this one with $1/4 · 1/4$ chances. This occurs repeatedly so we have the following probability:

p = \frac{1}{4} + \frac{1}{4}\frac{1}{4} + \frac{1}{4^2} \frac{1}{4} + ... = \frac{1}{4} \left(1 + \frac{1}{4} + \frac{1}{4^2} + ... \right).

Recognising the part in the parenthesis as a geometric series allows us to get a result for the infinite sum:

p = \frac{1}{4} \frac{1}{1-1/4} = \frac{1}{4} \frac{1}{3/4} = \frac{1}{3}.

And there we have it.

3. Comparing the two

So we got an exact solution, with a small caveat. There’s a non-zero probability that we will be tossing coins until the end of our lives. Unless you are on your death bed, I’m willing to bet quite strongly against that happening, but still makes sense to ask, which option is more time efficient?

Let’s workout how many tosses on average we need to be exact. We have a $3/4$ chance of just needing the first $2$ , then a $1/4 · 3/4$ of needing $4$ , and it goes like that as before. The expected tosses $E[k]$ are:

\begin{align*} E[k] &= 2 · 3/4 + 4 · 1/4 · 3/4 + ... = 3/4 · \left( 1 + 1/2 + 1/4 ... \right) \\ E[k] &= 3/2 \frac{1}{1-1/2} = 3. \end{align*}

So in exchange for a little bit of uncertainty we get an exact solution with the same tosses or less than we were considering before! Mathematics tends to not disappoint.

This highlights the importance of continuing to work on problems, even when you’ve found a solution, as you never know whether there’s an even better solution lying ahead. Also, having different solutions available can be useful as the problem definition varies. If we somehow needed a more complex probability like 5/124, the mathematical approach will require an unreasonable number of tosses, while the engineering one will do just fine.