Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory

Understand

The spectral gap $\gamma$ of an ergodic and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence.

• In applications, the transition matrix $P$ may be unknown, yet one sample of the chain up to a fixed time $t$ may be observed.
• Hsu, Kontorovich, and Szepesvari (2015) considered the problem of estimating $\gamma$ from this data.
• Let $\pi$ be the stationary distribution of $P$, and $\pi_\star = \min_x \pi(x)$.