Abstract
dc:description.abstractIn 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 × 3Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 15160035
- Dc Identifier Other
-
ProQuest Submission ID: 12727
ProQuest Publication ID: 28713191