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

preprint2016arXivOpen access

Abstract

The spectral gap γγ of an ergodic and reversible Markov chain is an important parameter measuring the asymptotic rate of convergence. In applications, the transition matrix PP may be unknown, yet one sample of the chain up to a fixed time tt may be observed. Hsu, Kontorovich, and Szepesvari (2015) considered the problem of estimating γγ from this data. Let ππ be the stationary distribution of PP, and π⋆=min⁡xπ(x)π_\star = \min_x π(x). They showed that, if t=O~(1γ3π⋆)t = \tilde{O}\bigl(\frac{1}{γ^3 π_\star}\bigr), then γγ can be estimated to within multiplicative constants with high probability. They also proved that Ω~(nγ)\tildeΩ\bigl(\frac{n}γ\bigr) steps are required for precise estimation of γγ. We show that O~(1γπ⋆)\tilde{O}\bigl(\frac{1}{γπ_\star}\bigr) steps of the chain suffice to estimate γγ up to multiplicative constants with high probability. When ππ is uniform, this matches (up to logarithmic corrections) the lower bound of Hsu, Kontorovich, and Szepesvari.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.