2019/10/11 by Sarah Miracle, Miracle, Sarah, Amanda Pascoe Streib +3 · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1910.05184
openalex publication_date 2019/10/11 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
The spectral gap of a Markov chain can be bounded by the spectral gaps of\nconstituent "restriction" chains and a "projection" chain, and the strength of\nsuch a bound is the content of various decomposition theorems. In this paper,\nwe introduce a new parameter that allows us to improve upon these bounds. We\nfurther define a notion of orthogonality between the restriction chains and\n"complementary" restriction chains. This leads to a new Complementary\nDecomposition theorem, which does not require analyzing the projection chain.\nFor \ε-orthogonal chains, this theorem may be iterated O(1/\ε)\ntimes while only giving away a constant multiplicative factor on the overall\nspectral gap. As an application, we provide a 1/n-orthogonal decomposition of\nthe nearest neighbor Markov chain over k-class biased monotone permutations\non [n], as long as the number of particles in each class is at least C\log\nn. This allows us to apply the Complementary Decomposition theorem iteratively\nn times to prove the first polynomial bound on the spectral gap when k is\nas large as \Θ(n/\log n). The previous best known bound assumed k was\nat most a constant.\n