Ch. 6. Patterns in sequences of random events

This chapter records three encounters with patterns in sequences of random events; it is not intended to be a review of the field, but concentrates rather on those areas which arose almost accidentally in the course of my research. My first encounter with the topic was through the use of tables of random numbers, while my second resulted from a study of the theory of runs. My third and most recent encounter followed some editorial work on a short note of Siegel (1997). In it, he produced a neat proof that in a sequence of length n whose elements may be 0 or 1, the number of sequences avoiding the pattern 11 was the Fibonacci number F(n + 2), a result derivable from the work of Guibas and Odlyzko (1981), and also known to Rényi (1984). Intrigued by this result, I read more widely in the field. I was eventually led to the recognition that there existed a Markov chain formulation for the case of general patterns; these arise when consecutive events from an alphabet of k letters themselves form a Markov chain.