LFD Book Forum - View Single Post

svend · #4 09-17-2016, 11:43 AM

Here's my take on Problem 1.9, part(b), which is following the same lines as the description of MaciekLeks above.

We have:

$\begin{split} P(u \geq \alpha ) & = P(\frac{1}{N}{}\sum_n x_n \geq \alpha) \\ & = P(\sum_n x_n \geq N \alpha) \\ & = P(e^{s \sum_n x_n} \geq e^{s N \alpha}) \end{split}$

Since $e^{s t}$ is monotonically increasing in t.

Also, $e^{s t}$ is non negative for all t, implying Markov inequality holds:

$\begin{split} P(e^{s \sum_n x_n} \geq e^{s N \alpha}) & \leq \frac{E(e^{s \sum_n x_n})}{e^{s N \alpha}} \\ & = \frac{E(\prod_n e^{s x_n})}{e^{s N \alpha}} \\ & = \frac{\prod_n E(e^{s x_n})}{e^{s N \alpha}} \end{split}$

The last line being true since [math]x_n[\math] are independent.

From there it directly follows that

$P(u \geq \alpha ) \leq U(s)^N e^{-s N \alpha}$