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 <j\leq n, then Var[X] = \sum_{i=1}^{n}Var[X_{i}].

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].


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


One response to this post.

  1. I’m gone to say to my little brother, that he should also go to see this blog on regular basis to obtain updated from most up-to-date reports.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: