@article{206cac3825374e41b924dfb02bf58a46,
title = "Concentration of Markov chains with bounded moments",
abstract = "Let {Wt}∞t=1 be a finite state stationary Markov chain, and suppose that f is a real-valued function on the state space. If f is bounded, then Gillman's expander Chernoff bound (1993) provides concentration estimates for the random variable f (W1) + · · · +f (Wn) that depend on the spectral gap of the Markov chain and the assumed bound on f. Here we obtain analogous inequalities assuming only that the q'th moment of f is bounded for some q ≥ 2. Our proof relies on reasoning that differs substantially from the proofs of Gillman's theorem that are available in the literature, and it generalizes to yield dimension-independent bounds for mappings f that take values in an Lp(μ) for some p ≥ 2, thus answering (even in the Hilbertian special case p = 2) a question of Kargin (Ann. Appl. Probab. 17 (4) (2007) 1202-1221). ",
keywords = "Concentration bounds, Expander graphs, Gillman's theorem, Markov chains",
author = "Assaf Naor and Shravas Rao and Oded Regev",
note = "Funding Information: 1Supported by the Packard Foundation and the Simons Foundation. The research that is presented here was conducted under the auspices of the Simons Algorithms and Geometry (A&G) Think Tank. 2This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1342536. 3Courant Institute of Mathematical Sciences, New York University. Supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation under Grant No. CCF-1814524. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. Funding Information: Supported by the Packard Foundation and the Simons Foundation. The research that is presented here was conducted under the auspices of the Simons Algorithms and Geometry (A&G) Think Tank. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE- 1342536. Courant Institute of Mathematical Sciences, New York University. Supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation under Grant No. CCF-1814524. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. Publisher Copyright: {\textcopyright} Association des Publications de l'Institut Henri Poincar{\'e}, 2020.",
year = "2020",
month = aug,
doi = "10.1214/19-AIHP1039",
language = "English (US)",
volume = "56",
pages = "2270--2280",
journal = "Annales de l'institut Henri Poincare (B) Probability and Statistics",
issn = "0246-0203",
publisher = "Institute of Mathematical Statistics",
number = "3",
}