A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle

Details A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle

2011-12-26

arxiv.org/abs/1112.5847v1

Mathematics

Probability

Scientific paper

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, with high probability the number of cards within a certain distance from their initial position is the same under the measure induced by the shuffle and under the stationary measure, up to a lower order term. However, under the induced measure, this lower order term is dominated by the cards yet-to-be-removed, and is of higher order than for the stationary measure.

Affiliated with

Also associated with

No associations

Rating

A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-252779