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.
Categories: math.ST math.PR stat.TH