Iterated Decomposition of Biased Permutations Via New Bounds on the Spectral Gap of Markov Chains

The spectral gap of a Markov chain can be bounded by the spectral gaps of constituent “restriction” chains and a “projection” chain, and the strength of such a bound is the content of various decomposition theorems. In this paper, we introduce a new parameter that allows us to improve upon these bounds. We further define a notion of orthogonality between the restriction chains and “complementary” restriction chains. This leads to a new Complementary Decomposition theorem, which does not require analyzing the projection chain. For $ϵ$-orthogonal chains, this theorem may be iterated $O(1\mathrm{/}ϵ)$ times while only giving away a constant multiplicative factor on the overall spectral gap. As an application, we provide a $1\mathrm{/}n$-orthogonal decomposition of the nearest neighbor Markov chain over $k$-class biased monotone permutations on [$n$], as long as the number of particles in each class is at least $C\log n$\mathrm{.}ThisallowsustoapplytheComplementaryDecompositiontheoremiteratively$n$timestoprovethefirstpolynomialboundonthespectralgapwhen$k$ is as large as $\mathrm{\Theta }(n\mathrm{/}\log n)$. The previous best known bound assumed $k$ was at most a constant.