7
$\begingroup$

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:

  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?

$\endgroup$
2
  • 4
    $\begingroup$ What a dreadful formula for the Chernoff bounds! Do they have to make it so complicated? $\endgroup$ Oct 28 '14 at 2:20
  • $\begingroup$ 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. $\endgroup$
    – Xi'an
    Dec 27 '14 at 14:53
10
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.