Spectral Gap for Random-to-Random Shuffling on Linear Extensions. Issue 1 (2nd January 2017)

• Record Type: Journal Article
• Authors: Ayyer, Arvind; Schilling, Anne; Thiéry, Nicolas M.
• Is Part Of: Experimental mathematics. Volume 26:Issue 1(2017)
• Page Start: 22
• Page End: 30
• Publication Date: 2017-01-02
• Subjects: sampling linear extensions -- posets -- random-to-random shuffling -- discrete Markov chain -- spectral gap -- second largest eigenvalue -- mixing time; 60J10 -- 05C81 -- 06A07; Mathematics -- Periodicals; Mathematics -- Research -- Periodicals; 510.724
• DOI: 10.1080/10586458.2015.1107868
• Languages: English
• ISSNs: 1058-6458

Abstract

ABSTRACT: In this article, 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 log n ). We conjecture that the mixing time is in fact O ( n log n ) as for the usual random-to-random shuffling.