A probabilistic Escher waterfall

If a fair coin is repeatedly tossed till either the sequence HHHHH or HTHHT occurs, which of the two sequences is likely to occur first? If you thought the two sequences are equally likely, you’d be wrong. The correct answer is HTHHT. A quick way to see this is that HHHHH requires five H’s to occur in succession and the occurrence of a single T destroys any progress made towards obtaining the sequence. On the other hand, for HTHHT, if after obtaining HTH, the 4th toss results in a T instead of an H, then the HT formed by the 3rd and 4th tosses can serve as the starting ‘HT’ of the same sequence.  

[Taken from:  Konold, Clifford. 1995. Confessions of a coin flipper and would-be instructor, American Statistician 49: 203–209]

One can analyze such problems graphically using state diagrams. For example, suppose we repeatedly toss a fair coin till either HHH or THH appear. Which is likely to appear first? The state transition diagram below represents the ‘race’ between the two sequences

It can be seen why THH is more likely to occur first: once the sequence gets to the state ‘T’, there is no path that leads to the state HHH.

Walter Penney, in his article in the Journal of Recreational Mathematics (October 1969, p. 241) showed a curious property of sequences of three (or more) tosses of fair coins: for any sequence of length three, one can find another sequence of length three, that has a higher probability of occurring first in repeated tosses of a fiar coin. This is fascinating, and not at all intuitive, because it leads to circular loops like the following: THH is less likely to occur before TTH (2 to 1), which is less likely than HTT (3 to 1), which is less likely than HHT (2 to 1), which is less likely than THH (3 to 1)!