Back to search

Cornell University

Long-jump random walks on finite groups

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Yuwen
Chair dc:contributor.chair
  • Saloff-Coste, Laurent Pascal
Committee members dc:contributor.committeemember
  • Levine, Lionel
  • Tardos, Eva

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
15160035
Dc Identifier Other
ProQuest Submission ID: 12727
ProQuest Publication ID: 28713191

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wang, Yuwen. Long-jump random walks on finite groups. Doctor of Philosophy thesis, Cornell University, 2021. https://hdl.handle.net/1813/110666