Tail bound for finite sums of independent signs

For one sign variable $\xi$ with $p=\mathbb{P}(\xi =+1)$ and $\mu =\mathbb{E}\xi =2p-1$, put $\psi (s)=\log \mathbb{E}{e}^{s(\xi -\mu )}$. The two-point formula gives $\psi (s)=\log (p{e}^s+(1-p)e^{-s})-s\mu$, so $\psi (0)={\psi }^{\mathrm{\prime }}(0)=0$ and ${\psi }^{\mathrm{\prime }\mathrm{\prime }}(s)=\frac{4p(1-p)}{(p{e}^s+(1-p)e^{-s}{)}^2}\le 1$. The inequality follows from $4ab\le (a+b{)}^2$ with $a=p{e}^s$ and $b=(1-p)e^{-s}$. Integrating the second-derivative bound twice from $0$ to $s$, in either direction, gives $\psi (s)\le s^2\mathrm{/}2$ for every real $s$; if $p=0$ or $p=1$, $\psi$ is identically zero and the same bound holds.

Apply step 1.1 to each ${\xi }_i$ with $s=\lambda c_i$. The functions $x\mapsto e^{\lambda c_i(x-\mathbb{E}{\xi }_i)}$ are nonnegative Borel functions, so [F6] factors their expectations; [F4] combines the exponentials. Thus $\mathbb{E}{e}^{\lambda S}={\prod }_{i=1}^m\mathbb{E}{e}^{\lambda c_i({\xi }_i-\mathbb{E}{\xi }_i)}\le \exp \text{\hspace{0.17em}⁣}\left(\frac{{\lambda }^2}{2}{\sum }_{i=1}^m{c}_i^2\right)=e^{{\lambda }^{2}V\mathrm{/}2}$ for every real $\lambda$.

Suppose $V>0$ and choose $\lambda =t\mathrm{/}V>0$. Markov's inequality [F3] applied to $e^{\lambda S}$ and the MGF bound in step 2.1 give $\mathbb{P}(S\ge t)\le e^{-\lambda t+{\lambda }^{2}V\mathrm{/}2}=e^{-t^2\mathrm{/}(2V)}$. Applying the same argument to $-S$ gives $\mathbb{P}(S\le -t)\le e^{-t^2\mathrm{/}(2V)}$.

By [F5], $\mathbb{P}(\mathrm{\mid }S\mathrm{\mid }\ge t)\le \mathbb{P}(S\ge t)+\mathbb{P}(S\le -t)$, which gives the stated two-sided bound from step 3.1. If $V=0$, every $c_i=0$, so $S=0$ almost surely; the empty-sum case is the same.