The expected number of runs in a word
Simon J. Puglisi, Jamie Simpson · 2008
A word is a sequence of symbols taken from a (usually finite) alphabet. A run of period p in a word x is a factor x[m..n] such that n-m ≤ p and x[i] = x[i+p] for all i satisfying m ≤ i < i+p ≤ n, and such that this does not hold if m is replaced by a smaller integer or n by a larger one. The number of runs in words has been a subject of interest in recent years, particularly because of connections with data compression. In this paper we investigate the expected number of runs per unit length in words of given alphabet size, and compare our results with DNA, amino acid and other sequences.