Bringing out the big gnus: runs of coins

* 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 secret1 ? 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 = \left(
\begin{array} {c}
1 \\
0 \\
0 \\
0 \end{array} \right)$$

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.


Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. hardly a secret, though, is it; it's in one of the biggest selling maths books around []


6 comments on “Bringing out the big gnus: runs of coins

  • Nathan "Spanky" Briggs

    Dunno about less intensive, but I would’ve gotten the nearest comp sci nerd to run some Monte Carlos

    • Colin

      It was my instinct, too – but I risked the wrath of the mathematical circle by even firing up Octave!

  • barney

    Well done Colin I’m happy to go on record as being officially impressed. To be honest I had no idea matrices could be applied to this sort of problem – and so elegantly too. Your solution trumps computer simulation by a mile. Fake or fiction: THTTTTHTTHTTHHHTHTHH

    • Colin

      My instinct is that it fits a little too neatly into the expected runs and that you’ve made it up to try to trick me. Everyone says I’m paranoid!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter