Steve Lalley: Random Walks on Regular Languages and Algebraic Systems of Generating Functions

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:

(1).

Only the last two letters of a word may be modified in one jump, and at most one letter may be adjoined or deleted.

(2).

Probabilities of modification, deletion, and/or adjunction depend only on the last two letters of the current word.

Special cases include

(a).

reflecting random walks on the nonnegative integers

(b).

LIFO queues

(c).

finite-range random walks on homogeneous trees, and

(d).

random walks on the modular group.

It will be shown that the $n$-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