Jean Mairesse
Random walks on groups and queues
Consider a transient nearest-neighbor random walk on a plain group,
i.e. a free product of a finitely-generated free group and finitely
many finite groups.
Elements of the group can be set in bijection with a regular language L over the
alphabet of generators. The random walk can be viewed as a random
sequence of words of L, with a local dynamic affecting only one of the
extremities of the words, say the right one. We now change the model
by assuming that both extremities can be modified, the right one
according to the random walk mechanism, and the left one by
cancellation of one symbol. If the rate at which the left end gets
modified is large enough, then the model becomes a positive recurrent
Markov chain on L. First, we prove that the stationary distribution
exhibits a simple multiplicative form. Second, we show that the model
admits a very natural interpretation in terms of queueing theory. In
particular, we obtain a wide generalization of the classical theory of
`product form networks`.