Concentration Inequalities for Dependent Random Variables

Abstract

This thesis contains contributions to the theory of concentration inequalities, in particular, concentration inequalities for dependent random variables. In addition, a new concept of spectral gap for non-reversible Markov chains, called pseudo spectral gap, is introduced. We consider Markov chains, stationary distributions of Markov chains (including the case of dependent random variables satisfying the Dobrushin condition), and locally dependent random variables. In each of these cases, we prove new concentration inequalities that improve considerably those in the literature. In the case of Markov chains, we prove concentration inequalities that are only the mixing time of the chain times weaker than those for independent random variables. In the case of stationary distributions of Markov chains, we show that Lipschitz functions are highly concentrated for distributions arising from fast mixing chains, if the chain has small step sizes. For locally dependent random variables, we prove concentration inequalities under several different types of local dependence.