I'm just trying to follow the proof of Chernoff Bound in this paper

First problem

$$\Pr [|X| \geq \lambda \sigma ] \leq 2 e^{\frac{-\lambda^2}{4}} $$ is the same as the following,

$$\Pr [X \geq \lambda \sigma ] \leq e^{\frac{-\lambda^2}{4}} $$

I tried by squaring all the sides, but it seems too far from the right answer ..

Second problem

when optimizing, taken $t = \lambda/2\sigma$ starting from $\Pr[X \geq \lambda\sigma] \leq e^{t\sigma (t \sigma - \lambda)}$ to get $\Pr[X \geq \lambda\sigma] \leq e^{-\lambda^2 /4}$. This is how I tried as following, $$e^{t\sigma (t \sigma - \lambda)} = e^{(\lambda/2\sigma)\sigma ((\lambda/2\sigma) \sigma - \lambda)} = e^{(\lambda/2) ((\lambda/2) - \lambda)}$$ from this point I can go further, but it is far from the right answer.

I hope get hint for these inequality and equality..


The argumentation is symmetric for $$Pr[−X ≥ λσ].$$

says the author at the beginning of the proof. Then presents the proof for positive $X$.

As far as minimizing

$$e^{t\sigma (t \sigma - \lambda)}=e^{\sigma^2t^2-t\sigma\lambda}\tag 1$$

in $t$. Let's differentiate $(1)$ with respect to $t$ and set the derivative equal to zero:

$$\frac d{dt}e^{\sigma^2t^2-t\sigma\lambda}=(2t\sigma^2-\lambda\sigma)e^{\sigma^2t^2-t\sigma\lambda}=0.$$

The extremum is taken at


Substituting this value back to $(1)$ we get


which is the minimum of the upper bound considered.

  • $\begingroup$ Ahh, Exactly right, I just remember after your post that we can use calculus to solve "optimization problems", It's simple and awesome answer. Thank you so much $\endgroup$ – user777 Sep 14 '15 at 10:19

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.