Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.15438 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913303807131648 |
|---|---|
| author | Blumberg, Olena Morris, Ben Oberschelp, Hans |
| author_facet | Blumberg, Olena Morris, Ben Oberschelp, Hans |
| contents | In each step of the overlapping cycles shuffle on $n$ cards, a fair coin is flipped which determines whether the $m$th card or the $n$th card is moved to the top of the deck. Angel, Peres, and Wilson showed the following interesting fact: If $m = \lfloor αn \rfloor$ where $α$ is rational, then the relaxation time of a single card in the overlapping cycles shuffle is $θ(n^2)$. However if $α$ is the golden ratio, then the relaxation time of a single card is $θ(n^\frac{3}{2})$. We show that the mixing time of the entire deck under the overlapping cycles shuffle matches these bounds up to a factor of $\log(n)^3$. That is, the mixing time of the entire deck is $O(n^2 \log(n)^3)$ if $α$ is rational and $O(n^\frac{3}{2} \log(n)^3)$ if $α$ is the golden ratio. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_15438 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Mixing Time of the Overlapping Cycles Shuffle Blumberg, Olena Morris, Ben Oberschelp, Hans Probability 60G50 In each step of the overlapping cycles shuffle on $n$ cards, a fair coin is flipped which determines whether the $m$th card or the $n$th card is moved to the top of the deck. Angel, Peres, and Wilson showed the following interesting fact: If $m = \lfloor αn \rfloor$ where $α$ is rational, then the relaxation time of a single card in the overlapping cycles shuffle is $θ(n^2)$. However if $α$ is the golden ratio, then the relaxation time of a single card is $θ(n^\frac{3}{2})$. We show that the mixing time of the entire deck under the overlapping cycles shuffle matches these bounds up to a factor of $\log(n)^3$. That is, the mixing time of the entire deck is $O(n^2 \log(n)^3)$ if $α$ is rational and $O(n^\frac{3}{2} \log(n)^3)$ if $α$ is the golden ratio. |
| title | Mixing Time of the Overlapping Cycles Shuffle |
| topic | Probability 60G50 |
| url | https://arxiv.org/abs/2310.15438 |