First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The question itself is as follows. Suppose I have a sum $X=\sum_{i=1}^{n}{X_i}$ of mutually independent indicator random variables. Suppose also that I have an upper bound $\mu$ on the expected value $E[X]$ of $X$, but that I don't know the exact value of $E[X]$. Now, for some value $0 \lt \delta \le 1$, I wish to apply a chernoff bound in such a way, that I will receive the inequality $Pr[X \ge (1+\delta)E[X]] \le e^{-c \cdot \mu \cdot \delta^2}$, for some appropriate constant $c$.
In short, I want to be able to derive a useful upper bound on the probability that the value of $X$ is at least $(1+\delta)E[X]$, that uses the fact that $E[X] \le \mu$. If it held that $E[X] = \mu$, this would be straightforward, however in this case, there seems to be some difficulty showing this using the regular multiplicative error Chernoff bounds and standard algebraic operations. It does seem to make sense though, that this also holds in this case as well. That is, that the probability of the event $X \ge (1 + \delta)E[X]$ is no "worse" (no higher) than in the case where $E[X] = \mu$.


There's no useful bound. You need a lower bound on $E[X]$, not an upper bound.

If $E[X]=0$, then $\Pr[X \ge (1+\delta) E[X]] = 1$, so there is no useful upper bound on $\Pr[X \ge (1+\delta) E[X]]$ if all you know is an upper bound on $E[X]$. (That probability could be as large as 1, so all you can say is $\Pr[X \ge (1+\delta) E[X]] \le 1$.)

Perhaps you mean that you have a lower bound on $E[X]$. A standard Chernoff bound says that

$$\Pr[X \ge (1+\delta) E[X]] \le e^{-\delta^2 E[X]/3}.$$

Suppose now you have a lower bound $\ell$ on $E[X]$, i.e., $E[X] \ge \ell$. Then it follows that

$$\Pr[X \ge (1+\delta) E[X]] \le e^{-\delta^2 E[X]/3} \le e^{-\delta^2 \ell/3}.$$

This gives you an upper bound on that probability, if you know a lower bound on $E[X]$.


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.