# Chernoff bound when we only have upper bound of expectation

If $X$ is a sum of i.i.d. random variables taking values in $\{0,1\}$ and $E[X]=\mu$, the Chernoff bound tells us that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$

for all $0<\delta<1$.

If $E[X]\leq\mu$ instead, does there exist a constant $c$ such that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-c\delta^2\mu}$$

for all $0<\delta<1$?

(This question is related, but the answer there doesn't help.)

• What is $X$? You need more information about the random variable. – Louis Apr 28 '15 at 8:17
• @Louis It's a Chernoff bound so $X$ is a sum of i.i.d. random variables. I edited the question to clarify. – David Richerby Apr 28 '15 at 9:22
• How is this a computer science question? What have you tried an where did you get stuck? – Raphael Apr 28 '15 at 10:51
• @Raphael, it isn't purely about CS, but seeing as Chernoff bounds are common in analysis of randomized algorithms it isn't entirely off topic. – Nicholas Mancuso Apr 30 '15 at 23:17
• @NicholasMancuso That's not a very good argument; if all tools we use in CS were ontopic here, we'd have a weird scope. That said, if the question did make any connection to CS I'd be happy; but it does not. – Raphael May 1 '15 at 12:29

Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved. A relatively standard form of this kind of tail bound would assume that $$X = X_1 + \cdots + X_n$$ with all $X_i$ independent, discrete, supported in $[-1,1]$, with mean $\mu_i = 0$, variance $\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]} \sigma^2_i$ is the variance of $X$ and $\lambda\in[0,2\sigma]$. (Here is a proof by Van Vu.)
All Chernoff bounds are based on applying Markov's inequality to $e^{tX}$ to get that $\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 then optimize $t$. We can do the MGF 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 $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, $$\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 that $$\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).
Now let's assume that $\mu_i\le 0$ (instead of $= 0$ as before) and otherwise the same set of hypotheses. 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 $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 same tail bound as before.
Finally, note you always have $\sigma^2_i\le 4$, so $\sigma^2\le 4n$.
• @D.W., isn't that implicit from "centered"? That is, $X_i$ is centered in [-1, 1], => $E[X_i] = 0$. – Nicholas Mancuso Apr 30 '15 at 22:48