Concentration of Markov chains with bounded moments

Assaf Naor, Shravas Rao, Oded Regev

Research output: Contribution to journalArticlepeer-review

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).

Original languageEnglish (US)
Pages (from-to)2270-2280
Number of pages11
JournalAnnales de l'institut Henri Poincare (B) Probability and Statistics
Volume56
Issue number3
DOIs
StatePublished - Aug 2020

Keywords

  • Concentration bounds
  • Expander graphs
  • Gillman's theorem
  • Markov chains

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'Concentration of Markov chains with bounded moments'. Together they form a unique fingerprint.

Cite this