The $S_k$ shuffle block dynamics
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910790577029120 |
|---|---|
| author | Nestoridi, Evita Priestley, Amanda Schmid, Dominik |
| author_facet | Nestoridi, Evita Priestley, Amanda Schmid, Dominik |
| contents | We introduce and analyze the $S_k$ shuffle on $N$ cards, a natural generalization of the celebrated random adjacent transposition shuffle. In the $S_k$ shuffle, we choose uniformly at random a block of $k$ consecutive cards, and shuffle these cards according to a permutation chosen uniformly at random from the symmetric group on $k$ elements. We study the total-variation mixing time of the $S_k$ shuffle when the number of cards $N$ goes to infinity, allowing also $k=k(N)$ to grow with $N$. In particular, we show that the cutoff phenomenon occurs when $k=o(N^{\frac{1}{6}})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_02588 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The $S_k$ shuffle block dynamics Nestoridi, Evita Priestley, Amanda Schmid, Dominik Probability Mathematical Physics Combinatorics Primary: 60K35, Secondary: 60K37, 60J27 We introduce and analyze the $S_k$ shuffle on $N$ cards, a natural generalization of the celebrated random adjacent transposition shuffle. In the $S_k$ shuffle, we choose uniformly at random a block of $k$ consecutive cards, and shuffle these cards according to a permutation chosen uniformly at random from the symmetric group on $k$ elements. We study the total-variation mixing time of the $S_k$ shuffle when the number of cards $N$ goes to infinity, allowing also $k=k(N)$ to grow with $N$. In particular, we show that the cutoff phenomenon occurs when $k=o(N^{\frac{1}{6}})$. |
| title | The $S_k$ shuffle block dynamics |
| topic | Probability Mathematical Physics Combinatorics Primary: 60K35, Secondary: 60K37, 60J27 |
| url | https://arxiv.org/abs/2304.02588 |