Why is $\sum_{m=0}^{\lfloor xs\rfloor} 2 \binom{s}{m} p^m (1-p)^{s-m} \leq 2\exp{\left(-\frac{2(\lfloor xs\rfloor - sp)^2}{s}\right)}$

Question

I am trying to understand few of the mathematical steps I have encountered in a paper, there are two of them

(a) $\sum_{m=0}^{\lfloor xs\rfloor} 2 \binom{s}{m} p^m (1-p)^{s-m} \leq 2\exp{\left(-\frac{2(\lfloor xs\rfloor - sp)^2}{s}\right)}$

(b) $\sum_{m= \lfloor xs \rfloor + 1}^s \left(\frac{p}{x}\right)^m \left(\frac{1-p}{1-x}\right)^{s-m} \leq p\exp{\left(-sd(x,p)\right)}$, where $d(a,b) = a\log{\frac{a}{b}} + (1-a)\log{\frac{1-a}{1-b}}$.

I have searched and tried a lot but could not figure out it. If some one can help or point out some relevant reference it would be helpful.

Answer 1

Note that the sum in (a) is $2\cdot \mathbb{P}\{X\leqslant x\}$ for $X\sim \mathrm{Bin}(s,p)$. In view of this, (a) is a consequence of Hoeffding's inequality. (Recall that a binomial random variable is a sum of iid Bernoulli random variables.)