论文标题
对称组代数中的单面周期随机潮流
The one-sided cycle shuffles in the symmetric group algebra
论文作者
论文摘要
我们在对称集团$ s_n $上研究一个洗牌运营商的家族，其中包括自上而下的散装。一般的改组方案包括一次从甲板上删除一张卡（根据某些概率分布），并将其重新插入以下（均匀）随机位置。根据组代数$ \ mathbb {r} [s_n] $重写，我们的洗牌对应于右乘法，通过元素的线性组合\ [t_i：= \ text {cyc} _ {i}+\ text {cyc} _ {i，i+1}+\ text {cyc} _ {i，i+1，i+1，i+2}+\ cdots+\ cdots+cdots+cdc} \ Mathbb {r} [s_n] \]对于所有$ i \ in \ {1,2，\ ldots，n \} $（其中$ \ text {cyc} _ {j_1，j_2，j_2，\ ldots，j_p} $代表$ p $ -cycle）。 我们计算这些洗牌操作员及其所有线性组合的特征值。特别是，我们表明，右乘法的特征值$λ_1T_1+λ_2T_2+\ cdots+cdots+λ_nt_n$是数字$ $λ_1M_{i，1}+λ_2m_2m_2m_2m_{i，2}+cdots+cdots+c+λ_nmet$ imen $ $ \ {1,2，\ ldots，n-1 \} $，其中不包含两个连续的整数；这里$ m_ {i，i} $是某些整数。我们计算这些特征值的多重性，并表明，如果它们都不同，则改组的操作员将是可对角度化的。为此，我们证明了右乘法的运算符，$ t_1，t_2，\ ldots，t_n $ on $ \ mathbb {r} [r} [s_n] $同时是三角形的（通过合并定义的基础）。实际上，在$ \ mathbb {r} $上所述的结果实际上是通过任意的交换戒指$ \ mathbf {k} $进行了说明和证明的。 我们通过描述随机播种的固定时间的稳定时间来结束，这是随机选择下方的卡片的随机选择，我们为此事件提供了等待时间。
We study a family of shuffling operators on the symmetric group $S_n$, which includes the top-to-random shuffle. The general shuffling scheme consists of removing one card at a time from the deck (according to some probability distribution) and re-inserting it at a (uniformly) random position further below. Rewritten in terms of the group algebra $\mathbb{R}[S_n]$, our shuffle corresponds to right multiplication by a linear combination of the elements \[t_i:=\text{cyc}_{i}+\text{cyc}_{i,i+1}+\text{cyc}_{i,i+1,i+2}+\cdots+\text{cyc}_{i,i+1,\ldots,n}\in \mathbb{R}[S_n]\] for all $i\in\{1,2,\ldots,n\}$ (where $\text{cyc}_{j_1,j_2,\ldots,j_p}$ stands for a $p$-cycle). We compute the eigenvalues of these shuffling operators and of all their linear combinations. In particular, we show that the eigenvalues of right multiplication by a linear combination $λ_1t_1+λ_2t_2+\cdots+λ_nt_n$ are the numbers $λ_1m_{I,1}+λ_2m_{I,2}+\cdots+λ_nm_{I,n}$, where $I$ ranges over the subsets of $\{1,2,\ldots,n-1\}$ that contain no two consecutive integers; here $m_{I,i}$ are certain integers. We compute the multiplicities of these eigenvalues and show that if they are all distinct, the shuffling operator is diagonalizable. To this purpose, we show that the operators of right multiplication by $t_1,t_2,\ldots,t_n$ on $\mathbb{R}[S_n]$ are simultaneously triangularizable (via a combinatorially defined basis). The results stated here over $\mathbb{R}$ for convenience are actually stated and proved over an arbitrary commutative ring $\mathbf{k}$. We finish by describing a strong stationary time for the random-to-below shuffle, which is the shuffle in which the card that moves below is selected uniformly at random, and we give the waiting time for this event to happen.
