6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What is $X$? You need more information about the random variable. $\endgroup$ – Louis Apr 28 '15 at 8:17
  • $\begingroup$ @Louis It's a Chernoff bound so $X$ is a sum of i.i.d. random variables. I edited the question to clarify. $\endgroup$ – David Richerby Apr 28 '15 at 9:22
  • 1
    $\begingroup$ How is this a computer science question? What have you tried an where did you get stuck? $\endgroup$ – Raphael Apr 28 '15 at 10:51
  • 2
    $\begingroup$ @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. $\endgroup$ – Nicholas Mancuso Apr 30 '15 at 23:17
  • $\begingroup$ @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. $\endgroup$ – Raphael May 1 '15 at 12:29
5
$\begingroup$

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

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

$\endgroup$
  • 1
    $\begingroup$ @D.W., isn't that implicit from "centered"? That is, $X_i$ is centered in [-1, 1], => $E[X_i] = 0$. $\endgroup$ – Nicholas Mancuso Apr 30 '15 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.