Let $X_1,\dots,X_n$ be independent variables, $X_i$ having mean $\mu_i$ and variance $\sigma_i^2$. Let their sum $S = \sum_{i=1}^n X_i$. Of course, $S$ has mean $\lambda = \sum_{i=1}^n \mu_i$ and variance $\epsilon^2 = \sum_{i=1}^n \sigma_i^2$.

I was wondering if there are nice/simple tail bounds for $S$ in this case? (Edit: Another way to view this is asking for a rate of convergence to the Central Limit Theorem.) To make things easier feel free to assume all $\mu_i = \mu (= 0)$ and all $\sigma_i = \sigma$, or even that $X_i$ are identically distributed.

We can tail bound $S$ using Chebyshev's inequality: $\Pr[|S-\lambda| \geq k\epsilon] \leq \frac{1}{k^2}$.

  1. Can we get a better bound at all for $S$?
  2. In particular might it be possible to get a Chernoff-type exponential tail bound? If so, does $n$ need to be large (e.g. exponential in $\sigma_i$)?

One approach I thought of is to use Chebyshev on each $X_i$ separately, union bound the chance that any of them fail to satisfy this bound, then (with the remaining probability) they are bounded RVs and Chernoff applies. But it looks to me like this shouldn't work out (we need the bound to be on the order of $\sqrt{n}$ in order for the union bound to work, but then it's too big for the Chernoff bound to work).

Another is to find a distribution that has the heaviest possible tails for a given mean and variance, assume each $X_i$ is drawn from it, and just figure out a bound for this distribution. Is there any such distribution?

Other thoughts/approaches/references? Thanks!


1 Answer 1


This is only one idea for approaching the problem and not really the sort of answer I was looking for, but it looks like, if the variables have finite (and small-ish) third absolute moments, one approach is the Berry-Esseen theorem. Assume each $\mu_i = 0$ and let $\rho_i = \mathbb{E}|X_i|^3$. Then for all $x$,

$$ \Pr[S \leq x \epsilon] \leq \Phi(x) + C \frac{\sum_{i=1}^n \rho_i}{\epsilon^3} $$

where $\Phi(x)$ is the standard normal cdf.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .