Mixing time of the torus shuffle
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929585928536064 |
|---|---|
| author | Blumberg, Olena Morris, Ben Senda, Alto |
| author_facet | Blumberg, Olena Morris, Ben Senda, Alto |
| contents | We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only triplets of cards. Then we use it to analyze a classic model of card shuffling.
In 1988, Diaconis introduced the following Markov chain. Cards are arranged in an $n$ by $n$ grid. Each step, choose a row or column, uniformly at random, and cyclically rotate it by one unit in a random direction. He conjectured that the mixing time is ${\rm O}(n^3 \log n)$. We obtain a bound that is within a poly log factor of the conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06006 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mixing time of the torus shuffle Blumberg, Olena Morris, Ben Senda, Alto Probability 14J60 We prove a theorem that reduces bounding the mixing time of a card shuffle to verifying a condition that involves only triplets of cards. Then we use it to analyze a classic model of card shuffling. In 1988, Diaconis introduced the following Markov chain. Cards are arranged in an $n$ by $n$ grid. Each step, choose a row or column, uniformly at random, and cyclically rotate it by one unit in a random direction. He conjectured that the mixing time is ${\rm O}(n^3 \log n)$. We obtain a bound that is within a poly log factor of the conjecture. |
| title | Mixing time of the torus shuffle |
| topic | Probability 14J60 |
| url | https://arxiv.org/abs/2411.06006 |