Let $S_n = \sum_{i=1}^n X_i$ with $X_i$ iid $\exp(1)$ random variables. Fix a small $\epsilon >0$. What is the optimal bound for $P(S_n \leq \epsilon n)$?
The best bound I know starts by noting that $S_n \leq \epsilon n$ implies at least $n/2$ of the $X_i$ are smaller than $2 \epsilon$. We can compute $$P(X_1 \leq 2 \epsilon) = 1- e^{- 2 \epsilon} \approx - 2\epsilon.$$ Using the bound $\binom n {n/2} \leq 2^n$ we then have $$P( S_n \leq \epsilon n) \leq 2^n ( 2 \epsilon )^{n/2}) = (2 \sqrt {2 \epsilon} )^n.$$
This feels sub-optimal. Is there a better concentration inequality that can be applied?
Large deviations can take care of this. Fix $\theta >0$. The moment generating function of an $\exp(1)$-r.v. is $$E e^{-\theta X_1} = \frac{1}{1+ \theta}.$$ By Markov's inequality $$P(S_n \leq \epsilon n) = P( e^{- \theta S_n } \geq e^{-\theta \epsilon n} ) \leq \left( \frac{1} {1+\theta}\right)^n e^{\theta \epsilon n}.$$ The term $(1/(1+\theta))e^{\theta \epsilon}$ is minimized at $\theta_0 = \frac 1 \epsilon -1$. Plug this value in and we get $$P(S_n \leq \epsilon n) \leq (\epsilon e^{ 1- \epsilon})^n\leq (e\epsilon) ^n.$$