\documentclass[11pt,twoside]{article}   
\usepackage{latex-macros/course}

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightyear}{2002}
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{12W}

%%%% WED %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let $R$ be the number of heads that come up when we toss $n$
independent coins, where each coin comes up heads with probability
$p$. The random variable $R$ has a binomial distribution. Using the
formula for variance of sums, show that $\variance{R} = np(1-p)$.

\solution{

\textit{From the course notes:} Recall that if a random variable,
$R$, has a binomial distribution, then
\[
\pr{R = k} = \binom{n}{k} p^k (1-p)^{n-k}
\]
where $n$ and $p$ are parameters such that $n \geq 1$ and $0 < p < 1$.

We can think of $R$ as the sum of $n$ independent Bernoulli variables.
Formally, we can write $R = R_1 + R_2 + \cdots + R_n$ where
\begin{displaymath}
  R_i = \begin{cases}
    1 & \text{with probability $p$,} \\
    0 & \text{with probability $1-p$.}
  \end{cases}
\end{displaymath}
Now we can compute the variance of the binomially distributed
variable~$R$.
\begin{align*}
\variance{R}
   & =  \variance{R_1} + \variance{R_2} + \ldots + \variance{R_n}
              & \text{(Theorem~\ref{th:varsum})}\\
   & =  n \variance{R_1} & (\variance{R_i} = \variance{R_j})\\
   & =  n (\expect{R_1^2} - \expectsq{R_1}) 
             & \text{(Def. of variance)}\\
   & =  n (\expect{R_1} - \expectsq{R_1}) & (R_1^2 = R_1)\\
   & =  n (p - p^2). & (\expect{R_1} = \pr{R_1 = 1} = p)
\end{align*}

The binomial distribution has an $\expect{np}$. This shows that
the binomial distribution has variance $p (1 - p) n$ and standard
deviation $\sqrt{p (1- p) n}$.  In the special case of an unbiased
binomial distribution ($p = 1/2$), the variance is $n/4$ and the
standard deviation is $\sqrt{n}/2$.
}
\end{problem}

\begin{problem}
%% Rosen 4.5.46
Provide an example that shows that the variance of the sum of two
random variables is not necessarily equal to the sum of their
variances, when the random variables are not independent.

\solution{A dramatic example is to take $Y = -X$. Then the sum of the
two random variables is 0, so the variance of $X+Y$ is 0. But the sum
of the variances is $2\variance{X}$, since $Y$ has the same variance
as $X$. Another example: let $X$ be equal to 1 if a flipped coin is heads, 0 otherwise. Similarly, let $Y$ be 1 if the same coin comes up tails. Then $\variance{X}
= \variance{Y} = 1/4$, but $X+Y=1$, so $\variance{X+Y}=0$.
}
\end{problem}


%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%[[[expectation, variance, Chebyshev]]]
% Spring 00, problem set 10.5, problem 4
% Fall 01, problem set 12, problem 2
\begin{problem}
The hat-check staff has had a long day, and at the end of the party
they decide to return people's hats at random. Suppose that $n$ people
have their hats returned at random. We previously showed that the
expected number of people who get their own hat back is 1,
irrespective of the total number of people. In this problem we will
calculate the variance in the number of people who get their hat back.

Let $X_i = 1$ if the $i$th person gets his or her own hat back and 0
otherwise.  Let $S_n = \sum_{i=1}^n X_i$, so $S_n$ is the total number
of people who get their own hat back. Show that

\begin{problemparts}

\problempart $\expect{X_i^2} = 1/n$.

\solution{
$X_i = 1$ with probability $1/n$ and 0 otherwise. Thus $X_i^2 = 1$
with probability $1/n$ and 0 otherwise. So $\expect{X_i^2} = 1/n$.
}

\problempart $\expect{X_i X_j} = 1/n(n-1)$ for $i \neq j$.

\solution{

The probability that $X_i$ and $X_j$ are both 1 is $1/n \cdot 1/(n-1) =
1/n(n-1)$.  Thus $X_i X_j = 1$ with probability $1/n(n-1)$, and is zero
otherwise.  So $\expect{X_i X_j} = 1/n(n-1)$.

}

\problempart $\expect{S_n^2} = 2$. \hint Use (a) and (b).

\solution{

\begin{eqnarray*}
\expect{S_n^2} & = & \sum_i \expect{X_i^2} + \sum_i \sum_{j \neq i} \expect{X_i X_j} \\
         & = & n \cdot \frac{1}{n} + n(n-1) \cdot \frac{1}{n(n-1)} \\
         & = & 2.
\end{eqnarray*}

}

\problempart $\variance{S_n} = 1$.

\solution{
\begin{eqnarray*}
\variance{S_n} & = & \expect{S_n^2} - \expectsq{S_n} \\ 
       & = & 2 - (n (1/n))^2 \\
       & = & 2 - 1 \\
       & = & 1.
\end{eqnarray*}
}

\problempart Explain why you can not use the variance of sums formula to
calculate $\variance{S_n}$.

\solution{The indicator random variables, $X_i$, are not even pairwise independent.  This can be seen by comparing the marginal and conditional probability of a particular person, Alice, getting her hat back.  The marginal probability, unconditioned on any other events, is $1/n$ as we've computed before.  However, if compute this probability conditioned on the event that a second person, Bob, got his hat back, we find that the probability of Alice getting her hat back is $1/(n-1)$.}

\problempart Using Chebyshev's Inequality, show that $\Pr(S_n \geq 11)
\leq .01$ for any $n \geq 11$.

\solution{
\begin{eqnarray*}
\Pr(S_n \geq 11) &=& \Pr(S_n - \expect{S_n} \geq 11 - \expect{S_n}) \\
                 &=& \Pr(S_n - \expect{S_n} \geq 10) \\
                 &\leq& \frac{\variance{S_n}}{10^2} = .01
\end{eqnarray*}

Note that the $X_i$'s are Bernoulli variables but are \emph{not}
independent, so $S_n$ does not have a Bernoulli distribution and the
Bernoulli estimates from Lecture Notes do not apply.
}

\end{problemparts}
\end{problem}

\begin{problem}
Prove that $\variance{X+Y+Z} = \variance{X} + \variance{Y} +
\variance{Z}$, if $X,Y,Z$ are pairwise independent. Explain why
pairwise independence is sufficient.

{\em Reminder:} If two random variable are independent, then
$\expect{X_i X_j} = \expect{X_i} \expect{X_j}$. Given a set of random
variables, pairwise independence implies that every possible pair of
random variables is independent. Mutual independence on the other hand
implies that any two subsets of random variables must be independent.

\solution{
Let $R = X + Y + Z$.  We can compute $\expectsq{R}$ as follows:
\begin{eqnarray*}
\expectsq{R}
& = & \left(\expect{X+Y+Z}\right)^2 \\
& = & (\expect{X} + \expect{Y} + \expect{Z})^2 \\
& = & \expectsq{X} + \expectsq{Y} + \expectsq{Z} + 2\expect{X}\expect{Y} + 
       2\expect{X}\expect{Z} + 2\expect{Y}\expect{Z}
\end{eqnarray*}

Computing $\expect{R^2}$ we get:
\begin{eqnarray*}
\expect{R^2} 
& = & \expect{(X+Y+Z)^2}\\
& = & \expect{X^2 + Y^2 + Z^2 + 2XY + 2XZ + 2YZ} \\
& = & \expect{X^2}  + \expect{Y^2} + \expect{Z^2} + 2\expect{XY} + 2\expect{XZ} + 2\expect{YZ}\\
& = & \expect{X^2}  + \expect{Y^2} + \expect{Z^2} + 2\expect{X}\expect{Y} + 
       2\expect{X}\expect{Z} + 2\expect{Y}\expect{Z}
\end{eqnarray*}

Notice that the last step is only valid because the random variables are pairwise independent. Finally, we can compute $\variance{R}$.  We can begin immediately by cancelling out the cross terms leaving us with:

\begin{eqnarray*}
\variance{R}
& = & \expect{R^2} - \expectsq{R}\\
& = & \expect{X^2}  + \expect{Y^2} + \expect{Z^2} - (\expectsq{X} + \expectsq{Y} + \expectsq{Z}) \\
& = & \expect{X^2} - \expectsq{X} + \expect{Y^2} - \expectsq{Y} + \expect{Z^2} - \expectsq{Z} \\
& = & \variance{X} + \variance{Y} + \variance{Z}
\end{eqnarray*}

Thus concluding the proof.
}
\end{problem}

\appendix
\section{Appendix}
\setcounter{secnumdepth}{0}
%%%%%%%%%%%%%%%%%%%%%%%%% VARIANCE %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{definition}
The \emph{variance}, $\variance{R}$, of a random variable, $R$, is:
\[
\variance{R} \eqdef \expect{(R - \expect{R})^2}.
\]
Variance can also be equivalently defined as:
\[
\variance{R}\eqdef \expect{R^2} - \expectsq{R},
\]
\end{definition}

\begin{theorem}\label{th:varsum}
If $R_1, R_2, \ldots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \ldots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\]
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%% MARKOV %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Markov's Theorem]
  If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%% Chebyshev %%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{theorem}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
\end{theorem}

\end{document}
