# 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

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!

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.