Upper bound for $\sum_{i = 0}^{k-1} {n \choose i} (1 - \varepsilon)^i\varepsilon^{n-i}$

Question

What is tight upper and lower bound for following expression where $0 < \varepsilon < 1$ and $1\leq k \leq n$.

$\sum_{i = 0}^{k-1} {n \choose i} (1 - \varepsilon)^i\varepsilon^{n-i}$

Answer 1

Let $X \sim bin(n,\varepsilon)$ then $$ \sum_{i = 0}^{k-1} {n \choose i} (1 - \varepsilon)^i\varepsilon^{n-i} =\mathbb{P}(X\leq k-1) = 1-\mathbb{P}(X\geq k-1). $$ Usually, a common approach is to use the Chernoff inequalities, which provides pretty good upper and lower bounds.

Answer 2

For a simpler solution, use the appximation to $\binom{n}{k} = \frac{n^{k}}{k!}$, then the summand becomes $$ (1-\varepsilon)^n \frac{n^{i}\varepsilon^{i}(1-\varepsilon)^{-i}}{i!} $$ then the upper bound can be easily found by using partial Taylor series expansion for the exponential function: $$ S_{n} \leq(1-\varepsilon)^{n}\exp\bigg(\frac{n \varepsilon}{1-\varepsilon}\bigg) $$