Minimal Markov chain embeddings of pattern problems

The Markov chain embedding technique is commonly used to study the distribution of statistics associated with regular patterns (i.e. set of strings described by a regular expression) in random strings. In this extended abstract, we formalize the concept Markov chain embedding for random strings produced by a possibly non-stationary Markov source. A notion of memory conveyed by the states of a deterministic finite automaton is introduced. This notion is used to characterize the smallest state-space size Markov chain required to specify the distribution of the count statistic of a given regular pattern. The research finds applications in problems associated with regular patterns in random strings that demand exponentially large state spaces.