A random walk on a regular language is a Markov chain on the set of all finite words from a finite alphabet whose transition probabilities obey the following rules:
It will be shown that the -step transition probabilities of such a process must obey one of 3 distinct types of asymptotic behavior. This will be accomplished by the analysis of an algebraic system of generating functions related to the Green's function of the random walk. Possible extensions of the main theorem to Markov chains whose Green's functions are not algebraic will be discussed, along with connections to other combinatorial problems of interest in theoretical computer science.
Back to the Index