Written by Colin+ in probability.

* 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:

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)$$

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.

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

## 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!

## icecolbeveridge

RT @icecolbeveridge: [FCM] Bringing out the big gnus: runs of coins: http://t.co/J5strGfQtM < Featuring @alexbellos’s parents and Google.

## alexbellos

@icecolbeveridge i had to ask an former IMO silver medallist to work out the probabilities….the “phone a friend” solution