# Large deviation of Bernoulli random variables and applying Chernoff bound

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);


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$.
• Still little lost here. I have $\ln M(\theta) = \ln (p e^\theta + (1-p))$, which is the cumulant generating function (although I don't really understand what that means). And how do I minimize as a function of $\theta$? Commented Sep 24, 2013 at 3:54
• Surely you know how to find the minimum value of $e^{-\theta k}(pe^\theta + 1-p)^N$ as a function of $\theta$? Differentiate with respect to $\theta$, set derivative to equal $0$ and solve for $\theta$, etc? Commented Sep 24, 2013 at 16:36