\documentclass[12pt]{6042}
%\usepackage{eepic}
\usepackage{psfig}

%\documentstyle[12pt,twoside,multicol,amssymb]{article}
%\input{macros-course}


\newcommand{\E}{\mbox{E}}
\renewcommand{\Pr}{\mbox{Pr}}
%\newcommand\vari{\mbox{\bf Var}}
\newcommand\vari[1]{\variance{#1}}
%\newcommand\cov{\mbox{Cov}}
\newcommand\Ex[1]{\expect{#1}}
\newcommand\Prob[1]{\pr{#1}}

\begin{document}

\psol{11}{May 7, 1998}{\textbf{Pset 11 Not Assigned: For Review Only}}

\reading 6.042 Fall 1997 Lecture Notes 23--26

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 1
\problem

The couple who is having children until they get a boy and a girl knows 
that the expected number of children is 3.  What is the variance?

\textbf{Solution}:

After the first child, the waiting time until they get a success (a child of 
the opposite sex) is geometrically distributed.  That is the probability that the
first success occurs on the $n$th try is 
$(1-p)^{n-1} p$ ($n-1$ failures before 1 success).

The expectation of the geometric distribution is just the mean time to failure
$1/p$.

The variance is given by

$$
\sum_{n=1}^{\infty} n^2 (1-p)^{n-1} p - \frac{1}{p^2}
$$

From earlier in the course we know that

$$
\sum_{n=1}^{\infty} n^2 x^{n-1} = \frac{1 }{ (1-x)^2} + \frac{2x }{ (1-x)^3}
$$

Setting $x = (1-p)$ we obtain

$\sum_{n=1}^{\infty} n^2 (1-p)^{n-1} p = \frac{2 }{ p^2} - \frac{1 }{ p}$

Therefore the variance is 
$\frac{2 }{ p^2} - \frac{1 }{ p} - \frac{1 }{ p^2} = \frac{1 }{ p^2} -\frac{1 }{ p}$.

And putting $p=1/2$ we get that the variance is 2.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 2
%\problem 
%
%
%Now suppose that the couple wants to get two girls in a row.
%Find the expected number of children.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 3
\problem 


Let $X$ and $Y$ be random variables whose values are independent
observations drawn uniformly at random from the set
$\set{1,\ldots,n}$.  Compute the following quantities:
\bparts
\ppart $\vari{aX+bY}$.

\textbf{Solution}:

$$
\E[X] = \frac{1 }{ n} \sum_{i=1}^n i = \frac{(n+1) }{ 2}
$$

$$
\E(X^2) = \frac{1 }{ n} \sum_{i=1}^n i^2 = 
\frac{1 }{ n}\frac{n(n+1)(2n+1) }{ 6} = \frac{(n+1)(2n+1) }{ 6}
$$

so 

$$
\vari{X} = \frac{(n+1)(2n+1) }{ 6} - \frac{(n+1)^2 }{ 4} = \frac{n^2 -1 }{ 12}
$$


\begin{eqnarray*}
\vari{aX+bY} & = & \vari{aX}+\vari{bY}\\
& = & a^2 \vari{X} + b^2\vari{Y}\\
& = & (a^2+b^2)\vari{X}\\
& = & \frac{(a^2+b^2) }{ 12}(n^2-1)
\end{eqnarray*}

\ppart $\E[\max(X,Y)]$.

\textbf{Solution}:

Observe that $\Pr[\max(X,Y) = i] = \Pr[X = i \mbox{ and } Y < i] +
\Pr[X < i \mbox{ and } Y = i] + \Pr[X = Y = i] = \frac{1}{n} \cdot
\frac{i-1}{n} + \frac{i-1}{n} \cdot \frac{1}{n} + \frac{1}{n} \cdot
\frac{1}{n} = \frac{2i-1}{n^2}$.  

This means that
\[\E[\max(X,Y)] = \sum_{i=1}^n \frac{i(2i-1)}{n^2} =
\frac{1}{n^2} \sum_{i=1}^n (2i^2 - i) = \frac{1}{n^2}(
\frac{2n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}) = \frac{(n+1)(4n-1)}{6n}.\]


\ppart $\E[\min(X,Y)]$.  ({\em Hint:}  There is a way to get the answer 
to this using the previous part.)

\textbf{Solution}:

Observe that $\E[\max(X,Y)] + \E[\min(X,Y)] = \E[\max(X,Y) +
\min(X,Y)] = \E[X + Y] = \E[X] + \E[Y]$.  Now $\E[X] = \E[Y] =
\frac{n+1}{2}$.  so $\E[\min(X,Y)] = n+1 - \frac{(n+1)(4n-1)}{6n} =
\frac{(n+1)(2n+1)}{6n}$. 

\ppart $\E[|X-Y|]$.

\textbf{Solution}:

We have that $|X-Y| = \max(X,Y)-\min(X,Y)$, so by linearity of expectation
$\E[|X-Y|] = \E[\max(X,Y)]- \E[\min(X,Y)] = \frac{(n+1)(4n-1) }{ 6n} - 
\frac{(n+1)(2n+1) }{ 6n} = \frac{(n^2-1) }{ 3n}$.
 
\ppart $\vari{\abs{X-Y}}$.

\textbf{Solution}:

$\vari{\abs{X-Y}} = \E[\abs{X - Y}^2] - \expectsq{|X - Y|}$.  But $\E[|X -
Y|^2] = \E[(X - Y)^2] = \vari{X - Y} + \expectsq{X - Y} = \vari{X - Y} = 2
\vari{X} = (n^2 - 1)/6$ (since $\E[X - Y] = \E[X] - \E[Y] = 0$).

This means that 
\[\vari{|X - Y|} = \frac{n^2 - 1}{6} - (\frac{n^2 -
1}{3n})^2 = \frac{(n^2 - 1)(n^2 + 2)}{18 n^2}.\]

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 4
\problem


\bparts

\ppart Let $X$ be a random variable whose value is an observation drawn
uniformly at random from the $\set{i\in\nats \mid -n \le i \le n}$.  Let
$Y = X^2$.  Show that $X$ and $Y$ are {\em not} independent, but that
$\E[XY] = \E[X] \E[Y]$.

\textbf{Solution}:

Since $Y$ is determined by $X$, there are many cases indicating where $X$
and $Y$ are not independent, e.g., 
\[\pr{Y = 0} = 1/(2n+1),\mbox{  but } \pr{Y=0 \mid X= 0} = 1.\]

To see that $\E[XY] = \E[X] \E[Y]$, note that $\E[X] = 0$ and $\E[XY]
= \E[X^3] = 0$ since $X$ and $X^3$ are both symmetrical.

\ppart 
Show that in general for any two random variables $X$ and $Y$
that if $\E[XY] = \E[X] \E[Y]$ then $\vari{X+Y} =
\vari{X} + \vari{Y}$.  In particular, this shows that it is possible
for nonindependent variables to have variances that exhibit
linearity.

\textbf{Solution}:

We have that $\vari{X + Y} = \E[(X+Y)^2] - (\E[X+Y])^2 = \E[X^2 + 2XY +
Y^2] - (\E[X]+ \E[Y])^2 = \E[X^2] - (\E[X])^2 + \E[Y^2] - (\E[Y])^2 +
2\E[XY] - 2\E[X]\E[Y] = \vari{X} + \vari{Y}$. 

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 5
%\problem 
%
% (Wald's theorem)
%
%Consider the following $3$-stage experiment:
%
%In the first stage, I throw a $6$-sided die.  The number of spots that I
%get determines how many instances of the second stage to perform.
%
%In the second stage, I toss a fair coin.  This stage is repeated
%once for each spot I got in the first stage.  The total number of heads that I
%get in this stage determines how many instances of the third stage to perform.
%
%In the third stage, I throw a $6$-sided die.  This stage is repeated
%once for each head I got in all instances of the second stage.
%
%For example, if the outcome of the first stage is $3$, then stage 2
%gets played $3$ times.  Suppose the outcomes of the $3$ instances of
%stage 2 are $1,3,4$.  Then stage $3$ is played $1+3+4 = 8$ times, and the
%score is the sum of $8$ instances of stage $3$.
%
%Assume that all throws are mutually independent.
%
%My score is the total number of spots on all the instances of the
%third stage.
%
%What is my expected score?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 6
\problem 


Suppose that someone is infected with an unknown incurable contagious disease.
Everyday he encounters $n$ healthy people and infects each of them with
probability $p$. Encounters are mutually independent.
These people in turn meet $n$ people and infect them with 
probability $p$ and so on.

\bparts

\ppart 
Write a recurrence for the expected number of people on the $k+1$st day
in terms of the expected number of people on the $k$th day.
Assume that each day every sick person meets $n$ {\em different} persons.

\textbf{Solution}:

Let $S_k$ be a random variable giving  the number infected 
people after $k$ days. \\
We can write a recurrence for $S_{k+1}$ in terms of $S_k$. \\
\\
Let the sick people after day $k$ be numbered $1,\ldots,S_k$. \\
Let $H_i$ be a random variable giving the number of healthy 
people infected by sick person $i$ in one day. \\
Then $H_i$ has a binomial distribution with parameters $n$ and $p$. \\
Then: \\
\[
S_{k+1} = S_k+ \sum_{i=1}^{S_k} H_i
\]
It follows from linearity of expectation that
\[
\E[S_{k+1}] = \E[S_k]+\E[ \sum_{i=1}^{S_k} H_i].
\]
Then by Wald's theorem,
\[
\E[S_{k+1}] = \E[S_k]+\E[S_k]\cdot \E[H]
\]
where $H$ is a variable with the binomial distribution with
parameters $n$ and $p$. \\
Thus, $\E[H] = np$.  \\
\\
So
\[
\E[S_{k+1}] = \E[S_k]+\E[S_k]\cdot np = (1 + np) \E[S_k]
\]
Also, $\E[S_0] = 1$. \\
So we have a recurrence involving these expectations. \\
Writing $e_i$ for $\E[S_i]$, we have:
\[
e_{k+1} = (1+np)e_k
\]
and 
\[
e_0 = 1
\]

\ppart Solve the recurrence of part (a).

\textbf{Solution}:

$e_k = (1+np)^k$.

\ppart
Now suppose that any sick person recovers from the disease each day with 
probability $r$. Find the expected number of sick people on the $k$th day.

\textbf{Solution}:

 Let $B_i$ be the indicator variable for whether the $i^{th}$ sick person gets better.  Then $\E[B_i] = r$.  Then
\[
S_{k+1} = S_k+ \sum_{i=1}^{S_k} (H_i-B_i)
\]
It follows that
\[
\E[S_{k+1}] = \E[S_k]+\E[S_k]\cdot \E[H]-\E[S_k]\E[B_i]
\]
and so

\begin{eqnarray*}
e_{k+1} &= & e_k(1+np-r)\\ &= &(1+np-r)^k
\end{eqnarray*}

\eparts
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 7
\problem


A miner, lost in some abandoned mine, finds himself in a room 
containing three doors.  Door 1 leads him to freedom after two 
hours travel; door 2 returns him to the same room after four hours travel, and 
door 3 returns him to the room after eight hours travel.
Each time he finds himself in the room, 
the miner picks a door with equal probability.  
Let $T$ denote the time until he finds the exit. \\

\bparts

\ppart Define a sequence of iid random variables $X_i$ and a stopping rule 
$N$ such that

\begin{displaymath}
T = \sum_{i=1}^{N}{X_i}
\end{displaymath}


\textbf{Solution}:

We view this as an experiment where at each step we make a choice between
three equiprobable outcomes.

Let $X_i$ = number of hours to return to room on $i$th step.

Let $N$ = number of steps until good door is selected.

Then $N$ is geometrically distributed with probability $1/3$.

\ppart Use Wald's Identity to find $\E[T]$


\textbf{Solution}:

$\Pr(X_i = 2) = 1/3$

$\Pr(X_i = 4) = 1/3$

$\Pr(X_i = 8) = 1/3$

$\E[X_i] = 14/3$

$\E[N] = 3$

By Wald's Identity

$$
\E[\sum_{i=1}^N X_i] = 14
$$


\eparts   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 8
%\problem
%
%
%Recall than in the Chinese Appetizer Problem $R$ is number of people that
%get the same appetizer after a spin of the Lazy Susan.
%
%\bparts
%
%\ppart
%Compute the variance of $R$.
%
%\ppart
%Show that the upper bound that you get on $\Pr(R \geq N)$ from the strong form
%of Chebyshev's inequality is tight.
%
%\eparts
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F97 PS11 Problem 9


\problem 

In this problem, we analyze probabilistically the 1st stage of bubble sort
performed on a list of $n$ integers $\{ i_1, \ldots i_n \}$.  
We assume that all the integers are 
distinct.

On the first step we compare integers $i_1$ and  $i_2$. If $i_1 > i_2$ we
swap them otherwise we leave them as they are.

On step $k~(2\leq k\leq n-1)$, we compare the new  $i_k$ with
$i_{k+1}$. If $i_k > i_{k+1}$ we swap else we leave them as they are.

We assume that the order of the integers is chosen uniformly from all 
possible orderings.  

\bparts
\ppart  
If a number $x$ is randomly (uniformly) chosen from a set of 
$n$ distinct numbers, what is the probability that $x$ is the largest
number in the set? 

What is the probability that on the $k$th step ($2\leq k\leq n-1)$,
$i_{k+1}$ is the biggest integer to appear in the list so far?

\textbf{Solution}:

$\Pr({\mbox{choosing largest of $n$ numbers}}) = 1/n$.  

$\Pr({\mbox{$i_{k+1}$ in $k$ step is highest so far}})=1/(k+1)$.



\ppart 
Let $C_k$ be a random variable that is equal to $1$ if $i_{k+1} > i_{k}$. 
What is $\E[C_k]$?


\textbf{Solution}:
\[\E[C_k] = \Pr({C_k = 1}) 
	= \Pr({\mbox{ $i_k$ is highest so far}}) 
	= \frac{1}{k+1}.\]


\ppart  
Let random variable $C=\sum_{k=1}^n C_k$. 
Give an asymptotic bound for $\E[C]$ as well as an interpretation
of what $\E[C]$ is.


\textbf{Solution}:
\[\E[C] = \sum_k \E[C_k] = \sum_{k=2}^{n}\frac{1}{k} \sim \ln n.\]

$C$ is the total number of swaps, 
so $\E[C]$ is the expected number of swaps.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS 12 Problem 5
\problem
% (Wald's theorem)


Consider the following $3$-stage experiment:

In the first stage, I throw a $6$-sided die.  The number of spots that I
get determines how many instances of the second stage to perform.

In the second stage, I throw a $6$-sided die.  This stage is repeated
once for each spot I got in the first stage.  The total number of spots that I
get in this stage determines how many instances of the third stage to perform.

In the third stage, I throw a $6$-sided die.  This stage is repeated
once for each spot I got in all instances of the second stage.

For example, if the outcome of the first stage is $3$, then stage 2
gets played $3$ times.  Suppose the outcomes of the $3$ instances of
stage 2 are $1,3,4$.  Then stage $3$ is played $1+3+4 = 8$ times, and the
score is the sum of $8$ instances of stage $3$.

Assume that all throws are mutually independent.

My score is the total number of spots on all the instances of the
third stage.

What is my expected score?

(Analyze this as carefully as you can, using Wald's theorem.  Try to
be careful about uses of independence.)

\textbf{Solution}:

Let $X$ be the random variable whose value is the roll in the first
stage.  Let $Y_1, Y_2, \ldots, Y_X$ be the random variable whose values
are the rolls in the second stage.  Define $Y = Y_1 + \cdots + Y_X$.
Let $Z_1, Z_2, \ldots, Z_Y$ be the random variable whose values are
the rolls in the third stage.  Define $Z = Z_1 + \cdots + Z_Y$.  We
want to find $\E[Z]$.  Now all the rolls are mutually independent, so
we can use Wald's theorem to get $\E[Y] = \E[X]\E[Y_i] =
(7/2)^2$.  Since $Y$ is determined by rolls that are
independent of the rolls in the third stage,
$Y$ and $Z_i$ are independent.  So we apply Wald`s theorem again to
get $\E[Z] = \E[Y]\E[Z_i] = (7/2)^3.$

The answer is $(7/2)^3$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS 12 Problem 7
%\problem
%
%
%\bparts
%\ppart Let $X$ be a random variable whose value is an observation
%drawn uniformly at random from the set
%$\{-n,-n+1,\ldots,-2,-1,0,1,2,\ldots,n-1,n\}$.
%Let $Y = X^2$. Show that $X$ and $Y$ are {\em not} independent, but
%that
%$\Ex{XY} = \Ex{X} \Ex{Y}$.
%\ppart Show in general for any two random variables $X$ and $Y$
%that if $\Ex{XY} = \Ex{X} \Ex{Y}$ then $\vari{X+Y} =
%\vari{X} + \vari{Y}$.  In particular, this shows that it is possible
%for non independent variables to have variances that exhibit
%linearity.
%\ppart Let $X_1, X_2, \ldots, X_n$ be $n$ {\em pairwise} independent
%random variables.  Show that $\vari{X_1 + X_2 + \cdots + X_n} =
%\vari{X_1} + \vari{X_2} + \cdots + \vari{X_n}$.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS 12 Problem 8
\problem


Suppose you flip a fair coin 100 times.  The coin flips are all mutually independent.  
What is an upper bound on the probability
that the number of heads is at least 70\ldots
\begin{problemparts}

\problempart
\ldots according to Markov's Inequality?

\textbf{Solution}:
The expected number of heads of $50$.  So the probability that the
number of heads is at least $70$ is at most $50/70 = 0.71$.

\problempart
\ldots according to Chebyshev's Inequality?

\textbf{Solution}:
Let $X_i$ be the random variable whose value is $1$ if the $i$th coin
flip is heads.  Then $\Var[X_i] =  1/2 - (1/2)^2 = 1/4$.  So $\Var[X_1
+ \cdots + X_100] = 100/4 = 25$.
 The variance of the number of heads is $100/4 = 25$, so the standard
deviation is $5$.  So $70$ is four times the standard deviation from
the mean.  Since the distribution is symmetric, the
probability is at most $\frac{1}{2} \cdot \frac{1}{4^2} = \frac{1}{32}$


\problempart
\ldots according to Chernoff's Bound?

\textbf{Solution}:
We apply Chernoff`s bound with $c = 70/50 = 1.4$.  This gives us that
$\alpha = \ln(1.4) + 1/1.4 - 1 = 0.05076$ and that the probability is at most $e^{-0.05076 \cdot 1.4 \cdot 50} = 0.0286$.


%\problempart
%\ldots according to the upper bound for binomial distributions
%        derived in lecture?\\
%        (Get a strict upper bound by using the multiplicative factors
%of
%        $\frac{1-\alpha}{1-2\alpha}$ to account for the case that
%        there are strictly more than 70 heads,
%        and $(\frac{n}{e})^{\frac{1}{12n}}$ to adjust Stirling's
%        approximation.)
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%F96 PS12
%\problem
%Give upper bounds for the following probabilities using the Markov,
%Chebyshev, or Chernoff inequality, where appropriate.  If more than
%one inequality applies, use the inequality that gives you the best
%bounds. 

%\bparts
%\ppart Suppose you play the following game:  Flip $5$ independent and
%fair coins.  Score one point if the difference between the number of
%heads and tails is at least $3$.  What is the probability that your
%average score is greater than $0.9$ if you play the game $100$ times?

%\ppart Let $a$ and $b$ be two numbers picked independently and
%uniformly at random from the set $\{0,1,2,3,4\}$.
%For $i = 0,1,2,3,4$, define the random
%variable $X_i$ to be equal to $ai + b \bmod p$.  
%Let $Y = \frac{1}{5}(X_1 + X_2 + X_3 + X_4 + X_5)$.  
%What is the probability that $Y$ is greater than $3.5$?
%{\em Hint}: Observe that $X_i$ is distributed uniformly on the set
%$\{0,1,2,3,4\}$.  

%\ppart You are told that the average (mean) annual income is \$10,000
%in a particular population.  Five people are picked independently and
% uniformly and at random from the population.  
%What is the probability that their avearge (mean) annual income is
%greater than or equal to \$1,000,000?
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%S95 PS 10 Problem 4
\problem 


Let $S$ be a sample space.  Say random variable $X: S \rightarrow \naturals$ has 
distribution
\[
X = \left\{ \begin{array}{cl} 2 & \mbox{with probability $1/4$,} \\
                             3 & \mbox{with probability $1/4$,} \\
			     5 & \mbox{with probability $1/2$;} \end{array}
\right.
\]
and random variable $Y:S\rightarrow \naturals$ has distribution
\[
Y = \left\{ \begin{array}{cl} 1 & \mbox{with probability $2/3$,} \\
                             4 & \mbox{with probability $1/3$;} \end{array}
\right.
\]
where $X$ and $Y$ are independent.

Let random variable $Z:S\rightarrow \naturals$ be given by $Z = \max(X,Y)$.
\bparts
\ppart What is the expected value of $Z$?

\textbf{Solution}:

We first compute the values of $Z$ along with their associated
probabilities.  Note that $P(X=x \mbox{ \& } Y=y) = P(X=x)P(Y=y)$ since $X$
and $Y$ are independent.

\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
$X$ & $Y$ & $Z$ & $Z^2$ & Pr \\ \hline
$2$ & $1$ & $2$ & 4 & $\frac{1}{6}$ \\ \hline
$3$ & $1$ & $3$ & 9 & $\frac{1}{6}$ \\ \hline
$5$ & $1$ & $5$ & 25 & $\frac{1}{3}$ \\ \hline
$2$ & $4$ & $4$ & 16 & $\frac{1}{12}$ \\ \hline
$3$ & $4$ & $4$ & 16 & $\frac{1}{12}$ \\ \hline
$5$ & $4$ & $5$ & 25 & $\frac{1}{6}$ \\ \hline
\end{tabular}
\end{center}

Now
\[
E(Z) = 2\cdot\frac{1}{6} + 3\cdot\frac{1}{6} + 5\cdot\frac{1}{3} +
4\cdot\frac{1}{12} + 4\cdot\frac{1}{12} + 5 \cdot\frac{1}{6} = 4
\]

\ppart What is the variance of $Z$?

\textbf{Solution}:

Recall that ${\rm Var}Z = E(Z^2) - E(Z)^2$.  So we first compute $E(Z^2)$
using the data from the above table
\[
E(Z^2) = 4\cdot\frac{1}{6} + 9\cdot\frac{1}{6} + 25\cdot\frac{1}{3} +
16\cdot\frac{1}{12} + 16\cdot\frac{1}{12} + 15 \cdot\frac{1}{6} =
	\frac{52}{3}
\]
Finally ${\rm Var}(Z) = 52/3 - 16 = \frac{4}{3}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%S95 PS 10 Problem 6
\problem


\bparts
\ppart Show that if random variables $X$ and $Y$ are independent then ${\rm
Cov}(X,Y)=0$

\textbf{Solution}:

First we show that if $X$ and $Y$ are independent, then $E(XY) = E(X)E(Y)$.
\begin{eqnarray*}
E(XY) & = & \sum_{x,y} xyP(X=x \mbox{ \& } Y=y) \\
      & = & \sum_x \sum_y xyP(X=x \mbox{ \& } Y=y) \\
	  & = & \sum_x \sum_y xyP(X=x)P(Y=y) \\
	  & = & \sum_x xP(X=x)\sum_y yP(Y=y) \\
	  & = & \sum_x xP(X=x)E(Y) \\
	  & = & E(Y)\sum_x xP(X=x) \\
	  & = & E(X)E(Y)
\end{eqnarray*}
Since ${\rm Cov}(X,Y) = E(XY) - E(X)E(Y)$, ${\rm Cov}(X,Y) = 0$.

\ppart Show that having ${\rm Cov}(X,Y)=0$ does not necessarily mean that
$X$ and $Y$ are independent.

\textbf{Solution}:

Let $(X,Y)$ have joint probability given by the table below:

\begin{center}
\begin{tabular}{|c|c|c|} \hline
$X$ & $Y$ & P \\ \hline
$-1$ & $1$ & $\frac{1}{3}$ \\ \hline
$0$ & $0$ & $\frac{1}{3}$ \\ \hline
$1$ & $1$ & $\frac{1}{3}$ \\ \hline
\end{tabular}
\end{center}

Note that $X$ and $Y$ are not independent.  $P(X=1 \mbox{ \& } Y=1) =
\frac{1}{3} \neq \frac{2}{9} = P(X=1)P(Y=1)$.  But $E(X) = 0$ and $E(XY) =
0$ (since $XY=X$).  Thus ${\rm Cov}(X,Y) = 0$.


%\ppart Let $X_1,\ldots,X_n$ be random variables.  Prove that
%\[
%{\rm Var}(X_1+\ldots+X_n)=\sum_{i=1}^n {\rm Var}(X_i) + 2\sum_{i<j} {\rm Cov}(X_i,X_j)
%\]
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}
\end{document}
