Concentration inequalities for Markov chains by Marton couplings and spectral methods

2012/12/10 by Daniel Paulin, Paulin, Daniel · 13 citations
Mathematics · #Markov Chains and Monte Carlo Methods #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1212.2015

Abstract

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.

Cited by

• Decorated graphons for temporal network estimation
• Enhancing Node-Level Graph Domain Adaptation by Alleviating Local Dependency
• Large Deviation inequalities for sums of positive correlated variables with clustering
• Statistical analysis of Inverse Entropy-regularized Reinforcement Learning
• Worst-case mixing estimates for Brownian motion with semipermeable barriers
• Non Asymptotic Mixing Time Analysis of Non-Reversible Markov Chains
• Multi-Objective min-max Online Convex Optimization
• PAC-Bayesian Reinforcement Learning Trains Generalizable Policies
• Prediction-Powered Communication with Distortion Guarantees
• On the complexity of standard and waste-free SMC samplers
• Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
• Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments
• Efficient Bayesian Inference for Discretely Observed Continuous Time Markov Chains

Related

• Spectral gap of nonreversible Markov chains
• General mixing time bounds for finite Markov chains via the absolute spectral gap
• Toy examples for effective concentration bounds
• Rosenthal-type inequalities for linear statistics of Markov chains
• Exponential Concentration Inequalities for Additive Functionals of Markov Chains