Concentration inequalities for Markov processes via coupling

Abstract

We obtain moment and Gaussian bounds for general Lipschitz functions evaluated along the sample path of a Markov chain. We treat Markov chains on general (possibly unbounded) state spaces via a coupling method. If the first moment of the coupling time exists, then we obtain a variance inequality. If a moment of order 1+epsilon of the coupling time exists, then depending on the behavior of the stationary distribution, we obtain higher moment bounds. This immediately implies polynomial concentration inequalities. In the case that a moment of order 1+epsilon is finite uniformly in the starting point of the coupling, we obtain a Gaussian bound. We illustrate the general results with house of cards processes, in which both uniform and non-uniform behavior of moments of the coupling time can occur.

Electron. J. Probab. (2009). A little mistake, indicated by A. Guillin, was corrected in Theorem 7.1, see Remark 7.1

References in corpus (3)

• Transportation cost-information inequalities and applications to random dynamical systems and diffusions
• Obtaining Measure Concentration from Markov Contraction
• A probabilistic approach to Zhang's sandpile model

Cited by in corpus (1)

• Informational Confidence Bounds for Self-Normalized Averages and Applications