Concentration inequalities for Markov chains by Marton couplings and spectral methods

By Daniel Paulin. 2012

317 citations recorded by the source corpus.

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.

Subfields: Applied Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/538310f0307915e989351f6e6116a991d1af602c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

1. Yuejie Chi
2. Ronald Ortner
3. Yuantao Gu
4. Yuxin Chen
5. Richard Nickl
6. Jakob Sohl
7. D. Chetverikov
8. Evarist Gin'e

In Statistics and Probability

1. Jakob Sohl
2. Yuejie Chi
3. Richard Nickl
4. Ronald Ortner
5. Yuxin Chen
6. Kolyan Ray
7. I. Castillo
8. Evarist Gin'e

Citations in the corpus

• Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, methodology): “3 Concentration of the Empirical Distribution We will also need the following results on the concentration of the empirical state distribution of Markov chains from [21].”
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, background): “Throughout this paper, we impose the following assumption [34].”
• Nonparametric Bayesian posterior contraction rates for discretely observed scalar diffusions (2015, background): “This is not an artefact of our concentration inequalities but corresponds precisely to the connection between mixing times of Markov chains and their spectral gap (see also [21]).”