A lower bound for the mixing time of the random-to-random Insertions shuffle

Eliran Subag (Technion - Israel Institute of Technology)


The best known lower and upper bounds on the mixing time for the random to-random insertions shuffle are $(1/2-o(1))n\log n$ and $(2+o(1))n\log n$. A long standing open problem is to prove that the mixing time exhibits a cutoff. In particular, Diaconis conjectured that the cutoff occurs at $3/4n\log n$. Our main result is a lower bound of $t_n = (3/4-o(1))n\log n$, corresponding to this conjecture.

Our method is based on analysis of the positions of cards yet-to-be removed.We show that for large $n$ and $t_n$ as above, there exists $f(n)=\Theta(\sqrt{n\log n})$ such that,with high probability, under both the measure induced by the shuffle and the stationary measure, the number of cards within a certain distance from their initial positionis $f(n)$ plus a lower order term. However, under the induced measure, this lower order term is strongly influenced bythe number of cards yet-to-be-removed, and is of higher order than forthe stationary measure.

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

Pages: 1-20

Publication Date: February 3, 2013

DOI: 10.1214/EJP.v18-1950


  • Billingsley, Patrick. Probability and measure. Third edition. Wiley Series in Probability and Mathematical Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1995. xiv+593 pp. ISBN: 0-471-00710-2 MR1324786
  • Diaconis, P.; Saloff-Coste, L. Random walks on finite groups: a survey of analytic techniques. Probability measures on groups and related structures, XI (Oberwolfach, 1994), 44--75, World Sci. Publ., River Edge, NJ, 1995. MR1414925
  • Diaconis, Persi. Mathematical developments from the analysis of riffle shuffling. Groups, combinatorics & geometry (Durham, 2001), 73--97, World Sci. Publ., River Edge, NJ, 2003. MR1994961
  • Diaconis, Persi; Saloff-Coste, Laurent. Comparison techniques for random walk on finite groups. Ann. Probab. 21 (1993), no. 4, 2131--2156. MR1245303
  • Petrov, Valentin V. Limit theorems of probability theory. Sequences of independent random variables. Oxford Studies in Probability, 4. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995. xii+292 pp. ISBN: 0-19-853499-X MR1353441
  • Reyes, Jay-Calvin Uyemura. Random walk, semi-direct products, and card shuffling. Thesis (Ph.D.)–Stanford University. ProQuest LLC, Ann Arbor, MI, 2002. 163 pp. ISBN: 978-0493-62998-8 MR2703300
  • Saloff-Coste, L.; Zúñiga, J. Refined estimates for some basic random walks on the symmetric and alternating groups. ALEA Lat. Am. J. Probab. Math. Stat. 4 (2008), 359--392. MR2461789

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