How to bound a probability with Chernoff's inequality? In my class, we were given Chernoff's inequality as 
$$P(X\le -t) \le e^{(-(\lambda t - \log( E(e^{-\lambda x}))))}$$
$$P(X\ge -t) \le e^{(-(\lambda t - \log( E(e^{\lambda x}))))}$$
It says that to find the best upper bound, we must find the best value of $\lambda$ to maximize the exponent of $e$, thereby minimizing the bound. 
I'm trying to solve the problem:

Let $X_1, X_2$ be iid random variables with Geometric(.01)
  distribution. Let $Y = X_1 + X_2$
Derive the MGF of $Y$, then use Chernoff's inequality to bound
  $P(S-E(S) \le -t)$, with $t > 0$

I don't understand how to go about this problem - specifically:


*

*How to find the best lambda

*How to derive the MGF of $Y$

*Is finding the MGF supposed to help me get the bound? How?
 A: Your class is using needlessly complicated expressions for the Chernoff bound
and apparently giving them to you as magical formulas to be applied without
any understanding of how they came about.
Suppose that $X$ is a random variable for which we wish to compute $P\{X \geq t\}$.  One way of doing this is to define a real-valued function $g(x)$ 
as follows:
$$g(x) = \mathbf 1_{x \geq t} 
= \begin{cases}1, & x \geq t,\\0, & x < t,\end{cases}$$ and then consider the expected value of the random variable $g(X)$. This is readily expressed; we 
have that
$$\displaystyle E[g(X)] = \int_{-\infty}^\infty g(x)f_X(x)\,\mathrm dx 
= \int_t^\infty f_X(x)\,\mathrm dx = P\{X \geq t\}$$
or that
$$E[g(X)] = \sum_i g(x_i)p_X(x_i) = \sum_{i: x_i \geq t}p_X(x_i)
= P\{X \geq t\}$$
according as $X$ is a continuous random variable or a discrete random
variable.  Computations of this kind are, of course, straightforward when
we know the probability density function or probability mass
function of $X$. But what if don't know these or are too lazy to
determine these?  In such cases, perhaps a bound might be useful.
Note that for all positive real  numbers $\lambda$, 
$g(x) \leq e^{\lambda(x-t)}$ for all $x \in \mathbb R$.
In fact, equality holds only at $x=t$ where both functions equal $1$.
Therefore, we have that
$$\begin{align}P\{X \geq t\}&=  E[g(X)]\\
&\leq E[e^{\lambda(X-t)}]\\
&= e^{-\lambda t}\cdot E[e^{\lambda X}].\\
&\Downarrow\\
P\{X \geq t\} &\leq e^{-\lambda t}\cdot E[e^{\lambda X}]\tag{1}\end{align}$$
Do you begin to see why moment-generating functions (MGFs)
might have been recommended to you? I point out that the
occurrence of the MGF has been very cleverly concealed in your classroom
materials: you wrote down: $P(X\ge -t) \le e^{(-(\lambda*t - \log( E(e^{\lambda*x}))))}$ where the
MGF comes from the $e^{\log( E(e^{\lambda*x}))} = E(e^{\lambda*x})$ part.
So, once you have the MGF of $X$ (which is $E[e^{\lambda X}]$ and not
$E(e^{\lambda*x})$ as your instructor calls it) note that the MGF is
a real-valued function of $\lambda$, and so the right side
of $(1)$ is a function $h(\lambda)$ of the real variable $\lambda$. 
Since $P\{X \geq t\}\leq h(\lambda)$ for all $\lambda >0$, 
we get the best
upper bound (meaning smallest upper bound) on $P\{X \geq t\}$ by 
determining the minimum value of
$h(\lambda)$ on $(0,\infty)$.  Remember that $h(\lambda)$ is just an
ordinary real-valued function -- we have squeezed out all the probability
stuff from it -- and hopefully you know how to find the minimum value
of $h(\lambda)$ on $(0,\infty)$.
Finally, I will mention that since $X_1$ and $X_2$ are independent
random variables, we can determine the MGF of $Y = X_1+X_2$ from
the (hopefully known) MGFs of $X_1$ and $X_2$: we don't need to 
find the probability mass function of $Y$ in order to apply the 
Chernoff bound. Of course, in this case, the probability mass function
is not that hard to find and one can get the exact value of
$P\{X \geq t\}$ without extraordinarily complicated calculations, but
the bound certainly is a lot easier to calculate.
