Improved bounds for the mixing time of the random-to-random insertion shuffle
Skip to main content
eScholarship
Open Access Publications from the University of California

Department of Mathematics

Faculty bannerUC Davis

Improved bounds for the mixing time of the random-to-random insertion shuffle

Published Web Location

https://arxiv.org/pdf/1412.0070.pdf
No data is associated with this publication.
Abstract

We prove an upper bound of $1.5324 n \log n$ for the mixing time of the random-to-random insertion shuffle, improving on the best known upper bound of $2 n \log n$. Our proof is based on the analysis of a non-Markovian coupling.

Item not freely available? Link broken?
Report a problem accessing this item