Difference between upper and lower tails of multiplicative Chernoff bounds

Question

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?

Answer 1

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

Answer 2

The following intuition builds on the previous answer by user79365.

Suppose we fix $\delta$, and consider the case where $\mu$ is small (close to 0). Consider what this probability distribution would look like. The probability mass is more concentrated below the mean, since $\mu$ is close to 0. Therefore the same fixed $\delta mu$ deviation below the mean would be a rarer event than above. In this case the bounds do make sense.

Now consider the complementary case when $\mu$ is close to $\max (X)$. We can even take $p' = 1-p.$ It seems like we should get the same argument now for a deviation above $\mu$ with $\delta$ still fixed as before. However, $\mu$ is now much larger. So $\delta \mu$ is much larger. That is we consider much larger deviations from $\mu$ in this complementary case, so, it is believable that the previous bounds from the case where $\mu$ is small still hold, and they do.

So the lack of symmetry of the bounds boils down to the multiplicative effect of $\delta$ on $\mu$.

Answer 3

The question is targeted towards the multiplicative Chernoff bounds for th tails of distribution. I do not claim to have solved the problem but I can provide a better reference on how to do it:

Five Proofs of Chernoff’s Bound with Applications by Wolfgang Mulzer.

The advance to the already mentioned answers and proofs is that this source has the restriction of the question to the multiplicative cases of the upper tail and lower tail. This is really proof and honors the scientific history of the problems in the question.

I am able to give another link wherein there is a set formulas for working this through for more interesting distributions with the attributve multiplicative: CumulantGeneratingFunction.

This provides some impression on the relation of the surfaces under consideration:

.

Yellow is $\frac{1}{2}$. Blue is $\frac{1}{3}$.