ABSTRACT RANDOM WALKS ON FINITE FIELDS AND HEISENBERG GROUPS

Let H be a finite group and µ a probability measure on H. This data determines an invariant random walk on H beginning from the identity element. The probabil-ity distribution for the state of the random walk after n steps is given by the n’th convolution power of the probability measure µ. The random walk and measure µ are said to be ergodic if the support of this distribution is the entire group for n suf-ficiently large. In this case a specialization of the Markov Ergodic Theorem ensures that the distribution after n steps converges point-wise to the uniform distribution. One employs the total variation distance on probability measures to analyze the rate of convergence to equilibrium. Suppose now that a finite group K acts on H by automorphisms. We say that the action pair K: H is ergodic when the K-invariant probability measure µ supported on some K-orbit is ergodic. We call, moreover, K: H a Gelfand action pair when the convolution algebra of K-invariant functions on H is commutative. Specializing the theory of spherical functions to the context of Gelfand action pairs we obtain a version of the Diaconis-Shahshahani Upper Bound Lemma, controlling the total variation distance to equilibrium for the random wal