Computer Science/Discrete Mathematics Seminar I

While the notion of spectral gap is a fundamental and very useful feature of reversible Markov chains, there is no standard analogue of this notion for nonreversible chains. In this talk, I will present a simple proposal for spectral gap of nonreversible chains, and show that it shares all of the nice properties of the reversible spectral gap. The most important property of this spectral gap is that its reciprocal gives an exact characterization, with upper and lower bounds, of the time required for convergence of empirical averages. This works even if there is no contraction, such as in dynamical systems.