Abstract:

In this talk I'll present some general quantitative near-bipartite results for reversible Markov chains. It turns out that if the total variation of a reversible transition matrix P is much larger than that of its lazy version (I+P)/2 then P must satisfy certain strong near-bipartite behaviors, which for most starting states prevail for order of the mixing time number of steps. Namely, if f is an eigenvector corresponding to the smallest eigenvalue of P, then the chain is likely to alternate between being at A:={x : f(x) is positive} at even times to being at the complement at odd times, or vice-versa, for order mixing time number of steps. Moreover, the mixing behavior in this case is in a sense completely governed by the probability the chain assigns A. We also give a probabilistic characterization of the absolute spectral gap of P and show that P can have at most one (negative) eigenvalue whose distance from -1 is at most a small absolute constant the spectral gap (= 1 - second largest e.v. of P)