# Concentration of sum of concentrated random variables

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)

• The worst case scenario seems to be when all variables are just identical (so you have $nX$ instead of $X$ with obvious rescaled concentration bounds). Will that be good enough for you or you want more? (In the latter case some information about the nature of dependence would be necessary). It would also be nice to tell us a bit more about the setup: are your variables identically distributed, for instance? Jan 29 '20 at 21:10
• Thank you for the response. I have updated the question. I also updated it to make clear that I care about the relative deviations. This means that in the case of identical random variables, I can just get bound on one of them and the same bound applies to their sum. Jan 30 '20 at 8:56
• You need some quantitative control on how the dependence between your variables. As @fedja's example shows, without such assumptions you get trivialities. Jan 30 '20 at 9:01
• The central proposition is still in the middle of a complicated sentence. It would help to isolate and state that proposition in a self-contained paragraph. Then the comments about what to expect can go in a different paragraph. It would also help to clarify which of the four questions indicated with question marks is the key question. Jan 30 '20 at 9:25
• This still qualifies as “needs details or clarity”, so I’ll stop commenting. Jan 30 '20 at 9:34

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$$.