We use a few cookies

Essential cookies keep the library working. With your permission, we'd also like to use analytics to see what's useful and improve the experience. Read our Privacy Policy or Cookie Policy.

Skip to main content
Home/e-Resources/Mathematics/Concentration inequalities for Markov chains by Marton couplings and spectral methods
PeriodicalsMathematics

Concentration inequalities for Markov chains by Marton couplings and spectral methods

Checking your access to this record.

Abstract & Overview

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.

Cite this record

Daniel Paulin (2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20(none). https://doi.org/10.1214/ejp.v20-4039

Copy in another style

Paulin, D. (2015). Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20(none). https://doi.org/10.1214/ejp.v20-4039
Author names are used as deposited, so check their order before you submit.

Metadata is harvested from open-access indexes and can be incomplete. Check a citation against the published version before relying on it — see our open access & attribution policy.