2020/12/09 by Oliver Matheau-Raven, Matheau-Raven, Oliver
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2012.05118
openalex publication_date 2020/12/09 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
In this thesis we introduce a new type of card shuffle called the one-sided\ntransposition shuffle. At each step a card is chosen uniformly from the pack\nand then transposed with another card chosen uniformly from below it. This\ndefines a random walk on the symmetric group generated by a distribution which\nis non-constant on the conjugacy class of transpositions. Nevertheless, we\nprovide an explicit formula for all eigenvalues of the shuffle by demonstrating\na useful correspondence between eigenvalues and standard Young tableaux. This\nallows us to prove the existence of a total-variation cutoff for the one-sided\ntransposition shuffle at time n\log n. We also study weighted generalisations\nof the one-sided transposition shuffle called biased one-sided transposition\nshuffles. We compute the full spectrum for every biased one-sided transposition\nshuffle, and prove the existence of a total variation cutoff for certain\nchoices of weighted distribution. In particular, we recover the eigenvalues and\nwell known mixing time of the classical random transposition shuffle. We study\nthe hyperoctahedral group as an extension of the symmetric group, and formulate\nthe one-sided transposition shuffle and random transposition shuffle as random\nwalks on this new group. We determine the spectrum of each hyperoctahedral\nshuffle by developing a correspondence between their eigenvalues and standard\nYoung bi-tableaux. We prove that the one-sided transposition shuffle on the\nhyperoctahedral group exhibits a cutoff at n\log n, the same time as its\nsymmetric group counterpart. We conjecture that this results extends to the\nbiased one-sided transposition shuffles and the random transposition shuffle on\nthe hyperoctahedral group.\n