##
**A lower bound for the mixing time of the random-to-random insertions shuffle.**
*(English)*
Zbl 1410.60072

Summary: 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, P. Diaconis [in: Groups, combinatorics and geometry. Proceedings of the L. M. S. Durham symposium, Durham, UK, July 16–26, 2001. River Edge, NJ: World Scientific. 73–97 (2003; Zbl 1026.60005)] 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 for the stationary measure.

### MSC:

60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |

60C05 | Combinatorial probability |