Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path

Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path. Hsu, D., Kontorovich, A., Levin, D. A., Peres, Y., Szepesvári, C., & Wolfer, G. Annals of Applied Probability, 29(4):2439–2480, 07, 2019.

Paper abstract bibtex 4 downloads

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).},
	author = {Hsu, Daniel and Kontorovich, Arieh and Levin, David A. and Peres, Yuval and Szepesv{\'a}ri, Csaba and Wolfer, Geoffrey},
	date = {2019-07},
	date-added = {2019-07-24 20:08:32 -0600},
	date-modified = {2019-07-24 20:17:30 -0600},
	journal = {Annals of Applied Probability},
	keywords = {mixing, data-dependent bounds, a posteriori bounds, Markov chains, finite-sample bounds, theory},
	month = {07},
	number = {4},
	pages = {2439--2480},
	title = {Mixing Time Estimation in Reversible Markov Chains from a Single Sample Path},
	url_paper = {AAP19_mixing.pdf},
	volume = {29},
	year = {2019}}

Downloads: 4