Chernoff Bound for Binomial Distribution

1. Jul 31, 2015

S_David

Hello,

I've read in a paper that the following binomial distribution

$$\sum_{k=floor(N/2)+1}^N{N\choose k}\varepsilon^k(1-\varepsilon)^{N-k}$$

can be upper bounded using Chernoff bound by

$$e^{ floor(N/2)}\,\Phi(s_0)$$

where

$$\Phi(s)=\left(1-\varepsilon(1-e^s)\right)^N$$

and

$$floor(N/2)\,\Phi(s_0)=\frac{\partial}{\partial s}\left. \Phi(s)\right|_{s=s_0}$$

Could anyone explain to me how?

Thanks

2. Jul 31, 2015