Skip navigation
Please use this identifier to cite or link to this item:
Title: Mixing Time Bounds for Random Walks on the Symmetric Group
Authors: Chabot, Riley
Advisors: Nestoridi, Evita
Department: Mathematics
Class Year: 2020
Abstract: In this thesis, we present several different random walks on the symmetric group on n letters, and bound their mixing times from above and below. We begin by reviewing what the mixing time for a walk is, and various techniques developed recently for bounding. The first, using representation theory, was pioneered in [2]. After these preliminaries, we apply these techniques to new walks. Chapter 3 focuses on a specific class of walks, those with no fixed points, and proves some cases for a conjecture about how fast these walks mix. Chapter 4 looks at a more complicated walk, the adjacent j-cycle walk, and gives upper and lower bounds on its mixing time, which we show to be roughly of order n\(^{3}\)log(n) when j = o(n).
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
CHABOT-RILEY-THESIS.pdf313.11 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.