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 language | English |
---|---|
Article number | 79 |
Number of pages | 32 |
Journal | Electronic journal of probability |
Volume | 20 |
DOIs | |
Publication status | Published - Sept 2015 |
Externally published | Yes |
Fingerprint
Dive into the research topics of 'Concentration inequalities for Markov chains by Marton couplings and spectral methods'. Together they form a unique fingerprint.Profiles
-
Daniel Paulin
- School of Mathematics - Lecturer in Statistics and Data Science
Person: Academic: Research Active (Teaching)