Random Walks on Finite Fields and Heisenberg Groups

Abstract

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 [mu] 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 [mu] 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[~] x F 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.