JavaScript is disabled for your browser. Some features of this site may not work without it.
Long-jump random walks on finite groups

Author
Wang, Yuwen
Abstract
In this thesis, we study a variant of simple random walk on a finite group. At each step, we choose an element, s, from a set of generators uniformly, and an integer, j, from symmetric distribution, D, on the integers associated with the chosen direction, and move from the current position, g, to gs^j. For these walks, we want to measure how fast the walk converges to the stationary distribution, i.e. the mixing time. This thesis has two main parts: (1) When the underlining group is cyclic and D is a power law distribution, we compute the eigenvalues of the random walk and the mixing time. (2) We show that if the finite group is nilpotent, the mixing time is of the same order of magnitude as the diameter of a suitable pseudo-metric on the group, which is associated the generators and D. We combine classical eigenvalue techniques and heat kernel techniques to give sharp bounds on the l^2-distance between the distribution of the position of the walker and the stationary distribution, and compute the relevant diameter for some examples.
Description
84 pages
Date Issued
2021-08Subject
groups; probability; random walks
Committee Chair
Saloff-Coste, Laurent Pascal
Committee Member
Levine, Lionel; Tardos, Eva
Degree Discipline
Mathematics
Degree Name
Ph. D., Mathematics
Degree Level
Doctor of Philosophy
Rights
Attribution 4.0 International
Rights URI
Type
dissertation or thesis
Except where otherwise noted, this item's license is described as Attribution 4.0 International