Concentration inequalities for Markov chains by Marton couplings and spectral methods

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We prove a version of McDiarmid’s bounded differences inequality for Markov chains, with constants proportional to the mixing time of the chain. We also show variance bounds and Bernstein-type inequalities for empirical averages of Markov chains. In the case of non-reversible chains, we introduce a new quantity called the “pseudo spectral gap”, and show that it plays a similar role for non-reversible chains as the spectral gap plays for reversible chains. Our techniques for proving these results are based on a coupling construction of Katalin Marton, and on spectral techniques due to Pascal Lezaud. The pseudo spectral gap generalises the multiplicative reversiblication approach of Jim Fill.
Original languageEnglish
Article number79
Number of pages32
JournalElectronic journal of probability
Volume20
DOIs
Publication statusPublished - Sept 2015
Externally publishedYes

Fingerprint

Dive into the research topics of 'Concentration inequalities for Markov chains by Marton couplings and spectral methods'. Together they form a unique fingerprint.

Cite this