Rosenthal-type inequalities for linear statistics of Markov chains

Probability and moment inequalities for sums of random variables are of paramount importance in the complexity analysis of numerous stochastic approximation algorithms or finite-time analysis of Monte Carlo estimators; see [20], [10], and references therein. The main focus in this area has been on concentration inequalities for independent random variable sums or martingale difference sequences; see e.g. in [4, 36]. However, the study of concentration inequalities for additive Markov chain functions is still relatively underdeveloped. For the technically simple case of uniformly ergodic Markov chains, there is extensive work on Hoeffding-and Bernstein-like inequalities as found in [23, 34, 20, 38]. Nevertheless, the application of these results may be difficult due to a lack of quantitative data or the substitution of asymptotic variance of the chain by surrogates; see Section 2.1 for relevant definitions. The present work aims to fill this gap by extending Rosenthal-and Bernstein-type inequalities to Markov chains which converge geometrically fast to a unique invariant distribution, with an explicit emphasis on the mixing time of the underlying Markov chain. An important tool for establishing deviation bounds for sums of random variables is based on moment inequalities.