Improved Analysis of Higher Order Random Walks

Abstract: Local spectral expansion is a very useful method for arguing about the spectral properties of several random walk matrices over simplicial complexes. Our main result is a sharp upper bound on the second eigenvalue of the down-up walk on a pure simplicial complex, in terms of the second eigenvalues of its links. We discuss some applications of this result in analyzing mixing times of Markov chains which include some recent breakthroughs in sampling problems.