Long-jump random walks on finite groups

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.