Spectral gap for random-to-random shuffling on linear extensions

DOI10.1080/10586458.2015.1107868MaRDI QIDQ2969993zbMATH OpenOpenAlexFDO

Authors A. Ayyer, Anne Schilling, Nicolas Thiéry

Publication date 24 March 2017

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.7488

zbMATH Keywords

second largest eigenvaluemixing timeposetsspectral gaplinear extensionsdiscrete Markov chainrandom-to-random shuffling

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81) Combinatorics of partially ordered sets (06A07)

Abstract: In this paper, we propose a new Markov chain which generalizes random-to-random shuffling on permutations to random-to-random shuffling on linear extensions of a finite poset of size $n$. We conjecture that the second largest eigenvalue of the transition matrix is bounded above by $(1+1/n)(1-2/n)$ with equality when the poset is disconnected. This Markov chain provides a way to sample the linear extensions of the poset with a relaxation time bounded above by $n^2/(n+2)$ and a mixing time of $O(n^{2}logn)$. We conjecture that the mixing time is in fact $O(nlogn)$ as for the usual random-to-random shuffling.

Recommendations

• Mixing time for Markov chain on linear extensions
• Improved bounds for the mixing time of the random-to-random shuffle
• Rate of convergence for shuffling cards by transpositions
• Cutoff for a one-sided transposition shuffle
• Faster random generation of linear extensions

Cites work

• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• An interlacing theorem for eigenvalues of self-adjoint operators
• Combinatorial Markov chains on linear extensions
• Faster random generation of linear extensions
• Proof of Aldous' spectral gap conjecture

Cited in

(6)

• Total variation cutoff for the flip-transpose top with random shuffle
• The expected jaggedness of order ideals
• Spectral analysis of random-to-random Markov chains
• Mixing time for Markov chain on linear extensions
• Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
• Spectra of random M-extensions

This page was built for publication: Spectral gap for random-to-random shuffling on linear extensions

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