Mixing Time Bounds for Random Walks on the Symmetric Group

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).