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

**Eliran Subag**

*(Technion - Israel Institute of Technology)*

#### Abstract

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

#### References

- 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

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