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

\newcommand{\Fib}{{\sf Fib}}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \psetsol{12}{December 7, 2001}{\stamp}
\else
  \pset{12}{November 28, 2001}{Wednesday, December 5, beginning of lecture}{\stamp}
  \collaborationnote
\fi

\reading
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l13.pdf}
{Week 13 Notes}. 

\begin{problems}



%%%%
%%%%
%%%% PROBLEM 1
%%%%
%%%%

\problem{\bf Waiting for Godot}  

A couple plans to have children until they have a boy,
whom they'd like to name Godot.  What
is the expected number of children that they will have, and what is the
variance?

\hint You may need to reread Section 2.6 in
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l7.pdf}{Lecture
  Notes 7} on how to sum a series using differentiation.

\bparts

%\solution{The probability of having a single child (a boy) is
%$\frac{1}{2}$, the probability of having two children (a girl and then
%a boy) is $\frac{1}{4}$, and so forth; the probability of having $k$
%children is $\frac{1}{2^k}$.  Therefore, the expected number of
%children is:

%\begin{eqnarray*}
%\expect{\text{children}}& = &  \sum_{k=1}^{\infty} k \cdot \frac{1}{2^k} \\
%                       & = &   2
%\end{eqnarray*}


\solution{
\medskip
\textbf{Solution:}

Let $C$ be the expected number of children up to and including
the first boy. 
Each time the couple has a child, the probability that it is a boy is $1/2$.
Thus
$$\expect{C} = 2$$
as shown in lecture.
We can compute the variance as follows:
\[
\variance{C}
         = \expect{C^2} - \expect{C}^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 sum is computed by differentiating the
formula for the sum of an infinite geometric sequence.
}

\eparts






%%%%
%%%%
%%%% PROBLEM 2
%%%%
%%%%

%[[[expectation, variance, Chebyshev]]]
%Spring 00, problem set 10.5, problem 4

\problem {\bf A Random Hat-Check}

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\ge 2$ people have their hats returned at random.  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

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

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

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

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

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

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

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

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

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

\solnospace{
\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 21 do not apply.
}

\eparts





%pset10 problem9 spring98 (not used)
\problem {\bf Harry Potter mania}

We want to determine the percentage $r$ of people who intend to watch
the {\em Harry Potter} movie.   Since we are better at probability 
than magic, we conduct a poll.  Say that we poll a total of 800 people. 
What is the confidence level
that our estimated value is within 4 percentage points
of the actual value $r$?  Compute two lower bounds on the confidence 
level, one using Chebyshev's Inequality 
and the other using the binomial distribution
approximation.


\solnospace{

For this problem, we have the number of people polled $n=800$, the error $\epsilon=0.04$, and the actual percentage of people who intend to watch the movie $p=r$.  Let $\delta$ be the probability that the error is greater than $\epsilon$, and correspondingly, let $c = 1-\delta$ be the confidence level.

From Lecture Notes 12, equation (15), we know that
 
$$Pr(more than \epsilon error)   \leq    F_{n,p} ((p-\epsilon)n) 
                                        + F_{n,1-p} ((1-p-\epsilon)n)$$

We don't know $p$, but we do know from Fact 3.2 that the RHS is
maximized when $p=1/2$.  Therefore

\begin{eqnarray*}
\delta  & \leq  &  F_{n,1/2} ((1/2-\epsilon)n) + F_{n,1/2} ((1 - 1/2 \epsilon)n) \\
          & =     &  2 F_{n,1/2} ((1/2 - \epsilon) n)  \\ 
          & \leq  &  k_1         
\end{eqnarray*}

Thus we have $c = 1-\delta \geq k_1$.


Similarly, using Lecture Notes 13, we know that

$$\delta  \leq  \frac{\sigma^2}{n e^2}$$

We know that the variance, $\sigma^2 = p(1-p)$, but again, we do not know $p$.
However, as the Lecture Notes explain, $\sigma$ is maximized at $p=1/2$, and therefore we can say that

$$\delta  \leq  \frac{1/4}{n e^2}  = k_2$$.
 
Thus we obtain our second estimate $c = 1 - \delta \geq  k_2$.


}










\problem {\bf An Unbiased Estimator}

Suppose we are trying to estimate some physical parameter $p$.  When
we run our experiments and process the results, we obtain an estimator of $p$, call it
$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 the random
variable $p_e$
an \emph{unbiased} estimator if $\expect{p_e}=p$.

For example, say we are trying to estimate the height, $h$, of Green Hall.  However,
each of our measurements has some noise that is, say, Gaussian with zero mean.  So each 
measurement can be viewed as a sample from a random variable $X$.
The expected value of each measurement is thus $\expect{X} = h$, since the probabilistic
noise has zero mean.
Then, given $n$ independent trials, $x_1, ..., x_n$, 
an unbiased estimator for the height of Green
Hall would be
$$h_e = \frac{x_1+...+x_n}{n},$$
since
$$\expect{h_e} = \expect{\frac{x_1+...+x_n}{n}} = \frac{\expect{x_1} + ... + \expect{x_n}}{n} = \expect{x_1}= h.$$

Now say we take $n$ independent observations of a random variable $Y$.  Let 
the true (but unknown) variance of $Y$ be $\variance{Y} = \sigma^2$.
Then (see section 6.4 in the
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l13.pdf}{notes}),
we can define the following estimator $\sigma_e^2$ for $\variance{Y}$ 
using the data from our observations:

$$\sigma_e^2 =  \frac{y_1^2 + y_2^2 + \ldots + y_n^2}{n} -
                \left(\frac{y_1 + y_2 + \ldots + y_n}{n}\right)^2.$$

%\begin{eqnarray*}
%\variance{Y}
%%        & = & \expect{Y^2} - \expectsq{Y} \\
%%        & \approx & \frac{y_1^2 + y_2^2 + \ldots + y_n^2}{n} -
%                \left(\frac{y_1 + y_2 + \ldots + y_n}{n}\right)^2.
%\end{eqnarray*}

Is this an unbiased estimator of the variance?   In
other words, is $\expect{\sigma_e^2} = \sigma^2$?   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
  y_i^2}{n} - \left(\frac{\sum y_i}{n}\right)^2\\
\expect{\sigma^2_e}&=&\expect{\frac{\sum
  y_i^2}{n} - \left(\frac{\sum y_i}{n}\right)^2}\\
&=&\frac{\sum
  \expect{y_i^2}}{n} - \frac{\expect{(\sum y_i)^2}}{n^2}\\
&=&\frac{\sum(\sigma^2+\mu^2)}{n} - \frac{\variance{\sum
    y_i}+\expectsq{\sum y_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*}
\expect{\frac{n\sigma^2_e}{n-1}}&=&\sigma^2
\end{eqnarray*}
}





% adapted from Fall 95 tutorial 10, Problem 2
 % and Fall 98 tutorial 12, problem 2

\problem {\bf Lost in Infinite Corridors}

A distressed Harvard student, lost in the underground corridors of MIT, finds
himself in a room containing three doors.  Door 1 leads him to freedom
(out of MIT) after one hour of travel; door 2 returns him to the same
room after four hours travel, and door 3 returns him to the room after
seven hours travel.  Each time he finds himself in the room, the confused and memory-less
Harvard student picks a door with equal probability.
Let $T$ denote the time until he finds the exit.

\bparts

\ppart Let T be the total number of hours before he finds the exit.
Define a sequence of independent
identically distributed random variables $R_i$ and a stopping time
$Q$ such that

\begin{displaymath}
T = \sum_{i=1}^{Q}{R_i}
\end{displaymath}

\solnospace{
We view this an experiment where at each step the student makes a choice
between three equally likely outcomes.  We define $R_i$ as the number of
hours to return to the same room, or to escape, starting at the $i$th
step.  The experiment does not end.  That is, as soon as the student
escapes, he is doomed, like Sisyphus, to be stuck back in the room and
start trying to escape again.  This ensures that there is an $i$th step
for all $i \ge 0$, and that the $R_i$ are identically distributed (they
are also independent, though this fact is not needed in applying Wald's
Theorem).  In particular, $\pr{R_i=1}=\pr{R_i=4}=\pr{R_i =7}=1/3$, and
$\expect{R_i} = (1+4+7)/3=4$.

Define $Q$ to be the number of steps from the first step until the escape
door is selected \emph{for the first time}.  Now $Q$ is geometrically
distributed with probability $1/3$ and $\expect{Q}=3$.
}


\iffalse
\ppart Is $R_k$ independent of the event that $Q\geq k$?
Is $R_k$ independent of $Q$?

\solnospace{
$R_i$ is \emph{not} independent of $Q$.  For
example, if $Q=i$, then it must be that the student found the escape door
at the $i$th step, and so $\pr{R_i = 1 | Q=i} =1 \neq 1/3 = \pr{R_i = 1}$.

However, suppose we are given that the student has never managed to escape
before the $i$th step, that is, that $Q \ge i$.  Then we can observe that
the experiment starting at the $i$th step has exactly the same structure
as the experiment at the first step---where we were given, implicitly,
that the student had not escaped before the first step.  So we can
conclude that the distribution of $R_i$ given $Q \ge i$ is the same as
that of $R_1$ given that $Q\ge 1$, that is, the same as $R_1$, which we
already observed is the same as $R_i$.  In other words, $R_i$ is
independent of the event that $Q \geq i$, as required.
}
\fi


\ppart Use Wald's Theorem to find $\expect{T}$.

\solnospace{
Since Wald's Theorem is applicable, we conclude
\[\expect{T} = \expect{\sum_{i=1}^Q R_i}  = 3 \times 4 = 12.\]
}


\ppart Now suppose that an MIT student is also lost and finds herself in a 
similar situation to the Harvard student.  Of course, the MIT student never chooses the 
same door twice.  What is $\expect{T}$ for the MIT student?

\solnospace{
The problem can be solved by complete
enumeration; call $A$ the door that leads out, $B$ the door that leads
back in four hours, and $C$ the door that leads back in seven hours. The
possible events are

\begin {itemize}

\item
$A$ with probability $1/3$, in which case $T=1$

\item
$BA$ with probability $\frac 12 \cdot \frac 13 = \frac 16$, in which case $T=5$;

\item
$BCA$ with probability $\frac 12 \cdot \frac 13 \cdot 1 = \frac 16$, in which case $T=12$;

\item
$CA$ with probability $\frac 12 \cdot \frac 13  = \frac 16$, in which case $T=8$;

\item
$CBA$ with probability $\frac 12 \cdot \frac 13 \cdot 1 = \frac 16$, in which
case $T=12$.

\end {itemize}

The average of $T$ this time is $\expect{T} = 39/6 = 6.5$.
}
\eparts






\iffalse

%%%%
%%%%
%%%% PROBLEM 10
%%%%
%%%%



\problem %source: spring00 ps10-5
Let $X$ and $Y$ be independent random variables taking on
integer values in the range $1$ to $n$ uniformly.  Compute the
following quantities: 

\begin{problemparts}

\problempart $\variance{aX+bY}$

\solution{First, we compute $\variance{X}$, 
which is also $\variance{Y}$ since $X$ and $Y$ are identically distributed.
\begin{align*}
\variance{X}
        & = \expect{X^2} - \expect{X}^2 
        = \sum_{i=1}^n i^2 \cdot \frac{1}{n}
                - \left( \sum_{i=1}^n i \cdot \frac{1}{n} \right)^2 \\
        & = \frac{(n+1)(2n+1)}{6} - \frac{(n+1)^2}{4} 
        = \frac{n^2 - 1}{12}
\end{align*}

We now use this to compute $\variance{aX + bY}$: 
\begin{align*}
\variance{aX+bY}
        & = \variance{aX} + \variance{bY} 
                & & \text{because $aX$ and $bY$ are independent} \\
        & = a^2 \variance{X} + b^2 \variance{Y}
                & & \text{Theorem~4.4 in Lecture Notes 24} \\
        & = (a^2 + b^2) \variance{X}
                & & \text{because $\variance{X} = \variance{Y}$} \\
        & = (a^2 + b^2) \frac{n^2 - 1}{12}
                & & \text{substitution from computation above}
\end{align*}
}

\problempart $\expect{\max(X,Y)}$

\solution{
First we compute the probability that the maximum of $X$ and $Y$ 
is equal to $i$: 
\begin{align*}
\Pr(\max(X,Y) = i) 
        & = \Pr(X \leq i \land Y \leq i) - \Pr(X < i \land Y < i) \\
        & = \Pr(X \leq i) \Pr(Y \leq i) - \Pr(X < i) \Pr(Y < i) \\
        & = \frac{i}{n} \cdot \frac{i}{n} 
                - \frac{i-1}{n} \cdot \frac{i-1}{n} \\
%       & = \frac{i^2 - (i-1)^2}{n^2} \\
        & = \frac{2i-1}{n^2}
\end{align*}

We now compute the expectation using these probabilities:
\begin{align*}
\expect{\max(X, Y)}
        & = \sum_{i=i}^{n} i \cdot \Pr(\max(X,Y) = i) 
          = \sum_{i=i}^{n} i \cdot \frac{2i-1}{n^2} \\
        & = \frac{1}{n^2} \cdot \sum_{i=1}^{n} (2i^2 - i) 
          = \frac{1}{n^2} \cdot \left(
                2 \cdot \frac{n(2n+1)(n+1)}{6} - \frac{n(n+1)}{2}
                \right) \\
        & = \frac{(n+1)(4n-1)}{6n}
\end{align*}

Alternatively, we could also compute it as follows:
\begin{align*}
\expect{\max(X,Y)}
        & = \sum_{i=0}^{\infty} \Pr(\max(X,Y) > i) 
          = \sum_{i=0}^{n-1} \left(1 - \Pr(\max(X,Y) \leq i)\right) \\
        & = n - \sum_{i=0}^{n-1} \Pr(X \leq i \land Y \leq i) 
          = n - \sum_{i=0}^{n-1} \Pr(X \leq i) \Pr(Y \leq i) \\
        & = n - \sum_{i=0}^{n-1} \left(\frac{i}{n}\right)^2 
          = n - \frac{1}{n^2} \cdot \frac{n(n-1)(2n-1)}{6} \\
        & = \frac{(n+1)(4n-1)}{6n}
\end{align*}
}



\end{problemparts}






%%%%
%%%%
%%%% PROBLEM 1
%%%%
%%%%

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

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

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



\eparts
\fi



\end{problems}
\end{document}
