Mixing Time Bounds for Overlapping Cycles Shuffles
| Dublin Core | PKP Metadata Items | Metadata for this Document | |
| 1. | Title | Title of document | Mixing Time Bounds for Overlapping Cycles Shuffles |
| 2. | Creator | Author's name, affiliation, country | Johan Jonasson; Chalmers University of Technology and Göteborg University; Sweden |
| 3. | Subject | Discipline(s) | |
| 3. | Subject | Keyword(s) | comparison technique, Wilson's technique, relative entropy |
| 3. | Subject | Subject classification | 60J10 |
| 4. | Description | Abstract | Consider a deck of n cards. Let $p_1,p_2,\ldots,p_n$ be a probability vector and consider the mixing time of the card shuffle which at each step of time picks a position according to the pi 's and move the card in that position to the top. This setup was introduced in [5], where a few special cases were studied. In particular the case $p_{n-k}=p_n=1/2$, $k=\Theta(n)$, turned out to be challenging and only a few lower bounds were produced. These were improved in [1] where it was shown that the relaxation time for the motion of a single card is $\Theta(n^2)$ when $k/n$ approaches a rational number. In this paper we give the first upper bounds. We focus on the case $m:=n-k=\lfloor n/2\rfloor$. It is shown that for the additive symmetrization as well as the lazy version of the shuffle, the mixing time is $O(n^3\log(n))$. We then consider two other modifications of the shuffle. The first one is the case $p_{n-k}=p_{n-k+1}=1/4$ and $p_n=1/2$. Using the entropy technique developed by Morris [7], we show that mixing time is $O(n^2\log^3(n))$ for the shuffle itself as well as for the symmetrization. The second modification is a variant of the first, where the moves are made in pairs so that if the first move involves position $n$ , then the second move must be taken from positions $m$ or $m+1$ and vice versa. Interestingly, this shuffle is much slower; the mixing time is at least of order $n^3\log(n)$ and at most of order $n^3\log^3(n))$. It is also observed that results of [1] can be modified to improve lower bounds for some $k=o(n)$. |
| 5. | Publisher | Organizing agency, location | |
| 6. | Contributor | Sponsor(s) | |
| 7. | Date | (YYYY-MM-DD) | 2011-06-11 |
| 8. | Type | Status & genre | Peer-reviewed Article |
| 8. | Type | Type | |
| 9. | Format | File format | |
| 10. | Identifier | Uniform Resource Identifier | http://ejp.ejpecp.org/article/view/912 |
| 10. | Identifier | Digital Object Identifier | 10.1214/EJP.v16-912 |
| 11. | Source | Journal/conference title; vol., no. (year) | Electronic Journal of Probability; Vol 16 |
| 12. | Language | English=en | |
| 14. | Coverage | Geo-spatial location, chronological period, research sample (gender, age, etc.) | |
| 15. | Rights | Copyright and permissions | The Electronic Journal of Probability applies the Creative Commons Attribution License (CCAL) to all articles we publish in this journal. Under the CCAL, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles published in EJP, so long as the original authors and source are credited. This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available. Summary of the Creative Commons Attribution License You are free
|