Chernoff bound for independent bernoulli trials

The function $h(u)=\exp (u)-1-u$ is zero at zero and has derivative $\exp (u)-1$, nonnegative for $u\ge 0$ and nonpositive for $u\le 0$. On each compact interval between zero and u it is smooth, so F6 proves $h(u)\ge 0$ for either sign of u. Thus $1+u\le \exp (u)$ for every real u.

Functions of distinct independent variables remain mutually independent here: for each prescribed transformed value, sum the original joint probabilities over its finite preimage; the product factorization distributes over these finite sums. Consequently F2 and exponential addition give, for every real $\lambda$, $\mathbb{E}{e}^{\lambda S}={\prod }_i(1+p_i(e^{\lambda }-1))\le {\prod }_i{e}^{p_i(e^{\lambda }-1)}=e^{\mu (e^{\lambda }-1)}\mathrm{.}$ Every factor before the inequality is positive, even when $p_i=0$ or 1, so multiplying the inequalities from step 1.1 preserves order.

For $\mu >0,\delta >0$, Markov with $\lambda =\log (1+\delta )>0$ bounds the upper-tail probability by $\exp (\mu (e^{\lambda }-1)-\lambda (1+\delta )\mu )$, which is exactly the upper displayed expression. For $0<\delta <1$, take $\lambda =\log (1-\delta )<0$; then $S\le (1-\delta )\mu$ implies $e^{\lambda S}\ge e^{\lambda (1-\delta )\mu }$. Markov with this positive threshold gives the lower displayed expression. At $\delta =0$ both rate expressions are zero and the assertion is just a probability at most one; no positive exponential parameter is needed.

On $[0,1]$ set $a(u)=\log (1+u)-2u\mathrm{/}(2+u)$. Its derivative is $u^2\mathrm{/}((1+u)(2+u{)}^2)\ge 0$ and $a(0)=0$, hence $\log (1+u)\ge 2u\mathrm{/}(2+u)\ge 2u\mathrm{/}3$. Therefore the derivative of $(1+u)\log (1+u)-u-u^2\mathrm{/}3$ is nonnegative and its value at zero is zero. For $0\le u<1$, the derivative of $-\log (1-u)-u$ is $u\mathrm{/}(1-u)\ge 0$ and its value at zero is zero. It follows that the derivative of $u+(1-u)\log (1-u)-u^2\mathrm{/}2$ is nonnegative, with zero initial value. All denominators and logarithm arguments are positive on the compact intervals used. F6 proves the rate bounds $u^2\mathrm{/}3$ and $u^2\mathrm{/}2$. Substitution in step 3.1 gives the simplified tails away from the lower endpoint $u=1$.

At $\delta =1$, independence gives $\mathbb{P}(S=0)={\prod }_i(1-p_i)\le e^{-\mu }$ by step 1.1, including a zero factor when some $p_i=1$. This also implies the weaker lower bound $e^{-\mu \mathrm{/}2}$. If $\mu =0$, every $p_i=0$, so each event $X_i=1$ has mass zero; summing the finitely many masses shows $S=0$ almost surely. Both weak multiplicative thresholds then have probability one, matching their bounds one. For $N=0$ this holds identically by the empty-sum convention. Finally ${\mathbf{1}}_{A\cup B}\le {\mathbf{1}}_A+{\mathbf{1}}_B$ and finite summation give the union bound. Applying it to upper and lower deviations and using $e^{-\mu {\delta }^2\mathrm{/}2}\le e^{-\mu {\delta }^2\mathrm{/}3}$ gives the stated two-sided bound, also at $\delta =0$.

For a single Bernoulli(p), put $A(\lambda )=1-p+p{e}^{\lambda }>0$ and $g(\lambda )=\log A(\lambda )-p\lambda$. Direct differentiation gives $g(0)=g^{\mathrm{\prime }}(0)=0$, $g^{\mathrm{\prime }}=q-p$ and $g^{\mathrm{\prime }\mathrm{\prime }}=q(1-q)$, where $q=p{e}^{\lambda }\mathrm{/}A(\lambda )\in [0,1]$. Thus $g^{\mathrm{\prime }\mathrm{\prime }}\le 1\mathrm{/}4$, since $q(1-q)=1\mathrm{/}4-(q-1\mathrm{/}2{)}^2$. The smooth function $v(\lambda )=g(\lambda )-{\lambda }^2\mathrm{/}8$ has $v^{\mathrm{\prime }\mathrm{\prime }}\le 0$ and $v(0)=v^{\mathrm{\prime }}(0)=0$. Apply F6 first to v' and then to v on either side of zero: v' is nonincreasing, so v is nondecreasing up to zero and nonincreasing after zero. Hence $g(\lambda )\le {\lambda }^2\mathrm{/}8$ for all real $\lambda$, including both deterministic p endpoints. Exponentiating yields $\mathbb{E}{e}^{\lambda (X-p)}\le e^{{\lambda }^2\mathrm{/}8}$.

Factor the centered exponential expectation using the independence justification of step 2.1 to obtain $\mathbb{E}{e}^{\lambda (S-\mu )}\le e^{N{\lambda }^2\mathrm{/}8}$. For $t>0$, Markov with $\lambda =4t\mathrm{/}N$ bounds $\mathbb{P}(S-\mu \ge t)$ by $e^{-2t^2\mathrm{/}N}$. Apply the same estimate with $\lambda =-4t\mathrm{/}N$ to $S-\mu \le -t$. The union bound from step 5.1 gives the additive assertion. At t=0 its right side is two and is trivially an upper bound. Division by N is licensed by the additive assertion's hypothesis $N>0$; nothing is asserted from that formula at N=0.