Penney's game is a non-transitive competitive two-player coin tossing game, and a method known as Conway's algorithm provides a method for calculating the probabilities of each player winning; a description is given in Plus magazine and elsewhere. But this is not something for which I can or particularly want to remember the details.

Where I do remember the details (but seems to be less widely mentioned) is the simpler question of the expected number of tosses of a fair coin until a particular pattern appears; you might naively guess it is simply the reciprocal of the probability the pattern appears immediately and for the pattern HHHHHT this is correct, being an expected $\frac1 {2^{-6}}=64$ tosses. But for the same length pattern HHHHHH it is almost twice as high at $126$.

Here Conway's algorithm for calculating the expectation is easier to remember: you see whether the length $n$ string on the left of the pattern matches the length $n$ string on the right; if so then add $2^n$ to the result (clearly this happens at least when $n$ is the full length since the string matches itself).

So for example

• HHHHHH has $2^1+2^2+2^3+2^4+2^5+2^6=126$ expected tosses because everything matches
• HHHHHT has $2^6=64$ expected tosses because only the full length matches
• HHTHHH has $2^1+2^2+2^6=70$ expected tosses (the matches are H, HH and HHTHHH)
• HHTHHT has $2^3+2^6=72$ expected tosses (the matches are HHT and HHTHHT).

For me the nice part of this is that it does not have to involve coins. Dice work too by changing $2^n$ to $6^n$. So throwing the pattern $1\, 1\, 5\, 1\, 1\, 5$ has an expected number of $6^3+6^6=46872$ throws until the pattern appears. Neat and easy.