= Solution
The <Hoeffding lemma> for a <Bernoulli distribution> variable gives $\mathbb E e^{s(B-p)}\leq e^{s^2/8}$. Multiplication of the <moment-generating functions> of the <independent random variables> gives $\mathbb E e^{s(X-np)}\leq e^{ns^2/8}$. Thus the centered count is a <sub-Gaussian random variable> with variance proxy $n/4$. The <Chernoff bound>, optimized at $s=4t/n$, gives
$$
\boxed{\mathbb P(X-np>t)\leq e^{-2t^2/n},\qquad t>0.}
$$
The same estimate holds for the lower tail by applying the <Chernoff bound> to $-(X-np)$. No <independence> between different bin counts is needed.
Back to article page
