Poisson and Normal Tail For concentration inequalities, there are two types of tail probability,

*

*Normal tail, for example Hoeffding's inequality gives for sum of independent random variables taking values in $[a,b]$, for any $t > 0$, we have

$$P(S_N - ES_N) > t) \leq \exp \left\{-\frac{2t^2}{N(b-a)^2}\right\}$$


*Poisson tail, for example Chernoff's inequality, gives a tail probability for sum of independent Bernoulli random variables,

$$ P(S_N > t) \leq e^{-\mu} \left(\frac{e\mu}{t}\right)^t $$
if we have $\mu = ES_N$.
My questions is, it's usually claimed that Chernoff's bound is sharper in this case, but isn't $e^{-t^2} = o(t^{-t})$? If not, could someone please give me an intuition why we need to consider the Poission tail?
 A: Long story short: it is not enough to look only at the dependency on $t$.

I consider the following setting: $X_1,\ldots,X_N$ are independent random variables (not necessarily identically distributed) taking values in $[0,1]$. You can check that with a change of variable, your version of Chernoff's inequality is equivalent to
$$P(S_N-\mu > t)\le \exp\left(t-(\mu+t)\log\left(1+\frac{t}{\mu}\right)\right).$$
Plugging in the inequality $(1+x)\log(1+x)-x\ge \frac{x^2}{2+2x/3}$ for $x\ge 0$, it implies that
$$P(S_N-\mu > t)\le \exp\left(-\frac{t^2}{2\mu+\frac{2}{3}t}\right).$$

*

*When $t\le 3\mu$, we get an upper bound of $\exp(-Ct^2/\mu)$.

*When $t>3\mu$, we get an upper bound of $\exp(-Ct)$.

On the other hand, Hoeffding's inequality says that
$$P(S_N-\mu > t)\le \exp\left(-\frac{2t^2}{n}\right).$$
Now note that $\mu\le n$ and we are only interested in $0\le t\le n$ (which implies that $t\ge t^2/n$). Therefore, as long as you do not care about the constants inside the exponential, Chernoff's inequality is always at least as good as Hoeffding's. Furthermore, it can be much better in the regime $\mu\ll n$.
