Concentration inequalities for dependent Random variables via the martingale method

Abstract

The martingale method is used to establish concentration inequalities for a class of dependent random sequences on a countable state space, with the constants in the inequalities expressed in terms of certain mixing coefficients. Along the way, bounds are obtained on martingale differences associated with the random sequences, which may be of independent interest. As applications of the main result, concentration inequalities are also derived for inhomogeneous Markov chains and hidden Markov chains, and an extremal property associated with their martingale difference bounds is established. This work complements and generalizes certain concentration inequalities obtained by Marton and Samson, while also providing different proofs of some known results.

Published in at http://dx.doi.org/10.1214/07-AOP384 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Measure concentration for Euclidean distance in the case of dependent random variables
• Measure Concentration of Hidden Markov Processes
• Measure Concentration of Markov Tree Processes

Cited by in corpus (31)

• Concentration in unbounded metric spaces and algorithmic stability
• Simpler PAC-Bayesian Bounds for Hostile Data
• Hashing-Accelerated Graph Neural Networks for Link Prediction
• Chromatic PAC-Bayes Bounds for Non-IID Data: Applications to Ranking and Stationary $\beta$-Mixing Processes
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• Hoeffding's lemma for Markov Chains and its applications to statistical learning
• Consistent structure estimation of exponential-family random graph models with block structure
• Training Input-Output Recurrent Neural Networks through Spectral Methods
• Randomized maximum-contrast selection: subagging for large-scale regression
• Learning in Discounted-cost and Average-cost Mean-field Games
• Exponential inequalities for nonstationary Markov Chains
• Exponential Concentration Inequalities for Additive Functionals of Markov Chains
• Hoeffding's inequality for sums of weakly dependent random variables
• Theoretical Analysis of Binary Masks in Snapshot Compressive Imaging Systems
• Decision-Aware Conditional GANs for Time Series Data
• Optimal Gaussian concentration bounds for stochastic chains of unbounded memory
• Dependency-dependent Bounds for Sums of Dependent Random Variables
• Weak transport inequalities and applications to exponential inequalities and oracle inequalities
• Learning Markov models via low-rank optimization
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards
• Model-Free Change Point Detection for Mixing Processes
• Concentration inequalities using higher moments information
• Generalization bounds for learning under graph-dependence: A survey
• When Janson meets McDiarmid: Bounded difference inequalities under graph-dependence
• Concentration of Broadcast Models on Trees
• Deviation bound for non-causal machine learning
• PAC-Learning Uniform Ergodic Communicative Networks
• Multi-fidelity Stability for Graph Representation Learning
• Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity
• Estimating the Mixing Coefficients of Geometrically Ergodic Markov Processes