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

\renewcommand{\reading}
{\href{http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/lectures/ln13.pdf}
{Week 13 Notes}}

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document}
\problemset{11}

% From fall 01 tut 12
% editted from the S99 Tutorial 13 version to add distribution questions
% topics: understand Markov. Chebyshev bounds and distributions that satisy bounds

\begin{problem}
Suppose you have learned that the average graduating MIT student's
total number of credits is 200.

\begin{problemparts}

\problempart Knowing only this average, use Markov's inequality to
find a best possible upper bound for the fraction of MIT students
graduating with at least 235 credits. \footnote{Ignore the fact that there are
practical limits to the amount of time a student can stay at MIT and remain
sane; That is, assume that there is no bound on the number of credits a student
may earn.}

\solution{ 
Let $X$ be a random variable with a distribution equal to that of the 
graduating MIT students' credit count. We are given that $\expect{X} = 200$. 
By Markov's inequality:

\begin{displaymath}
\prob{X\geq 235}\leq\frac{\expect{X}}{235} = \frac{200}{235} \approx 0.85
\end{displaymath}
}

\problempart Demonstrate that this is a best possible bound by giving a
distribution for which this bound holds with equality.

\solution{ 
The bound is attained with equality at the two-point distribution which has
non-zero values only at 0 and 235, \ie
\begin{eqnarray*}
\prob{X=235} &=& 200/235\\
\prob{X=0} &=& 35/235\\
\prob{X=x} &=& 0\text{ for all other }x
\end{eqnarray*}
}

\problempart Suppose you are now told that no student can graduate
with fewer than 170 units.  How does this allow you to improve your
previous bound? As before, show that this is the best possible bound.

\solution{
We can now apply Markov's inequality to the nonnegative variable $Y = X -
170$, with expectation $\expect{Y} = \expect{X-170} = \expect{X} - 170 = 30$.
So,
\begin{displaymath}
\prob{X \geq 235} = \prob{X - 170 \geq 235 - 170} =  \prob{Y \geq 65}
\end{displaymath}

Therefore:
\begin{eqnarray*}
\prob{X \geq 235}
  & =    & \prob{Y \geq 65} \\
  & \leq & \frac{\expect{Y}}{65} \\
  & \leq & \frac{30}{65} \approx 0.46
\end{eqnarray*}

As above, we achieve an optimum (equality in the bound) when our
distribution consists of two spikes: one at $(x-170)=c-170$,
i.e. $x=235$, and one at $(x-170)=0$, i.e. $x=170$.
\begin{eqnarray*}
\prob{X=235} &=& (200-170)/(235-170)=30/65\\
\prob{X=170} &=& 35/65\\
\prob{X=x} &=& 0\text{ for all other }x
\end{eqnarray*}
}

\problempart Now suppose you {\em further} learn that the standard
deviation of the total credits per graduating student is~7.  What is the
Chebyshev bound on the fraction of students who can graduate with at least
235 credits?

\solution{The variance of $X$ is the square of the standard deviation, or
49. The variance of $Y$ is the same as that of $X$, by the linearity of
variance. That is, $\variance{Y} = \variance{X - 170} = \variance{X} -
\variance{170} = 49 - 0$. (The variance of a constant is 0).
\begin{eqnarray*}
\prob{X \geq 235}
& = & \prob{Y \geq 65} \\
& = & \prob{Y - \expect{Y} \geq 65 - \expect{Y}} \\
& = & \prob{Y - 30 \geq 35} \\
& \leq & \prob{| Y- 30 | \geq 35} \\
& \leq & \frac{\variance{Y}}{35^2} \\
& \leq & \frac{49}{1225} = \frac{1}{25} 
\end{eqnarray*}

This is a much better bound than before!
}

\end{problemparts}
\end{problem}


\begin{problem}
If a couple continues to have children until they have a boy, then we have
seen that the expected number, $N$, of children the will have is $1/(1/2)
= 2$, assuming boys and girls are equally likely to be born.  What is the
variance of the number of children they will have?  \hint By definition,
$\expect{N^2}$ equals an infinite series; find a closed form for this
series.


\solution{
We can compute the variance as follows:
\[
\variance{N}
         = \expect{N^2} - \expect{N}^2 
         = \sum_{k=1}^{\infty} k^2 \cdot \left(\frac{1}{2}\right)^k - 2^2 
         = \frac{\frac{1}{2} + (\frac{1}{2})^2}{(1 - \frac{1}{2})^3} - 4 
         = 6 - 4
         = 2
\]
The formula for the series was derived in Rosen and previous Notes.
}
\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 \eqdef \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 cannot 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 binomial distribution and the
binomial estimates from Lecture Notes do not apply.
}


\end{problemparts}
\end{problem}


% Problem: Hearts
          % Topics: Variance, Expectation
% Variants of this problem appeared in:
% SP 2000, PS 10.5, problem 3
% FA 2000, PS 11.5

\begin{problem}
Suppose you are playing the game ``Hearts'' with three of your friends.
In Hearts, all the cards are dealt to the players, in this case the four
of you will each have 13 cards.

\begin{problemparts}

\problempart
What is the expectation of the number of hearts in your hand?

\solution{
Let $H$ be the number of hearts in your hand, and let $X_i$ be the
indicator random variable for the event that the $i$th card in your
hand is a heart.  Then $H = \sum_{i=1}^{13} X_i$.  So
\[
\expect{H}  = \sum_{i=1}^{13} \expect{X_i}
        = \sum_{i=1}^{13} \Pr(\text{$i$th card is a heart}) 
        = \sum_{i=1}^{13} \frac{1}{4} = \frac{13}{4}.
\]
}

\problempart
What is the variance of the number of hearts in your hand?

\solution{
To compute variance, 
we first compute $\expect{H^2}$, 
following the solution to the Random Hat Check Problem.
\[
\expect{H^2} = \expect{\left(\sum_{i=1}^{13} X_i\right)^2}
        = \sum_i \expect{X_i} + \sum_i \sum_{j \neq i} \expect{X_i X_j} 
\]
Note that $X_i^2 = X_i$, so $\expect{X_i^2} = 1/4$.  
When $i \neq j$,
$X_i X_j = 1$ if cards $i$ and $j$ are both hearts, and 0 otherwise.  The
probability that both cards are hearts is $\binom{13}{2}/\binom{52}{2}$, 
so 
$\expect{X_iX_j} = \binom{13}{2}/\binom{52}{2} = 3/51$.  
In the summation above, there
are 13 $\expect{X_i^2}$ terms, and $13 \cdot 12 = 156$ terms of the
form $\expect{X_i X_j}$ with $i \neq j$.  Thus,
\[
\variance{H} = \expect{H^2} - \expectsq{H}
        = 13 \cdot \frac{1}{4} + 156 \cdot \frac{3}{51} - (\frac{13}{4})^2 
        \approx 1.864. 
\]
}

\problempart What is the expectation of the number of suits in your
hand?

\solution{ Let $N$ denote the number of suits in a hand.  Let $X_s$ be
the indicator random variable for the event that there is a spade in
the hand.  Define $X_h, X_d, X_c$ analogously for the three remaining
suits: hearts, diamonds, and clubs.  Then $N = X_s + X_h + X_d + X_c$.

The expectation of each of the indicator variables is the probability
that a hand contains the corresponding suit.  Thus, for $i \in \set{s,h,d,c}$
\[
\expect{X_i} = 1 -  \frac{\binom{52-13}{13}}{\binom{52}{13}} \approx 0.9872,
\]
because $\binom{52-13}{13}$ is the number of hands that are missing the
particular suit, and $\binom{52}{13}$ is the total number of hands.
\[
\expect{N}=\expect{X_s + X_h + X_d + X_c} = \expect{X_s} + \expect{X_h} +
\expect{X_d} + \expect{X_c} \approx 4 \cdot 0.9872 = 3.9488.
\]

}

\problempart What is the variance of the number of suits in your hand?

\solution{

To compute variance, we compute $\expect{N^2}$ directly, and then
$\variance{N} = \expect{N^2} - \expectsq{N}$.  We first calculate
$\Pr(N=i)$ for $i = 1,2,3,4$.
\[
\Pr(N=1) = \frac{4} {\binom{52}{13}} \approx 6.299 \times 10^{-12},
\]
because there are four possible hands of all one suit out of
$\binom{52}{13}$ possible hands of 13 cards.
\[
\Pr(N=2) = \frac{\binom{4}{2}\left[\binom{26}{13} - 2\right]}{\binom{52}{13}}
         \approx 9.827 \times 10^{-5},
\] 
because there are $\binom{4}{2}$ ways to choose which two suits.
There are $\binom{26}{13}$ ways to choose 13 cards from the 26
possible cards of those two suits.  Two of those $\binom{26}{13}$
hands actually contain only one suit.
\[
\Pr(N=3) = \frac{\binom{4}{3}
                    \left[\binom{39}{13} - \binom{3}{2}\binom{26}{13} 
                                + 3\right]}
                {\binom{52}{13}} \approx 0.05097,
\]
because there are $\binom{4}{3}$ ways to choose the three suits, and
$\binom{39}{13}$ ways to choose $13$ cards from the $39$ cards of
those three suits.  But that includes hands with only one or two
suits.  So, using Inclusion-Exclusion, we subtract the
$\binom{3}{2}\binom{26}{13}$ ways to choose two of the three suits and
then choose $13$ cards from the $26$ cards of those suits.  This
subtracts out the three hands with only one suit twice, so we add
these back.

Of course, 
\[
\Pr(N=4) = 1 - (\Pr(N=1) +\Pr(N=2) + \Pr(N=3)) \approx 0.9489.
\]
Thus, 
\begin{align*}
\expect{N^2} & = 1 \cdot \Pr(N=1) + 4 \cdot \Pr(N=2) 
                + 9 \cdot \Pr(N=3) + 16 \cdot \Pr(N=4) \\
        & \approx 0 + 0.0004 + 0.4587 + 15.1824 = 15.6415
\end{align*}
This allows us to complete the calculation of the variance:
\[
\variance{N} \approx 15.6415 - (3.9488)^2 \approx 0.0485.
\]
}

\end{problemparts}

\end{problem}


\begin{problem}

Random variables $R$ and $S$ are said to be \emph{uncorrelated} iff
\begin{equation}\label{ERS}
\expect{R\cdot S} = \expect{R} \cdot \expect{S}.
\end{equation}

\bparts

\ppart
Let $R$ be a random variable taking values $-1, 0, 1$ with a uniform
distribution and $S$ be the indicator variable
for the event $[R = 0]$.  Show that $R$ and $S$ are uncorrelated but are
not independent.
\solution{
Clearly, $\expect{R} = 0$.  Also,
note that $S=0$ iff $R \neq 0$, and hence $RS \equiv 0$.  So
\[
\expect{RS} = \expect{0} = 0 = 0 \cdot \frac{2}{3} = \expect{R}\expect{S},
\]
confirming that $R$ and $S$ are uncorrelated.

$R$ and $S$ are obviously not independent, since
\[
\prcond{R=0}{S=0} = 0 \neq \frac{1}{3} = \pr{R=0}.
\]

There are also examples of uncorrelated but dependent variables whose
expectations are nonzero.  For example, $R+2$ and $S+1$ are also
uncorrelated and only take positive values.}

\ppart
Explain how to strenthen the proof of the Pairwise Independent Sampling
Theorem of Notes 13 to obtain
\begin{corollary*}
\label{uncorsample}[Pairwise Uncorrelated Sampling]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i
\]
where $G_1, \dots, G_n$ are pairwise \emph{uncorrelated} variables with
the same mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Snx}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} \leq \frac{1}{n}
\left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{corollary*}

\solution{Call a set of variables $G_1, G_2, \ldots, G_n$ \emph{pairwise
uncorrelated} iff $G_i$ and $G_j$ are uncorrelated for all $i \neq j$.  A
look at the proof of the additivity of variances of pairwise independent
variables reveals that it used pairwise independence of two variables
only to conclude that they were uncorrelated.  In other words, without
changing the proof, the Pairwise Independent Additivity of Variance
theorem could be strengthened to
\begin{theorem*}[Pairwise Uncorrelated Additivity of Variance]
If $G_1, G_2, \ldots, G_n$ are pairwise \emph{uncorrelated} random
variables, then
\begin{equation}\label{th2:varsum}
\variance{G_1 + G_2 + \cdots + G_n} = \variance{G_1} + \variance{G_2} +
  \cdots + \variance{G_n}.
\end{equation}
\end{theorem*}

Similarly, a look at the proof of the Pairwise Independent Sampling
Theorem reveals that the only property needed of the $G_i$'s was the
additivity of their variances, so the proof of the Pairwise Independent
Sampling Theorem actually proves the Pairwise Uncorrelated version.}  

\eparts
\end{problem}


\begin{problem}
Let $R$ be a random variable with finite variance.  The ``one-sided''
version of Chebyshev's Theorem is:
\begin{equation}\label{1s}
\pr{(R - \expect{R}) \geq x} \leq \frac{\variance{R}}{x^2+ \variance{R}}
\end{equation}

Prove inequality~(\ref{1s}).

\hint $(R- \expect{R}) \geq x$ implies $(R- \expect{R} + a)^2 \geq (x +
a)^2$.  By Markov,
\[
\pr{(R-\expect{R} + a)^2 \geq (x + a)^2} \leq \frac{\expect{(R-\mu_R + a)^2}}{(x+a)^2}.
\]
Choose $a$ to minimize this last bound.

\solution{
\begin{proof}
Let $\mu \eqdef \expect{R}$.  Then     
\begin{align}
\pr{R-\mu \geq x} & \leq \pr{(R-\mu + a)^2 \geq (x + a)^2}
                          & \text{(from the hint)} \notag\\
   & \leq \frac{\expect{(R-\mu + a)^2}}{(x+a)^2}
                          & \text{(Markov  bound)} \notag\\
   & =  \frac{\expect{(R-\mu)^2} +2a(\expect{R}-\mu) + a^2}{(x+a)^2}
                & \text{(linearity of expectation)} \notag\\
   & =  \frac{\expect{(R-\mu)^2} + a^2}{(x+a)^2} & (\expect{R} = \mu) \notag\\
   & =  \frac{\variance{R} + a^2}{(x+a)^2} & \text{(def of variance)\label{Va}}.
\end{align}

Setting the derivative of~(\ref{Va}) with respect to $a$ to zero, we find
that $a = \variance{R}/x$ minimizes~(\ref{Va}).  Plugging in this value for
$a$, we have
\begin{align*}
\pr{R-\mu \geq x} & \leq \frac{\variance{R} +
\left(\variance{R}/x\right)^2}{\left(x+ \variance{R}/x\right)^2}
    & \text{($a = \variance{R}/x$ in~(\ref{Va}))}\\
    & = \frac{\variance{R}x^2 + \varsq{R}}{\left(x^2+
         \variance{R}\right)^2}
       & \text{(multiply by $x^2/x^2$)}\\
    & = \frac{\variance{R}(x^2 + \variance{R})}{\left(x^2+
\variance{R}\right)^2}\\
    & = \frac{\variance{R}}{x^2+ \variance{R}}.
\end{align*}

\end{proof}
}
\end{problem}


\begin{problem} %source: spring00 ps10-5
We have two coins: one is a fair coin and the other is a coin that
produces heads with probability 3/4.  One of the two coins is picked,
and this coin is tossed $n$ times.

\bparts

\ppart Does the Weak Law of Large Numbers allow us to \emph{predict}
what limit, if any, is approached by the expected proportion of heads
that turn up as $n$ approaches infinity?  Briefly explain.

\solution{ The Weak Law of Large Numbers tells us that the proportion
of heads will approach $1/2$ if the fair coin was picked, and it will
approach $3/4$ if the other coin was picked.  But it does not tell us
anything about which of these two numbers it will approach, as we have
no information about which coin is picked.  }

\ppart How many tosses suffice to make us 95\% confident which coin was
chosen?  Any sufficient number of tosses that does not depend on $n$ is
acceptable as an answer, but you should explain your answer.

\solution{
To guess which coin was picked, set a threshold $t$ between $1/2$ and
$3/4$.  If the proportion of heads is less than the threshold, guess
it was the fair coin; otherwise, guess the biased coin.  Let the
random variable $H_n$ be the number of heads in the first $n$ flips.
We need to flip the coin enough times so that $\pr{H_n/n > t} \leq
0.05$ if the fair coin was picked, and $\pr{H_n/n < t} \leq 0.05$ if
the biased coin was picked.  A natural threshold to choose is $5/8$,
exactly in the middle of $1/2$ and $3/4$.

$H_n$ is the sum of independent Bernoulli variables, which each have
variance $1/4$ for the fair coin and $3/16$ for the biased coin.
Using Chebyshev's Inequality for the fair coin,
\begin{align*}
\pr{\frac{H_n}{n} > \frac{5}{8} } 
        & = \pr{\frac{H_n}{n} - \frac{1}{2} > \frac{5}{8} - \frac{1}{2}} 
          = \pr{H_n - \frac{n}{2} > \frac{n}{8} } \\
        & = \pr{H_n - \expect{H_n} > \frac{n}{8} } 
          \leq \pr{|H_n - \expect{H_n}| > \frac{n}{8} } \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{n/4}{n^2/64} 
          = \frac{16}{n}
\end{align*}
For the biased coin, we have
\begin{align*}
\pr{\frac{H_n}{n} < \frac{5}{8} } 
        & = \pr{\frac{3}{4} - \frac{H_n}{n} > \frac{3}{4} - \frac{5}{8}} 
          = \pr{\frac{3n}{4} - H_n > \frac{n}{8} } \\
        & = \pr{\expect{H_n} - H_n > \frac{n}{8} } 
          \leq \pr{|H_n - \expect{H_n}| > \frac{n}{8} } \\
        & \leq \frac{\variance{H_n}}{(n/8)^2} 
          = \frac{3n/16}{n^2/64} 
          = \frac{12}{n}
\end{align*}
We are 95\% confident if these are at most $0.05$, 
which is satisfied if $n \geq 320$. 

Because the variance of the biased coin is less that of the fair coin, 
we can do slightly better if make our threshold 
a bit bigger, to about $0.634$, 
which gives 95\% confidence with 279 coin flips. 

Because $H_n$ has a binomial distribution, we can get a much better bound
using the estimates of the binomial distribution, which give 95\%
confidence when $n > 42$.}

\eparts

\end{problem}





\end{document}                            
