Large deviation of Bernoulli random variables and applying Chernoff bound

Question

Let $X_1,X_2,..,X_n$ be i.i.d Bernoulli random variables with $P(X_1)=0.005$ and let $S_n:=X_1+...+X_n$. I need to:

• Evaluate the exact value of $P(S_{100} \geq 4)$
• Use the Chernoff bound to estimate $P(S_{100} \geq 4)$

---

The first part is easy when using the formula found here, $$\begin{align} P = \frac{N!}{k!(N-k)!}p^k q^{N-k} \end{align}$$

I know that the Chernoff bound is defined for $\theta \in \mathbb{R}$ as, $ l(a) := \sup[\theta a - \ln M(\theta)]$ where $M(\theta) := E[e^{\theta X_1}]$.

What I don't understand is how to actually apply / conceptualize the Chernoff bound to an example, like the one above.

P.S I need to be able to solve this by hand, but I've started to write the following MATLAB code to solve it exactly and to help with visualizing the problem

%% Inputs
numRV = 100;

%% Calculate exact value
p = 0.005;
q = 1 - p;

P = 0;
for k=4:1:numRV
P = P + factorial(numRV) / (factorial(k) * factorial(numRV-k)) * p^k * q^(numRV-k);
end
fprintf('P(Sn >= 4) = %f\n',P);

Answer 1

For all $\theta > 0$, $$\begin{align} P\{S_N \geq k\} &= \sum_{i=k}^N \binom{N}{i}p^i(1-p)^{N-i}\\ &= \sum_{i=0}^N \binom{N}{i}p^i(1-p)^{N-i}\cdot \mathbf 1_{i\geq k}\\ &< \sum_{i=0}^N \binom{N}{i}p^i(1-p)^{N-i}\cdot e^{\theta(i-k)} = e^{-\theta k}E[e^{\theta S_n}]\\ &= e^{-\theta k}(pe^\theta + 1-p)^N \end{align}$$ Now minimize the right hand side as a function of $\theta$.