论文标题
彩色排列上的顶部到随机散热
Top to random shuffles on colored permutations
论文作者
论文摘要
$ n $卡的甲板通过反复脱下顶部卡，用概率$ 1/2 $翻转，然后将其插入以随机位置将其插入甲板，从而改组。该过程可以被视为签名排列的组$ b_n $上的马尔可夫链。我们表明，过渡概率矩阵的特征值为$ 0,1/n，2/n，\ ldots，（n-1）/n，1 $ and and eigenValue $ i/n $的多重性等于{\ em signed}的数量{\ em signed}置换率的数量。我们还显示了彩色排列的相似结果。此外，我们表明，这款马尔可夫链的混合时间为$ n \ log n $，与普通的“自面到随机”的散装相同，而无需翻转卡片。还通过使用第二类Stirling数字的渐近行为来分析截止。
A deck of $n$ cards are shuffled by repeatedly taking off the top card, flipping it with probability $1/2$, and inserting it back into the deck at a random position. This process can be considered as a Markov chain on the group $B_n$ of signed permutations. We show that the eigenvalues of the transition probability matrix are $0,1/n,2/n,\ldots,(n-1)/n,1$ and the multiplicity of the eigenvalue $i/n$ is equal to the number of the {\em signed} permutation having exactly $i$ fixed points. We show the similar results also for the colored permutations. Further, we show that the mixing time of this Markov chain is $n\log n$, same as the ordinary 'top-to-random' shuffles without flipping the cards. The cut-off is also analyzed by using the asymptotic behavior of the Stirling numbers of the second kind.
