论文标题
在对称组上随机步行：单方面转置洗牌的截止
Random Walks on the Symmetric Group: Cutoff for One-sided Transposition Shuffles
论文作者
论文摘要
在本文中，我们介绍了一种新型的卡片，称为单方面的转置洗牌。在每个步骤中，从包装均匀地选择了一张卡，然后用另一个卡片从下面选择另一个卡片。这定义了由分布产生的对称组的随机步行，该分布在换位的共轭类别上是非恒定的。然而，我们通过证明特征值和标准的Young tableaux之间有用的对应关系，为洗牌的所有特征值提供明确的公式。这使我们能够证明在时间$ n \ log n $的单方面转置随机缩短的总变量截止。我们还研究了称为有偏见的单方面转置混合物的单方面转座洗牌的加权概括。我们为每种有偏见的单方面换个侧面洗牌计算全光谱，并证明存在某些加权分布选择的总变化截止。特别是，我们恢复了经典随机转置洗牌的特征值和众所周知的混合时间。我们将高肠面体组研究为对称组的扩展，并在此新组上随机行走时，制定了单面转置洗牌和随机的转座散装。我们通过在其特征值和标准的年轻双尾元之间开发对应关系来确定每个高二摄氏度的频谱。我们证明，在高二面体组上的单方面转置随机散布在$ n \ log n $的截止时间与对称组的同时相同。我们猜想这结果扩展到偏置的单方面转座混合物和上二十面体群上的随机转置混合物。
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.
