If you have some information about the first two moments of the summandsYes, youwe can get something usefula bound like this. For exampleTo see why, we will need to look a fairlylittle more closely at how Chernoff bounds are proved. A relatively standard form of the Chernoffthis kind of tail bound would say something like ifassume that $$ X = X_1 + \cdots + X_n $$ with all $X_i$ independent, discrete, supported in $[-1,1]$, centeredwith mean (i.e.$\mu_i = 0$, variance $\mathbb{E}[X_i]=0$), and independent, then$\sigma_i^2$. The resulting tail bound ends up being that: $$\operatorname{Pr}[X > \lambda\sigma]\le e^{-\lambda^2/4}$$ where $\sigma^2 = \sum_{i\in [n]} \operatorname{Var}[X_i]$$\sigma^2 = \sum_{i\in [n]} \sigma^2_i$ is the variance of $X$ and $\lambda\in[0,2\sigma]$. Here (Here is a proof by Van Vu.)
If, insteadI'm more or less going to first reproduce the proof, so you can get an idea of why decreasing the expectation turns out to be ok.
All Chernoff bounds are willingbased on applying Markov's inequality to assume$e^{tX}$ to get that $\operatorname{E}[X_i]\le 0$$\operatorname{Pr}[X > \lambda\sigma]\le \mathbb{E}[e^{tX}]e^{-t\lambda\sigma}$. So the general method is to work out $\mathbb{E}[e^{tX}]$ and replacethen optimize $\sigma^2$ with$t$. We can do the sumMGF computation a little differently from the link, namely as $$\mathbb{E}[e^{tX}] = \prod_{i\in [n]}\mathbb{E}[e^{tX_i}] \le \prod_{i\in [n]}\mathbb{E}[(1 + tX_i + t^2X_i^2)]$$ where we first used independence of the $\operatorname{E}[X_i^2]$$X_i$ and then $e^x\le 1 + x + x^2$ for $x\in [0,1]$. Under the hypotheses we started with and linearity of expectation, you'll $$\mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t^2\sigma_i^2\le e^{t^2\sigma_i^2}$$ so we get a reasonably nice looking bound by just tracing through the argumentthat $$ \operatorname{Pr}[X > \lambda\sigma] \le e^{t^2\sigma^2 - t\lambda\sigma}$$ With $t = \lambda/2\sigma$ this is what we wanted (and since $t\in[0,1]$, all the inequalities we used are valid).
Also, this will explain why you can't just infer a general answerNow let's assume that $\mu_i\le 0$ (instead of $= 0$ as before) and otherwise the same set of hypotheses. The natural units Returning to the MGF computation, we get $$ \mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t\mu_i + t^2\mathbb{E}[X_i^2] = 1 + t\mu_i + t^2\sigma_i^2 + t^2\mu_i^2 $$ Using that $x^2 + x < 0$ for tail bounds are standard deviations from$x\in (-1,0)$, this implies that $$ \mathbb{E}[(1 + tX_i + t^2X_i^2)] \le 1 + t^2\sigma_i^2 $$ and so we get the meansame tail bound as before. In this case
Finally, ifnote you move the mean away from zeroalways have $\sigma^2_i\le 4$, thenso $\operatorname{E}[X_i^2]$ isn't quite the variance any more$\sigma^2\le 4n$.
