Random walks on the symmetric group: cutoff for one-sided transposition shuffles

In this thesis we introduce a new type of card shuffle called the one-sided transposition
shuffle. At each step a card is chosen uniformly from the pack and then transposed
with another card chosen uniformly from below it. This defines a random walk on the
symmetric group generated by a distribution which is non-constant on the conjugacy class
of transpositions. Nevertheless, we provide an explicit formula for all eigenvalues of the
shuffle by demonstrating a useful correspondence between eigenvalues and standard Young
tableaux. This allows us to prove the existence of a total-variation cutoff for the one-sided
transposition shuffle at time n log n. We also study weighted generalisations of the one-sided
transposition shuffle called biased one-sided transposition shuffles. We compute the
full spectrum for every biased one-sided transposition shuffle, and prove the existence
of a total variation cutoff for certain choices of weighted distribution. In particular, we
recover the eigenvalues and well known mixing time of the classical random transposition
shuffle. We study the hyperoctahedral group as an extension of the symmetric group, and
formulate the one-sided transposition shuffle and random transposition shuffle as random
walks on this new group. We determine the spectrum of each hyperoctahedral shuffle by
developing a correspondence between their eigenvalues and standard Young bi-tableaux.
We prove that the one-sided transposition shuffle on the hyperoctahedral group exhibits
a cutoff at n log n, the same time as its symmetric group counterpart. We conjecture
that this results extends to the biased one-sided transposition shuffles and the random
transposition shuffle on the hyperoctahedral group.