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

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)$. They showed that, if $t = tilde{O}bigl(frac{1}{gamma^3 pi_star}bigr)$, then $gamma$ can be estimated to within multiplicative constants with high probability. They also proved that $tilde{Omega}bigl(frac{n}{gamma}bigr)$ steps are required for precise estimation of $gamma$. We show that $tilde{O}bigl(frac{1}{gamma pi_star}bigr)$ steps of the chain suffice to estimate $gamma$ up to multiplicative constants with high probability. When $pi$ is uniform, this matches (up to logarithmic corrections) the lower bound of Hsu, Kontorovich, and Szepesvari.