# Improved Analysis of Higher Order Random Walks and Applications

arXiv: https://arxiv.org/abs/2001.02827 · HTML: https://mlsanity.com/paper/2001.02827/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jan 2020.

## Built on by (most cited first, 3 of 3)

- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Learning From Simplicial Data Based on Random Walks and 1D Convolutions](https://mlsanity.com/paper/2404.03434/) (2024)

## Abstract (arXiv)

The motivation of this work is to extend the techniques of higher order random walks on simplicial complexes to analyze mixing times of Markov chains for combinatorial problems. 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 show some applications of this result in analyzing mixing times of Markov chains, including sampling independent sets of a graph and sampling common independent sets of two partition matroids.