Hoeffding's Inequality for Sums of Dependent Random Variables

We provide a systematic approach to deal with the following problem. Let$X_1,\ldots,X_n$ be, possibly dependent, $[0,1]$-valued random variables. Whatis a sharp upper bound on the probability that their sum is significantlylarger than their mean? In the case of independent random variables, afundamental tool for bounding such probabilities is devised by WassilyHoeffding. In this paper we consider analogues of Hoeffding's result for sumsof dependent random variables for which we have certain information on theirdependency structure. We prove a result that yields concentration inequalitiesfor several notions of weak dependence between random variables. Additionally,we obtain a new concentration inequality for sums of, possibly dependent,$[0,1]$-valued random variables, $X_1,\ldots,X_n$, that satisfy the followingcondition: there exist constants $\gamma \in (0,1)$ and $\delta\in (0,1]$ suchthat for every subset $A\subseteq \{1,\ldots,n\}$ we have$\mathbb{E}\left[\prod_{i\in A} X_i \prod_{i\notin A}(1-X_i) \right]\leq\gamma^{|A|} \delta^{n-|A|}$, where $|A|$ denotes the cardinality of $A$. Ourapproach applies to several sums of weakly dependent random variables such assums of martingale difference sequences, sums of $k$-wise independent randomvariables and $U$-statistics. Finally, we discuss some applications to thetheory of random graphs.

Publication year:2017