ProV Logo
0
Concentration inequalities for Markov ch...
Paulin, Daniel...

Free

Concentration inequalities for Markov chains by Marton couplings and spectral methods by Paulin, Daniel ( Author )
Lemonjar Open Access
Australian National University
26-07-2023
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.
-
Article
pdf
37.08 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1212.2015
Share this eBook