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

DOI10.1214/17-ECP3955MaRDI QIDQ519713zbMATH OpenOpenAlexFDO

Authors Chuan Qin, Ben Morris

Publication date 5 April 2017

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0070, https://projecteuclid.org/euclid.ecp/1491271396

zbMATH Keywords

mixing timenon-Markovian couplingrandom-to-random shuffle

Mathematics Subject Classification ID

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

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

Recommendations

• A lower bound for the mixing time of the random-to-random insertions shuffle
• Cutoff for random to random card shuffle
• Improved mixing time bounds for the Thorp shuffle
• Mixing time of the Rudvalis shuffle
• Mixing time of the card-cyclic-to-random shuffle

Cited in

(8)

• Spectral analysis of random-to-random Markov chains
• Mixing time of the Rudvalis shuffle
• Cutoff for random to random card shuffle
• Eigenvalues of symmetrized shuffling operators
• Spectral gap for random-to-random shuffling on linear extensions
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Comparing limit profiles of reversible Markov chains
• A strong uniform time for random transpositions

This page was built for publication: Improved bounds for the mixing time of the random-to-random shuffle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519713)