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

DOI10.1080/10586458.2015.1107868zbMATH Open1360.60133arXiv1412.7488OpenAlexW3100041946MaRDI QIDQ2969993FDOQ2969993

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

Publication date: 24 March 2017

Published in: Experimental Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Combinatorial Markov chains on linear extensions
• Title not available (Why is that?)
• Proof of Aldous' spectral gap conjecture
• An interlacing theorem for eigenvalues of self-adjoint operators
• Faster random generation of linear extensions

Cited In (6)

• Spectra of random M-extensions
• Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
• 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

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)