Improved bounds for the mixing time of the random-to-random insertion shuffle
classification
🧮 math.PR
keywords
boundinsertionmixingrandom-to-randomshuffletimeupperanalysis
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.