\documentclass[12pt]{article}
\input{macros-course}

\showsolutionstrue
\askaboutsolutions

\begin{document}

\ifshowsolutions
  \tutsol{12}{November 29, 2001}{\stamp}
\else
  \tutprobn{12}{November 29, 2001}{\stamp}
\fi

%% TUTORIAL 12: More Expectations, Variance, Deviation

\begin{problems}

\problem %From S99 Tutorial 13

Suppose you have learned that the average graduating MIT student's
total number of credits is 200.

\bparts

\ppart 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.  (Ignore the fact that students who graduate do so
after at most a century---that is, assume that there is no theoretical
upper bound on the possible number of credits a student may earn.)

Explain why this is a best possible bound.  In other words, describe a
distribution for which this bound holds with equality.

\solnospace{ 
By Markov's inequality $\prob{X\geq c}\leq\expect{X}/c$, with 
$c = 235$, giving the upper bound $200/235 \approx 0.85$.

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

You might wonder how we got to this particular distribution, since the
space of all possible probability functions is very large \texttt{:-)}.
This function could be derived intuitively as follows:

Consider any distribution with the given mean, $\expect{X}=200$.  We can
`shift' this distribution around, like sand on a see-saw, subject to the
constraint that it remains balanced around the mean.  We want to maximize
the portion of the distribution that is to the right of the point $x=235$.

How can we do this?  Look at the portion of the distribution to the right
of $x=235$.  We need to minimize this portion's contribution to the mean
(so we can then maximize its volume).  \iffalse UNCLEAR, SHOULD BE REVISED
TO CONSISTENT MAINTAIN THE SEE-SAW ANALOGY\fi For this, we must move it
as close to the mean as possible, i.e. we pile it all up at the point
$x=235$.

Similarly, we need to maximize the contribution of the distribution to
the left of the mean.  To do this, we move it \emph{away} from the
mean, i.e. to the left as far as possible.  Since $X$ is non-negative,
this means that it all piles up at the point $x=0$.

Mathematically
\iffalse
\begin{math}
\begin{array}[rcrlcrl]
\expect{X} & = & \expect{X|X\ge c} & \pr{X\ge c} & + & \expect{X|X<c}
& \pr{X<c}\\
&\ge&c\cdot&\pr{X\ge c}&+&0\cdot&\pr{X<c}\\
&=&\multicolumn{5}{l}{c\cdot\pr{X\ge c}}
\end{array}
\end{math}
\fi
\begin{eqnarray*}
\expect{X}&=&\expect{X|X\ge c}  \pr{X\ge c}  +  \expect{X|X<c}
 \pr{X<c}\\
&\ge&c\cdot\pr{X\ge c}+0\cdot\pr{X<c}\\
&=&c\cdot\pr{X\ge c}
\end{eqnarray*}
Equality holding iff $\expect{X|X\ge c}=c$ AND $\expect{X|X<c}=0$,
i.e. $x\ge c\Rightarrow x=c$ and $x<c\Rightarrow x=0$.
}

\ppart Suppose you are now told that no student can graduate with fewer
than 170 units.  How does this allow you to improve your previous answer?

As in the first part, show that this is the best possible bound.

\solnospace{
We can now apply Markov's inequality to the nonnegative variable $X -
170$, obtaining 
$$\prob{X \geq 235} = \prob{X - 170 \geq 235 - 170} \leq
\expect{X - 170}/(235 - 170) = 30/65 \approx 0.46$$

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*}
}

\ppart Now suppose you further learn that the standard deviation of the
total credits per graduating student is~7.  Give a best possible bound on the
fraction of students who can graduate with at least 235 credits.

(Optional) As in previous parts, show that this is a best possible
bound. 

\solnospace{
Use the one-way Chebyshev inequality
\[
\prob{X \geq \expect{X} + c \sigma_X} \leq \frac{1}{1+c^2}
\]
with $c = 5$ to get an upper bound of $1/26$.

The correct distribution yet again turns out to be a two-point
distribution.
\begin{eqnarray*}
\prob{X=235} &=& 1/26\\
\prob{X=198.6} &=& 25/26\\
\prob{X=x} &=& 0\text{ for all other }x
\end{eqnarray*}

Intuitively showing that $1/26$ this is the best possible bound turns out to
be somewhat tricky.  To be honest, this question baffled the staff for
quite a while!  We use the following Lemma:

\begin{lemma*}\label{eq:variancelemm}
For any random variable $X$, and any disjoint events $Y_1,
Y_2, Y_3...$ whose union spans the sample space,
\begin{eqnarray*}
\variance{X}+\expectsq{X}&=&\expect{X^2}\\
&=&\sum_i\pr{Y_i}\expect{X^2|Y_i}\\
&=&\sum_i\pr{Y_i}\left(\variance{X|Y_i}+\expectsq{X|Y_i}\right)
\end{eqnarray*}
\end{lemma*}

Now suppose we're given an arbitrary
probability distribution (mean $\mu$, variance $\sigma^2$) and want to tweak it
around to maximize $\pr{X\ge 235}$.  We can do this in two steps.
First, we shift it to minimize the variance while maintaining the mean
and the probability that $X\ge 235$.  Then, we shift around this new
distribution while maintaining the mean and raising the variance to
its original value of $\sigma^2$, and simultaneously increasing $\pr{X\ge
  235}$.

Define $Y_1\equiv(X<235)$, $Y_2\equiv(X\ge 235)$.  Then let us maintain
$\expect{X}$, $\pr{Y_1}$, $\expect{X|Y_1}$, and the distribution of
$\pr{X|Y_2}$ as constant.  From the Lemma\iffalse
~\eqnref{eq:variancelemm}\fi, it follows that we can minimize
$\variance{X}$ iff we minimize $\variance{X|Y_1}$.  As it happens, we can
bring $\variance{X|Y_1}$ down to 0.  We simply compress the pdf left of
235 into a spike at its mean value.  This will maintain $\pr{Y_1}$ and
$\expect{X|Y_1}$, and clearly will also maintain
$\expect{X}=\pr{Y_1}\expect{X|Y_1}+\pr{Y_2}\expect{X|Y_2}$.

Having done this, we can further reduce the variance of the
distribution by applying the same process to $Y_2$:  that is,
compressing the pdf for $X|Y_2$ into a spike at its mean value.

We now have a pdf with two spikes --- one to the left of $x=200$ and
one to the right of $x=235$.  We can still reduce the variance
further!  We shift the right spike to the left until it hits $x=235$,
while simultaneously shifting the left spike to the right in such a
way as to maintain the expected value (200) of the overall system.  Since
both spikes are moving towards the mean, the variance will fall.  We
now have the lowest possible variance we can achieve without changing
$\expect{X}$ or $\pr{X\ge 235}$.

We now move to the second stage:  we shift the left spike to the
left, while reducing its height and adding to that of the right
spike, in such a way that the center of mass of the two spikes stays
the same.  Doing so will potententially raise the variance of the
whole pdf;
hence, we can only continue this shift until the variance has risen back to
its original value, $\sigma^2$.

What is the eventual result of all this shifting?  We have a 2-spike
distribution with the mean at $\mu=200$, the variance $\sigma^2=49$
and the right spike at the point $x=\mu+c\sigma=235$.  Let $p_1$ and
$p_2$ be the heights of the left and right spikes, and $\delta$ be the
distance of the left spike from the mean.  Then

\begin{eqnarray*}
p_1+p_2&=&1\\
p_1\delta&=&p_2c\sigma\\
p_1\delta^2+p_2c\sigma^2&=&\sigma^2
\end{eqnarray*}
Solving gives $\pr{X\ge\mu+c\sigma}=p_2=1/(1+c^2)$, our desired
optimal bound.
}

\eparts

\problem
Suppose we have a calculation that will require $n$~operations to
complete, and our computer has a mean time to failure of
$f$~operations where the failure process is memoryless.  When the
computer fails, it loses all state, so the calculation has to be
restarted from the beginning.

\bparts
\ppart Louis Reasoner decides to just run the calculation over and
over until it eventually completes without failing. If the calculation
ever fails, Louis restarts the entire calculation. Give a lower bound
on the time that Louis can expect to wait for his code to complete
successfully on a typical gigahertz processor ($10^{12}$ operations per
second), with $n = 10^{13}$ and 
$f = 10^{12}$? 
%\hint $(1-p)^n \leq e^{-pn}$ for all $p \in [0,1]$ and
%$(1-p)^n \geq e^{-(p-p^2)n}$ for all $p \in [0,1/\sqrt{2}]$.

\hint $e^{-(p-p^2)n}\leq (1-p)^n \leq e^{-pn}$ for all $p \in [0,1/\sqrt{2}]$.

\solnospace{
This part and the next were discussed in
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l13.pdf}{Notes
13.3}, where Wald's Theorem is used to show that
\begin{equation*}
\expect{T} = \frac{1}{p}(\frac{1}{(1-p)^n} - 1).
\end{equation*}

The hint now tells us that
  \begin{displaymath}
    \expect{T} \geq \frac{e^{pn}-1}{p} = 10^{12} \cdot (e^{10} - 1),
  \end{displaymath}
so the expected \emph{time} to complete the task is at least $e^{10}
- 1$ seconds, or roughly 6~hours. Since the operation should only
take 10~seconds in the absence of failures, this is quite a penalty.}

\ppart Alyssa P. Hacker decides to divide Louis's calculation into
10 equal-length parts, and has each part save its state when it
completes successfully. Saving state takes time~$s$. When a failure
occurs, Alyssa restarts the program from the latest saved state. How
long can Alyssa expect to wait for her code to complete successfully
on Louis's system? You can assume that $s < 10^{-4}$~seconds.

\solnospace{Now we have to do 10 calculations each of which can be
computed without regard to previous failures.  So by the previous
analysis, Alyssa expects the $i$th component to take
\[
    \expect{T_i} \geq \frac{e^{pn}-1}{p} = 10^{12} (e - 1)
\]
operations (note that $n = 10^{12}$). So, the expected number of
operations for the entire computation is
\[
\expect{\sum_{i=1}^{10} T_i} = 
\sum_{i=1}^{10} \expect{T_i} = 10^{13} (e - 1),
\]
giving an expected total computing time of roughly 17~seconds.  The 10
state saves take time $10 \cdot 10^{-4} = 10^{-3}$ seconds, which is
negligible.}

\ppart Alyssa tries to further optimize the expected total computing
time by dividing the calculation into 10\,000 parts instead of~10.
How long can Alyssa expect to wait for her code to complete
successfully? 

\hint $1+np\leq (1-p)^{-n}<1 + np + 2n^2p^2$ for all $np \in
[0,1], n>3$.

\solnospace{
As before,
%\geq \frac{e^{pn}-1}{p} = \frac{1 + pn + O((pn)^2) - 1}{p}
\begin{eqnarray*} 
  \expect{T_i} &=& \frac{1}{p}\biggl(\frac{1}{(1-p)^n} - 1\biggr)\\
  &=& \frac{1 + pn + \delta(pn)^2 - 1}{p}\\
  &=& n(1 + \delta pn) 
\end{eqnarray*} 
with $0\leq\delta<2, n = 10^{13} / 10000 = 10^9$. So, the expected
number of operations for the entire computation, excluding state saves,
is roughly $10^{13}$ (since $p = 10^{-12}$ and $n = 10^9$, we ignore the
$\delta pn$ term).  This time the $10^{4}$ state saves are not
negligible, but only take one second, giving a total time of 11~seconds.}

\eparts


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

\solnospace{
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?
Explain.

\solnospace{ 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 $D_n$ be the number of heads in the first $n$ flips.  We
need to flip the coin enough times so that $\Pr(D_n/n > t) \leq 0.05$ if
the fair coin was picked, and $\Pr(D_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$.

$D_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\left(\frac{D_n}{n} > \frac{5}{8} \right) 
        & = \Pr\left(\frac{D_n}{n} - \frac{1}{2} > \frac{5}{8} - \frac{1}{2}\right) 
          = \Pr\left(D_n - \frac{n}{2} > \frac{n}{8} \right) \\
        & = \Pr\left(D_n - \expect{D_n} > \frac{n}{8} \right) 
          \leq \Pr\left(|D_n - \expect{D_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{D_n}}{(n/8)^2} 
          = \frac{n/4}{n^2/64} 
          = \frac{16}{n}
\end{align*}
For the biased coin, we have
\begin{align*}
\Pr\left(\frac{D_n}{n} < \frac{5}{8} \right) 
        & = \Pr\left(\frac{3}{4} - \frac{D_n}{n} > \frac{3}{4} - \frac{5}{8}\right) 
          = \Pr\left(\frac{3n}{4} - D_n > \frac{n}{8} \right) \\
        & = \Pr\left(\expect{D_n} - D_n > \frac{n}{8} \right) 
          \leq \Pr\left(|D_n - \expect{D_n}| > \frac{n}{8} \right) \\
        & \leq \frac{\variance{D_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 $D_n$ has a binomial distribution, 
%%we can get a much better bound using the estimates 
%%from Lecture 21, 
%%giving 95\% confidence when $n > 42$. 
}

\eparts



\problem
The St.\ Petersburg Casino offers the following game: the gambler bets a
fixed wager, and then the dealer flips a fair coin (dealers do not flip
coins in US casinos, but they do in St.\ Petersburg) until it comes up
heads. The gambler receives \$1 if the coin shows heads the first time,
\$2 if it shows the first head at second toss, and in general $\$2^{k-1}$
if the dealer tosses the coin $k$ times to get the first head.

\bparts
\ppart Suppose the fixed wager is \$10.  What is the expected amount of
money that the gambler will win in this game?  Suppose the fixed wager is
\$10,000?

\solnospace{
Let $V$ be the random variable corresponding to the amount of money
that the gambler is paid by the dealer. The distribution of
$V$ is as follows: for any $n\geq 1$,
\[
\prob{V= 2^{n-1}} = 2^{-n},
\]
where the probability refers to the event that the dealer
tosses $n-1$ tails followed by a head.
The average of $V$ is
\[
\expect{V} = \sum_{n=1}^{\infty} [2^{-n} 2^{n-1}]
= \sum_{n=1}^{\infty} 1/2 = \infty.
\]
So whatever the fixed wager, the gambler expects to win an infinite amount.}

\ppart What is the probability that the gambler does not lose money in a
game when the fixed wager is \$10,000?

\solnospace{
The probability of recovering the
money of the wager is only
\begin {eqnarray*}
\prob{V \geq 10,000} & = & \prob{V \geq 2^{14}}\\
& = & \prob{\mbox{dealer flips at least 14 consecutive tails}}\\
& = & 2^{-14} = \frac{1}{16,384}
\end {eqnarray*}
}

\ppart In reality, it would not be reasonable for the gambler to play the
game with the fixed wager at \$10,000.  Why?  \hint Suppose the casino
goes bankrupt.

\solnospace{
In reality, the casino goes bankrupt after a relatively
small number of consecutive tails, so the gambler's win in bounded by the
casino's net worth.  This makes the expectation finite.  Optional exercise:
what should the casino's net worth be in order for the gambler's
expectation to be positive?}

\eparts


\iffalse
%Spring 98, tutorial 13
\problem

Let $X$ be a non-negative random variable with expectation
$n/2$. Markov's inequality implies that
\begin{equation}\label{eq:mark}
\pr{ X \geq \frac 23 n} \leq \frac 34 .
\end {equation}

\bparts

\ppart
Define a random variable $X$ with expectation $n/2$ such
that the bound~\eqnref{eq:mark} holds with equality.

\solnospace{
Let $X$ take the value 0 with probability $1/4$, and the value $2n/3$
with probability $3/4$.  Then clearly bound~\eqnref{eq:mark} is
satisfied, and 
$$
\expect{X}=0\cdot\frac 14 + \frac{2n}3\cdot\frac 34 = n/2
$$
This is the only distribution with expectation $n/2$ for which the
bound holds with equality.
}
\ppart If
$X_1,\ldots,X_n$ are a collection of {\em independent} unbiased Bernoulli
variables over the same sample space, then $X = \sum_i X_i$ has
expectation $n/2$ and is non-negative, therefore bound~\eqnref{eq:mark}
applies. Unfortunately it is exceedingly inaccurate.
However, under the general hypotheses for Markov's inequality
(where no independence is assumed) bound~\eqnref{eq:mark}
is the best one can hope for.

Define a sample space and unbiasied Bernoulli variables $X_1,\ldots,X_n$
on it, such that for $X = \sum_{i=1}^n X_i$ the
  bound~\eqnref{eq:mark}
holds with equality (assume $n$ is a multiple of 3).

[Hint:  the variables will have to be dependent. 
The event $X_1= \cdots =X_n = 0$ has probability $1/4$
in the sample space.]

\solnospace{
\iffalse
Consider the sample space where $X_1 = \cdots = X_n = 0$ occurs with
probability $1/4$, and where for any $i=1,\ldots,n$, the event
$(X_1,\ldots,X_n) = \mbox{shift}_k (0^{n/3}1^{2n/3})$ happens with
probability $3/4n$.  The notation $\mbox{shift}_k (a_1,\ldots,a_n)$, where
$a_1,\ldots,a_n$ is a binary string, stands for the string $(a_{k+1}\cdots
a_{n}a_1\cdots a_{k})$ obtained by doing a $k$ times a cyclic shift to the
left of the string $a_1,\ldots,a_n$.  Notice that with probability exactly
$3/4$ exactly a fraction $2/3$ of the $X_i$ get value $1$, therefore
expression~\eqnref{eq:mark} is satisfied with equality.  We have to check
that for any $i$ we have $\pr {X_1 = 1} = 1/2$. This follows from the fact
that there are exactly $2n/3$ shifts such that $X_i=1$, each one happening
with probability $3/4n$; since they are disjoint events we can sum their
probability, and their sum is $1/2$.
\fi
%Simpler answer

From the first part, we want $X = \sum_i X_i$ to be $0$ with
probability $1/4$, and $2n/3$ with probability $3/4$.  One way to
accomplish this is to let $(X_1,\ldots,X_n)$ be chosen uniformly from
$(0^{3m})$, $(0^{m}1^{2m})$, $(1^{m}0^{m}1^{m})$, $(1^{2m}0^{m})$
where $m=n/3$.

With probability $3/4$, exactly $2n/3$ of the $X_i$ get value $1$,
therefore expression~\eqnref{eq:mark} is satisfied with equality.  To
show the $X_i$'s are unbiased, note that each $X_i$ gets value 1 in
exactly 2 of the 4 outcomes.  So $\pr{X_1=1} = 2/4 = 1/2$.

}
\eparts
\fi

\end{problems}

\end{document}

\iffalse
\problem %source: spring00 ps10-5
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.
\bparts
\ppart
What is the expectation and variance of the number of hearts in your hand?

\solnospace{
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}.
\]

To compute variance, 
we first compute $\expect{H^2}$, 
following the solution to Problem~4c. 
\[
\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} - \expect{H}^2
        = 13 \cdot \frac{1}{4} + 156 \cdot \frac{3}{51} - (\frac{13}{4})^2 
        \approx 1.864. 
\]
}
\ppart What is the expectation and variance of the number of suits in
your hand?

\solnospace{
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.
\]
To compute variance, we compute $\expect{N^2}$ directly, 
and then $\variance{N} = \expect{N^2} - \expect{N}^2$. 
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.
\]
}
\eparts

% Saw this in another class I took --Ashish
\problem
Suppose we are trying to estimate some physical parameter $p$.  When
we run our experiments and process the results, we obtain an estimator
$p_e$.  But if our experiments are probabilistic, then $p_e$ itself is a
random variable which has a pdf over some range of values.  We call it
an \emph{unbiased} estimator if $E[p_e]=p$.

Say we take $n$ independent observations of a random variable $X$.
Recall from lecture notes the efficient estimator of Var[$X$]:
\begin{eqnarray*}
\variance{X}
        & = & \expect{X^2} - \expectsq{X} \\
        & \approx & \frac{x_1^2 + x_2^2 + \ldots + x_n^2}{n} -
                \left(\frac{x_1 + x_2 + \ldots + x_n}{n}\right)^2.
\end{eqnarray*}
Is this an unbiased estimator of the variance?  If not, can you
suggest how to modify this estimator to make it unbiased?

\solnospace{
Let $\sigma^2=\variance{X}, \mu=\expect{X}$.  Then our estimator
$\sigma^2_e$ is given by
\begin{eqnarray*}
\sigma^2_e&=&\frac{\sum
  x_i^2}{n} - \left(\frac{\sum x_i}{n}\right)^2\\
\expect{\sigma^2_e}&=&\expect{\frac{\sum
  x_i^2}{n} - \left(\frac{\sum x_i}{n}\right)^2}\\
&=&\frac{\sum
  \expect{x_i^2}}{n} - \frac{\expect{(\sum x_i)^2}}{n^2}\\
&=&\frac{\sum(\sigma^2+\mu^2)}{n} - \frac{\variance{\sum
    x_i}+\expectsq{\sum x_i}}{n^2}\\ 
&=&\frac{n(\sigma^2+\mu^2)}{n} - \frac{n\sigma^2+n^2\mu^2}{n^2}\\
&=&\sigma^2\left(1-\frac{1}{n}\right)
\end{eqnarray*}
So this gives a biased estimator, but we can make it
unbiased simply by multiplying by $\frac{n}{n-1}$.
\begin{eqnarray*}
E\left[\frac{n\sigma^2_e}{n-1}\right]&=&\sigma^2
\end{eqnarray*}
}

%Fall 97 Tutorial 12
\problem
We are trying to collect baseball
cards. Assume there are $n$ different cards. We can buy them one
at a time. When we buy a card, 
it is equally likely that we get any one of the $n$ cards, and purchases
are mutually independent.
We want to study how many cards we need to buy before we get one each 
of the $n$ different kinds. 
\bparts
\ppart
Suppose we already have $k$ different cards. What is the expected
number of cards we need to buy to get a new card?

\solnospace{
Define 
$X_k$ to be the random variable denoting the number of purchases to get the $(k+1)^{th}$ new card, after getting
$k$ different cards.  

After getting $k$ different cards, a new purchase has
probability ${n-k \over n}$ of getting a new card. We can view each new 
purchase as Bernoulli trial with probability of success $p = {n-k \over n}$.
Hence the expected number of trials to success is ${1 \over p} = {n \over n-k}$.  That is,
$$E(X_k) = {n \over n-k}$$
}
\ppart
Using the above, what is the expected number of cards we
need to buy to get one of each kind?

\solnospace{
Since $X_0 = 1$, the number of purchases we need is $1+\sum_{i=1}^{n-1}X_i$.
By linearity of expectation,
\begin{eqnarray*}
E(1+\sum_{i=1}^{n-1} X_i) &=& 1+\sum_{i=1}^{n-1}E(X_i)\\
&=& 1+\sum_{i=1}^{n-1} {n \over n-i}\\
&=& n\sum_{i=1}^{n} { 1 \over i}\\
&=& n{\cal H}_n \sim n \ln n+\gamma n+\Theta(1)
\end{eqnarray*}
Where $\gamma$ is Euler's constant.
}
\ppart
Suppose we buy $n\ln n+cn$ cards, where $c>0$ is a real number.
What is the probability that we don't have the $1^{st}$ card?

\solnospace{
Let $A_1$ be the event that we don't have the first card
in $n\ln n + cn$ trials.

In any single trial the probability that we don't get $A_1$ is
$(1 - {1 \over n})$. Since the trials are independent,
$$Pr(A_1) = (1-{1 \over n})^{n \ln n + cn}$$
$$ \leq e^{-{1 \over n} (n \ln n +cn)}$$
$$ = e^{-\ln n + c} = {e^{-c} \over n}$$
}
\ppart
What is an upper bound on 
the probability that we don't have all $n$ cards?

\solnospace{
Let $A_i$ be the event that we don't have the $i^{th}$ card after
$n \ln n + cn$ trials. 

Then the probability that we don't have all the cards is
$$Pr(A_1 \cup \ldots \cup A_n) \leq \sum_{i=1}^n Pr(A_i)$$
by Boole's inequality.
But this is 
$$ = n {e^{-c} \over n} = e^{-c}$$
}
\eparts
\fi
