The spectral gap of a finite, 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 n may be observed. We consider here the problem of estimating the spectral gap from this data and give a fully empirical interval estimate, whose width is essentially unimprovable (shortened abstract).
%0 Journal Article
%1 HsuKoLePeSzeWo19
%A Hsu, D.
%A Kontorovich, A.
%A Levin, D. A.
%A Peres, Y.
%A Szepesvári, Cs.
%A Wolfer, G.
%D 2019
%J Annals of Applied Probability
%K Markov a bounds, chains, data-dependent finite-sample mixing, posteriori theory
%N 4
%P 2439--2480
%T Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path
%V 29
%X The spectral gap of a finite, 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 n may be observed. We consider here the problem of estimating the spectral gap from this data and give a fully empirical interval estimate, whose width is essentially unimprovable (shortened abstract).
@article{HsuKoLePeSzeWo19,
abstract = {The spectral gap of a finite, 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 n may be observed. We consider here the problem of estimating the spectral gap from this data and give a fully empirical interval estimate, whose width is essentially unimprovable (shortened abstract).},
added-at = {2020-03-17T03:03:01.000+0100},
author = {Hsu, D. and Kontorovich, A. and Levin, D. A. and Peres, Y. and {Sz}epesv{\'a}ri, {Cs}. and Wolfer, G.},
biburl = {https://www.bibsonomy.org/bibtex/24433feed9c7777dc7f0b2bc73e2ff950/csaba},
date-added = {2019-07-24 20:08:32 -0600},
date-modified = {2019-07-24 20:17:30 -0600},
interhash = {66eeb3de0753e6463b4497b8b4f4bcfd},
intrahash = {4433feed9c7777dc7f0b2bc73e2ff950},
journal = {Annals of Applied Probability},
keywords = {Markov a bounds, chains, data-dependent finite-sample mixing, posteriori theory},
month = {July},
number = 4,
pages = {2439--2480},
pdf = {papers/AAP19_mixing.pdf},
timestamp = {2020-03-17T03:03:01.000+0100},
title = {Mixing Time Estimation in Reversible {M}arkov Chains from a Single Sample Path},
volume = 29,
year = 2019
}