Random walks on regular languages and algebraic systems of generating functions
Steven P. Lalley · Contemporary mathematics - American Mathematical Society · 2001
Abstract. A random walk on a regular language is a Markov chain on the set of all finite words from a finite alphabet A 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 P SL2(Z). It is shown that the n−step transition probabilities of a random walk on a regular language must obey one of three different types of power laws. The analysis is based on the study of an algebraic system of generating functions related to the Green’s function. 1.