# 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$

1. How to find the best lambda

2. How to derive the MGF of $Y$

3. Is finding the MGF supposed to help me get the bound? How?

• What a dreadful formula for the Chernoff bounds! Do they have to make it so complicated? Oct 28 '14 at 2:20
• Please, could you remove the "*" from the formulas? This is a programming, not a mathematical notation for multiplication. And you want to minimise the exponent of $e$, not maximise it, in order to minimise the upper bound. Dec 27 '14 at 14:53

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.