Random walks on finite fields and Heisenberg groups

Let H be a finite group and mu a probability measure on H. This data determines an invariant random walk on H beginning from the identity element. The probability distribution for the state of the random walk after n steps is given by the n'th convolution power of the probability measure mu. The random walk and measure m are said to be ergodic if the support of this distribution is the entire group for n sufficiently 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 m 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 walk determined by mu.;The main results in this thesis concern invariant random walks on finite fields and three dimensional Heisenberg groups over finite fields. Let F be a finite field of odd characteristic and K a subgroup of the multiplicative group for F with even order. We obtain a necessary and sufficient condition for ergodicity of the action pair K:F and an explicit summation formula for the upper bound on total variation distance to equilibrium guaranteed by the Upper Bound Lemma. Let F˜ be a quadratic extension field for F˜ and U denote the kernel of the norm mapping from F˜ to F. An application of our field theoretic criterion for ergodicity shows that U:F˜ is an ergodic action pair and we specialize our upper bound result to this context. Forming the three dimensional Heisenberg group H=F˜xF over F the action of U on F˜ induces an action of U on H by automorphisms. Benson and Ratcliff have shown that U:H is a Gelfand action pair and determined the associated spherical functions. We prove that the pair U:H is ergodic and make explicit the bound given by the Upper Bound Lemma.