## Probability and Computing: Chapter 3 Exercises (cont.2)

Exercise 3.15: Let the random variable $X$ be representable as a sum of random variables $X=\sum_{i=1}^{n}X_{i}$. Show that, if $E[X_{i}X_{j}]=E[X_{i}]E[X_{j}]$ for every pair of $i$ and $j$ with $1 \leq i , then $Var[X] = \sum_{i=1}^{n}Var[X_{i}]$.

Solution:
The proof is essentially the same as described in the text. Note that this problem implies we don’t need mutual independence to use linearity of variance, just $E[A.B] = E[A]E[B]$ is enough.

Exercise 3.16: This problem shows that  Markov’s inequality is as tight as it could possible be. Given a positive integer $k$, describe a random variable $X$ that assumes only nonnegative values such that:

$Pr(X \geq kE[X]) = \frac{1}{k}$.

Exercise 3.17: Can you give an example(similar to that for Markov’s inequality in Exercise 3.6) that shows that Chebyshev’s in equality is tight? If not, explain why not?

Exercise 3.19: Let $Y$ be a nonnegative integer-valued random variable with postive expectation. Prove

$\frac{E[Y]^{2}}{E[Y^{2}]} \leq Pr( Y \ne 0) \leq E[Y]$.

Solution:

First we will prove $E[Y] \ge Pr(Y \ne 0)$

$E[Y] = \sum_{y=1}^{\infty}yPr(Y = y) \ge \sum_{y=1}^{\infty} Pr(Y = y) = Pr(Y \ne 0)$

Now we prove $E[Y]^{2} \le E[Y^{2}]Pr(Y \ne 0)$

$E[Y]^{2} = \big(\sum_{y=1}^{\infty}yPr(Y=y)\big)^{2}$

$= \sum_{y=1}^{\infty}\big(yPr(Y=y)\big)^{2} + \sum_{i=1}^{\infty}\sum_{j = i + 1}^{\infty}2ijPr(Y=i)Pr(Y=j)$

$E[Y^{2}]Pr(Y \ne 0) = \big(\sum_{i=1}^{\infty}i^{2}Pr(Y=i)\big)\big(\sum_{j=1}^{\infty}Pr(Y = j)\big)$

$= \sum_{y=1}^{\infty}\big(yPr(Y=y)\big)^{2} + \sum_{i=1}^{\infty}\sum_{j=i+1}^{\infty}(i^{2}+j^{2})Pr(Y=i)Pr(Y=j)$

By comparing $\sum_{i=1}^{\infty}\sum_{j = i + 1}^{\infty}2ijPr(Y = i)Pr(Y = j)$
$\le \sum_{i=1}^{\infty}\sum_{j=i+1}^{\infty}(i^{2} + j^{2})Pr(Y=i)Pr(Y = j)$,

we obtain $E[Y]^{2} \le E[Y^{2}]Pr(Y \ne 0)$.

Thus $\frac{E[Y]^{2}}{E[Y^{2}]}\le Pr(Y \ne 0). \qquad \square$