Latest update

# 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