# 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? – fedja Jan 29 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. – user2316602 Jan 30 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. – Aryeh Kontorovich Jan 30 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. – Matt F. Jan 30 at 9:25
• This still qualifies as “needs details or clarity”, so I’ll stop commenting. – Matt F. Jan 30 at 9:34

## 1 Answer

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.

• This is an amazing answer! I have had this question a couple of times before, now I know the answer. – user2316602 Jan 30 at 17:04