Mixing Time Bounds for Overlapping Cycles Shuffles

Johan Jonasson (Chalmers University of Technology and Göteborg University)


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)$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1281-1295

Publication Date: June 11, 2011

DOI: 10.1214/EJP.v16-912


  1. Angel, Omer; Peres, Yuval; Wilson, David B. Card shuffling and Diophantine approximation. Ann. Appl. Probab. 18 (2008), no. 3, 1215--1231. MR2418243 (2009c:60013)
  2. Diaconis, Persi; Saloff-Coste, Laurent. Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993), no. 4, 2131--2156. MR1245303 (95a:60009)
  3. Diaconis, Persi; Shahshahani, Mehrdad. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159--179. MR0626813 (82h:60024)
  4. Durrett, Rick. Shuffling chromosomes. J. Theoret. Probab. 16 (2003), no. 3, 725--750. MR2009200 (2004j:92045)
  5. Jonasson, Johan. Biased random-to-top shuffling. Ann. Appl. Probab. 16 (2006), no. 2, 1034--1058. MR2244440 (2008g:60218)
  6. Jonasson, Johan. The overhand shuffle mixes in $Theta(nsp 2log n)$ steps. Ann. Appl. Probab. 16 (2006), no. 1, 231--243. MR2209341 (2006m:60016)
  7. Morris, Ben. Improved mixing time bounds for the Thorp shuffle and $L$-reversal chain. Ann. Probab. 37 (2009), no. 2, 453--477. MR2510013 (2010e:60156)
  8. Saloff-Coste, Laurent. Random walks on finite groups. Probability on discrete structures, 263--346, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023654 (2004k:60133)
  9. Wilson, David Bruce. Mixing times of Lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14 (2004), no. 1, 274--325. MR2023023 (2004m:60155)
  10. Wilson, David Bruce. Mixing time of the Rudvalis shuffle. Electron. Comm. Probab. 8 (2003), 77--85. MR1987096 (2004d:60191)

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.