* Thanks to Barney Maunder-Taylor for the problem

In Alex’s Adventures In Numberland, the author - Alex Bellos - makes a big production of getting one of his parents to pretend to toss a coin 20 times and the other to actually do it, then tell which one is which. His secret ((hardly a secret, though, is it; it’s in one of the biggest selling maths books around)) ? People don’t put enough runs of coins in their pretend results. If you toss 20 coins, you’re much more likely than not - about 77% - to have a run of at least four heads or four tails.

So, naturally, Barney wanted to know:

How do you work that out?

The answer: with some difficulty, if you’re me. I didn’t see an immediate statistical way in to the problem, and I’d never hear the last of it if I ran simulations. So I turned to recurrence relations, with preposterous definitions like $p_k = \frac{1}{8} + \frac{1}{8}p_{k+3} + \frac{1}{4}p_{k+2} + \frac{1}{2}p_{k+1}$, with $p_1 = p_2 = p_3 = 0$. In honesty, I’m not sure if that’s even right, let alone how to solve it.

The answer came, as many answers do, when I started doodling. A load of numbers with arrows between them. 1 pointed to 1 and 2. 2 pointed to 1 and 3. 3 pointed to 1 and 4. 4 pointed to… well, only 4 - because you’ve won, hooray, you don’t want to stop winning once you’ve won.

You can draw this as a transition matrix. If only someone had a more practical use for transition matrices than this! If you’ve got a transition matrix, you can turn to Octave or Matlab or your computer language of choice, and have it do the heavy lifting.

Here’s the transition matrix: \(A = \left( \begin{array}{cccc} 0.5 & 0.5 & 0.5 & 0 \\ 0.5 & 0 & 0 & 0 \\ 0 & 0.5 & 0 & 0 \\ 0 & 0 & 0.5 & 1 \end{array} \right)\)

Each column is a starting point on the doodle, and each row is a finishing point: for instance, in the first column, starting from 1 (say, a run of one head), I have a 50-50 chance of increasing that to two heads or starting a new run of one tail. In the third column, I’ve got a 50-50 chance of turning my run of three heads into a run of four or a new run of one tail. And in the final row, I’ve got my run of four and I stop, happy.

I also came up with an initial probability matrix - after my first throw, I’m guaranteed to have a run of one, so my initial probabilities are: \(p_0 = \begin{pmatrix}{c} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}\)

Over and over and over

Then all I need to do is multiply the matrix by this repeatedly! $A\cdot p$ gives me the probabilities after my second throw (hey, what do you know? a 50-50 chance of having a run of one or two!). $A^2 \cdot p$ gives me the probabilities after the third throw. And, for the health of Alex Bellos’s parents: \(A^{19}\cdot p = \left( \begin{array}{c} 0.126 \\ 0.068 \\ 0.037 \\ 0.768 \end{array} \right)\)

It’s possible to extend this method to as many throws (and as long runs) as you want - although you may need a bigger matrix. It’s easy to set up, though: the first row is all 0.5 except for the last element; the entries just below the diagonal are all 0.5 as well; and the bottom-right entry is 1.

It turns out, for instance, that if you toss a million coins, you’ve got a 61% chance of throwing at least one run of 20 or more.

Is there a less computer-intensive way of figuring out the problem? I’d love to know.

  • Edited 2021-06-04 to fix LaTeX. Thanks, Adam!