Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp013x816q641
 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). URI: http://arks.princeton.edu/ark:/88435/dsp013x816q641 Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2020