The one-sided cycle shuffles in the symmetric group algebra
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910461181558784 |
|---|---|
| author | Grinberg, Darij Lafrenière, Nadia |
| author_facet | Grinberg, Darij Lafrenière, Nadia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06274 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The one-sided cycle shuffles in the symmetric group algebra Grinberg, Darij Lafrenière, Nadia Combinatorics Group Theory Probability Representation Theory 05E99, 20C30, 60J10 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. |
| title | The one-sided cycle shuffles in the symmetric group algebra |
| topic | Combinatorics Group Theory Probability Representation Theory 05E99, 20C30, 60J10 |
| url | https://arxiv.org/abs/2212.06274 |