Chernoff Bound. Inequalities like $P(Y \ge 150) \le e^{-50log(\frac{27}{16})} $ .

2017-12-03 03:07:45

Let $X_1, X_2 , ...,X_{200} $ be independent Bernoulli random variables.

In other words: $X_i$ ~ $Ber(\frac{1}{2}$) for $ i \in $ {1,...,200}.

Define $ Y = \sum_{i=1}^{200} X_i $.

Given: $Y$ ~ $Bin(200,\frac{1}{2}) $.

Show that:

a) $ P(Y \ge 150) \le \frac{2}{3} $

b) for every $ t$ $\in$ $\mathbb{R}$ :

$\mathbb{E}(e^{t Y}) $ = $ e^{200log(\frac{1}{2}e^t+\frac{1}{2})} $

c) for every $t$ $\in \mathbb{R}$ : $P(Y \ge 150) \le e^{-150t+200log(\frac{1}{2}e^t+\frac{1}{2})} $

d) Find the optimal $t$ and show that: $P(Y \ge 150) \le e^{-50log(\frac{27}{16})} $

My attempt:

a) Solved this with Markov's inequality.

b) $\mathbb{E}(e^{t Y}) = \mathbb{E}(e^{t \sum_{i=1}^{200} X_i }) = \mathbb{E}(e^{ \sum_{i=1}^{200} t X_i }) = \mathbb{E}( \prod_{i=1}^{200}e^{t X_i }) $ . I know that $X_i$ is independent. But how do I know that $ e^{tX_i}$ is independent? Anyways now I'm using the independence: $ \prod_{i=1}^{200} \mathbb{E}(e^{t X_i }).$ Now I need that: $\mathbb{E}( e

  • b) The independence comes from a standard theorem that if $X_1, X_2, \dots, X_n$ are independent, then $f_1(X_1), f_2(x_2), \dots, f_n(X_n)$ are independent for any functions $f_i$. For the expectations, try the Law of the Unconscious Statistician:

    $$\mathbb E[e^{t X_i}] = e^{t \cdot 1} \cdot \frac 1 2 + e^{t \cdot 0} \cdot \frac 1 2.$$

    c) Show that when $t < 0$, the exponent on $e$ is positive, hence the bound is trivial.

    d) Hint: Recall from early calculus how to find optimal values of functions; the upshot is always to take a derivative, set it to 0, and solve.

    2017-12-03 05:26:23