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 [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.
Zhu, Yi. (January 2011). Random Walks on Finite Fields and Heisenberg Groups (Master's Thesis, East Carolina University). Retrieved from the Scholarship. (http://hdl.handle.net/10342/3603.)
Zhu, Yi. Random Walks on Finite Fields and Heisenberg Groups. Master's Thesis. East Carolina University, January 2011. The Scholarship. http://hdl.handle.net/10342/3603. May 27, 2018.
Zhu, Yi, “Random Walks on Finite Fields and Heisenberg Groups” (Master's Thesis., East Carolina University, January 2011).
Zhu, Yi. Random Walks on Finite Fields and Heisenberg Groups [Master's Thesis]. Greenville, NC: East Carolina University; January 2011.
East Carolina University