I'm struggling with the intuition behind why Chernoff bounds differ in the upper and lower tails. That is, for the lower tail we have:
$$
Pr(X \le (1 – \delta)\mu)\ \ \le\ \ e^{-\frac{\mu\delta^2}{2}}
$$
Whereas for the upper tail:
$$
Pr(X \ge (1 + \delta)\mu)\ \ \le\ \ e^{-\frac{\mu\delta^2}{3}}
$$
Both bounds are found in roughly the same manner, so at a high level, why would they differ in value when we don't know that the distribution is necessarily asymmetric?
Best Answer
One way to see the lack of symmetry is to consider the extreme case $\delta = 1$. Then $P(X< (1-\delta)\mu)=0$ while $P(X> (1+\delta)\mu)$ may be positive. This (weakly) suggests that the first tail probability may be smaller. And the bounds conform to that expectation: $\exp(-\mu \delta^2/2)$ is less than $\exp(-\mu \delta^2/3)$.
Except that you have them switched around (cf. wikipedia, lecture notes).