Concentration of sum of concentrated random variables

Question

I have a sum of positive random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this?

Namely, I would expect that for the number of random variables going to infinity (and maybe even if not) if I have upper bound on the probability that $(1-\epsilon)E[X_i] \leq X_i \leq (1+\epsilon)E[X_i]$ then the worst of these bounds also holds for the sum. Is this so? (In the sense that the sum would be with given probability between $1-\epsilon$ and $1+\epsilon$ multiple of its expectation).

I could estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)

Answer 1

There is a bad news and a good news. The bad one is that if you have no information other than that the probability of the $\varepsilon$-deviation is at most $p$ for each variable, then you can hardly do anything better than the union bound. Indeed, consider the random variables $X_i$ that are exactly $E[X_i]$ with probability $1-p$ and something else (say, with continuous distribution) with probability $p$. Then you have your $\varepsilon$-concentration for every $\varepsilon>0$, but, of course, the only estimate you may have for the probability that the sum hits the sum of expectations exactly is the union bound. The good news is that if you obtained your concentration bounds by the same method, i.e., by estimating $$ E\Phi\left(\frac{X_i-EX_i}{EX_i}\right)\le C $$ with the same convex function $\Phi$ (Chernov, for instance, corresponds to $\Phi(x)=e^{Ax}+e^{-Ax}$), then, by the Jensen inequality, you have $$ E\Phi\left(\frac{X-EX}{EX}\right)\le C $$ for the sum $X=\sum_i X_i$.

If you have obtained your concentration bounds by different methods for different variables or if you used different convex functions with different right hand sides, then the story gets more complicated, but then you'll need to tell us more to have a meaningful discussion.

Answer 2

I did some more digging and found an answer. In many cases, only the bounds on deviations suffice to get the bounds I wanted on the sum.

The answer is the theory of sub-gaussian random variables and, more specifically, the theorem on sums of (dependent) sub-gaussians.

To learn more, I can recommend these lecture notes as well as a (sub)chapter on this topic in the book "High-Dimensional Probability"