The detection of words and an ordering for Markov chains

This paper considers the occurrence of patterns in sequences of independent trials from a finite alphabet; Gani and Irle (1999) have described a finite state automaton which identifies exactly those sequences of symbols containing the specific pattern, which may be thought of as the word of interest. Each word generates a particular Markov chain. Motivated by a result of Guibas and Odlyzko (1981) on stochastic monotonicity for the random times when a particular word is completed for the first time, a new level-crossing ordering is introduced for stochastic processes. A process (Y_n: n = 0, 1, …)\ is slower in level-crossing than a process (Z_n)\, if it takes (Y_n)\ stochastically longer than (Z_n)\ to exceed any given level. This relation is shown to be useful for the comparison of stochastic automata, and is used to investigate this ordering for Markov chains in discrete time.