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 $epsilon$-orthogonal chains, this theorem may be iterated $O(1/epsilon)$ times while only giving away a constant multiplicative factor on the overall spectral gap. As an application, we provide a $1/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 $Clog n$. This allows us to apply the Complementary Decomposition theorem iteratively $n$ times to prove the first polynomial bound on the spectral gap when $k$ is as large as $Theta(n/log n)$. The previous best known bound assumed $k$ was at most a constant.
Download