# Inequality and equality in Chernoff Bound proof.

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

$$t=\frac{\lambda}{2\sigma}.$$

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

$$e^{-\frac{\lambda^2}4}$$

which is the minimum of the upper bound considered.

• 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 – user777 Sep 14 '15 at 10:19