\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%nikos
%PSET11 - last used Spring 99, pset 11
%LEARNING OUTCOMES:7 (calculate numbers of possible outcomes)
%                  8  (calculate probabilities)
%New problem added this term
\problem The faculty holds a dinner party for $n \geq 2$ couples.  The
hostess chooses a seating arrangement for the $2n$ people around a
circular table uniformly at random. What is the expected number of
couples such that the husband and wife are sitting next to each other?

\solnospace{
Let $I_k$ be an indicator variable for the event that couple
$k$ is sitting together.  Then the number of couples sitting together
is $I_1 + I_2 + \ldots + I_n$.  The probability that a couple is
seated together is $2 / (2n-1)$, since a wife is equally likely to
occupy each of the $2n-1$ positions relative to her husband and there
are 2 positions right next to him.  Consequently, $\Pr(I_k = 1) = 2 /
(2n-1)$, and we can reason as follows:

\begin{eqnarray*}
\Ex(\text{couples sitting together})
	& = &	\Ex\left(\sum_{k=1}^n I_k\right) \\
	& = &	\sum_{k=1}^n \Ex(I_k) \\
	& = &	\sum_{k=1}^n \Pr(I_k = 1) \\
	& = &	\sum_{k=1}^n \frac{2}{2n-1} \\
	& = &	\frac{2n}{2n-1}
\end{eqnarray*}
%Thus, regardless of the size of the party, the expected number of
%couples seated together is always close to 1.
Thus, as $n$ increases, the expected number of couples seated together converges to 1.
}


%nikos
%PSET11 - last used Spring 99, pset 11
%LEARNING OUTCOMES:7 (calculate numbers of possible outcomes)
%                  8  (calculate probabilities)
%New problem added this term

\problem Each bag of Doritos contains a cool sticker. There are $n$
different types of stickers and if I collect at least one sticker of
each type I will win a big screen TV. Assume that all sticker types
are equally likely and stickers are placed in bags independently.

\bparts \ppart Suppose that I have already collected $k$ types of
stickers.  What is the expected number of additional bags of Doritos
that I must eat to collect one additional type of sticker?

\solnospace{
The probability that I must eat $i$ or more bags is:
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get new type}}}\\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of bags to get new type} > i} \\
        & = &   \sum_{i=0}^{\infty} \prob{\text{number of old types in first $i$ bags}} \\
        & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
        & = &   \frac{n}{n-k}
\end{eqnarray*}
}

\ppart What is the expected number of bags of Doritos that I
must eat to collect at least one sticker of each type?

\solution{We sum the expected number of bags to get the first type,
the expected number to get the second type, and so forth.
\begin{eqnarray*}
\lefteqn{\expect{\text{number of bags to get all types}}}\\
        & = &   \sum_{k=0}^{n-1} \frac{n}{n-k} \ = \   n \cdot
        \sum_{k=0}^{n-1} \frac{1}{n-k} \\
        & = &  n \cdot \sum_{j=1}^{n} \frac{1}{j} 
        \ = \   n H_n.
\end{eqnarray*}
}

\eparts


%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 10    *
%**************


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

\problem {\bf (5 points)} Suppose that I roll a 4-sided die, a 6-sided
die, an 8-sided die, a 10-sided die, a 12-sided die, and a 20-sided
die.  What is the expected number of 6's that come up?  (Assume that
all of the dice are fair.)

\solution{
\begin{eqnarray*}
\Ex(\text{6's on all dice})
        & = &   \Ex(\text{6's on 4-sided die}) + \Ex(\text{6's on 6-sided die}) + \ldots \\
        &   &   \mbox{} \quad + \Ex(\text{6's on 20-sided die}) \\
        & = &   \frac{0}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{10} +
        \frac{1}{12} + \frac{1}{20} \\
        & = &   \frac{21}{40}
\end{eqnarray*}

The first step uses linearity of expectation, and the second step is
simplification.  }

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

\problem {\bf (10 points)} Suppose that I roll $n$ dice that are
6-sided, fair, and mutually independent.  What is the expected value
of the largest number that comes up?

\solution{Let the random variable $M$ be the largest number that comes
up.  We will use the identity

\begin{eqnarray*}
\Ex(M)  & = &   \sum_{i=0}^{\infty} \Pr(M > i)
\end{eqnarray*}

We must compute the probability of the event $M > i$; that is, the
event that some die shows a value greater than $i$.

\begin{eqnarray*}
\Ex(M > i)
        & = &   \sum_{i=0}^5 \Pr(M > i) \\
        & = &   \sum_{i=0}^5 1 - \Pr(\text{every die $\leq i$}) \\
        & = &   \sum_{i=0}^5 1 - (\Pr(\text{one die $\leq i$}))^n \\
        & = &   \sum_{i=0}^5 1 - \left(\frac{i}{6}\right)^n \\
        & = &   6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}
\end{eqnarray*}
}

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

\problem {\bf (10 points)} Suppose that I choose a listing of the
numbers $1, 2, \ldots, n$ uniformly at random.  What is the expected
number of entries that are greater than all preceding entries?  For
example, in the listing 4, 2, 1, 5, 3, the numbers 4 and 5 are greater
than all preceding entries.

\solution{
Let $i_k$ be an indicator for the event that the $k$-th entry is
greater than the preceding $k-1$ entries.  By linearity of expectation

\begin{eqnarray*}
\Ex(\text{\# new maxima})
        & = &   \sum_{k=1}^n \Ex(i_k) \\
        & = &   \sum_{k=1}^n 1 \cdot \Pr(i_k = 1) + 0 \cdot \Pr(i_k = 0) \\
        & = &   \sum_{k=1}^n \Pr(i_k = 1)
\end{eqnarray*}

All that remains is to compute $\Pr(i_k = 1)$, which is the
probability that the $k$-th entry is greater than all preceding
entries.  Note that each of the first $k$ entries is equally likely to
be the largest.  Therefore, $\Pr(i_k = 1) = \frac{1}{k}$.
Substituting into the equation above gives:

\begin{eqnarray*}
\Ex(\text{\# new maxima})
        & = &   \sum_{k=1}^n \Pr(i_k = 1) \\
        & = &   \sum_{k=1}^n \frac{1}{k} \\
        & = &   H_n
\end{eqnarray*}
}

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

\problem {\bf (10 points)} Biologists are inexplicably obsessed with
{\em genetic strings}, which consist of the characters $A$, $C$, $T$,
and $G$.  A biology student once observed that the sequence $AAA$
occurs more often in a random genetic string than, say, $CTG$.

His reasoning is that once $AAA$ has appeared, there is a
$\frac{1}{4}$ chance that the next symbol will be an $A$.  If this
happens, then the sequence $AAA$ has appeared a second time, offset
one character to the right of the first occurrence.  By contrast, once
$CTG$ has appeared, the next appearance of $CTG$ must be offset at
least three characters to the right of the first occurrence.
Furthermore, the probability that a second $CTG$ appears immediately
to the right of the first is a miniscule $\frac{1}{4^3} =
\frac{1}{64}$.

\begin{problemparts}
\problempart Compute the expected number of occurrences of $AAA$ and of
$CTG$ in a genetic string of length 4 chosen uniformly at random.

\solution{We have a uniform sample space containing the $4^4 = 256$
possible length-4 genetic strings.  Let the random variable $X$ equal
the number of occurrences of $AAA$, and let the random variable $Y$
equal the number of occurrences of $CTG$.

\begin{eqnarray*}
\Ex(X)  & = &   \sum_{x\in\mathbb{N}} x \cdot \Pr(X = x) \\
        & = &   0 \cdot \frac{249}{256} + 1 \cdot \frac{6}{256} +
                        2 \cdot \frac{1}{256} \\
        & = &   \frac{1}{32}
\end{eqnarray*}

The six outcomes with $X = 1$ are $CAAA$, $TAAA$, $GAAA$, $AAAC$,
$AAAT$, and $AAAG$.  The single outcome with $X = 2$ is $AAAA$.

\begin{eqnarray*}
\Ex(Y)  & = &   \sum_{y\in\mathbb{N}} y \cdot \Pr(Y = y) \\
        & = &   0 \cdot \frac{248}{256} + 8 \cdot \frac{1}{256} \\
        & = &   \frac{1}{32}
\end{eqnarray*}

The eight outcomes with $Y = 1$ are $ACTG$, $CCTG$, $TCTG$, $GCTG$,
$CTGA$, $CTGC$, $CTGT$, and $CTGG$.
}

\problempart Compute the expected number of occurrences of $AAA$ and of
$CTG$ in a genetic string of length $n$ chosen uniformly at random.

\solution{There are $n-2$ sequences of three consecutive characters in
a genetic string of length $n$.  Each sequence is $AAA$ with
probability $\frac{1}{64}$.  The expected number of occurrences of
$AAA$ in three consecutive positions is therefore $\frac{1}{64}$.  By
linearity of expectation, the expected number of occurrences of $AAA$
in a genetic string of length $n$ is $\frac{n-2}{64}$.  Precisely the
same calculation is valid for the sequence $CTG$, and so the answer is
the same.}

\end{problemparts}

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

\problem {\bf (20 points)} Suppose that $R$ is a random variable.  Let
$E$ be an event.  The {\em conditional expectation} of $R$ given that
event $E$ occurs is denoted $\Ex(R \mid E)$ and is defined to be

\begin{eqnarray*}
\Ex(R \mid E)   & = &   \sum_{x \in \text{range}(R)} x \cdot \Pr(R = x \mid E).
\end{eqnarray*}

\begin{problemparts}

\problempart Compute the expected value of the number rolled on a
fair, 6-sided die, given that the outcome is even.

\solution{Let the random variable $R$ be the number rolled, and let
$E$ be the event that the number rolled is even.

\begin{eqnarray*}
\Ex(R \mid E)   & = &   \sum_{x=1}^{6} x \cdot \Pr(R = x \mid E) \\
                & = &   1 \cdot 0 + 2 \cdot \frac{1}{3} + 
                        3 \cdot 0 + 4 \cdot \frac{1}{3} + 
                        5 \cdot 0 + 6 \cdot \frac{1}{3} \\
                & = &   4
\end{eqnarray*}
}

\problempart Compute the expected value of the number rolled on a
fair, 6-sided die, given that the outcome is odd.

\solution{Define $R$ and $E$ as before.

\begin{eqnarray*}
\Ex(R \mid \overline{E})
        & = &   \sum_{x=1}^{6} x \cdot \Pr(R = x \mid \overline{E}) \\
        & = &   1 \cdot \frac{1}{3} + 2 \cdot 0 + 
                3 \cdot \frac{1}{3} + 4 \cdot 0 + 
                5 \cdot \frac{1}{3} + 6 \cdot 0 \\
        & = &   3
\end{eqnarray*}
}

\problempart Prove the following identity, assuming that all
expectations exist.

\begin{eqnarray*}
\Ex(R)  & = &   \Pr(E) \cdot \Ex(R \mid E) +
                        \Pr(\overline{E}) \cdot \Ex(R \mid \overline{E})
\end{eqnarray*}

\solution{We transform the right side into the left side.  All
summations are over $x \in \text{Range}(R)$.

\begin{eqnarray*}
\lefteqn{\Pr(E) \cdot \Ex(R \mid E) +
        \Pr(\overline{E}) \cdot \Ex(R \mid \overline{E})} \\
        & = &   \Pr(E) \cdot \left( \sum_{x}
                        x \cdot \Pr(R = x \mid E) \right)
                + \Pr(\overline{E}) \cdot  \left( \sum_{x}
                        x \cdot \Pr(R = x \mid \overline{E}) \right) \\
        & = &   \Pr(E) \cdot \left( \sum_{x}
                        x \cdot \frac{\Pr(R = x \cap E)}{\Pr(E)} \right)
                + \Pr(\overline{E}) \cdot  \left( \sum_{x}
                        x \cdot \frac{\Pr(R = x \cap \overline{E})}
                        {\Pr(\overline{E})} \right) \\
        & = &   \sum_{x} x \cdot \left(
                        \Pr(R = x \cap E) + \Pr(R = x \cap \overline{E})
                        \right) \\
        & = &   \sum_{x} x \cdot \left(
                        \Pr((R = x \cap E) \cup (R = x \cap \overline{E}))
                        \right) \\
        & = &   \sum_{x} x \cdot \Pr(R = x) \\
        & = &   \Ex(R)
\end{eqnarray*}

The first step uses the definition of conditional expectation.  The
second step uses the definition of conditional probability.  The third
step is simplification.  The fourth step uses the fact that the
probability of a disjoint union of events is equal to the sum of the
event probabilities.  The fifth step is simplification, and the final
step uses the definition of expected value.}

\problempart Compute the expected value of the product of the numbers
rolled on two dice that are 6-sided, fair, and independent, given that
the numbers rolled are distinct.

\solution{Let the random variable $R$ be the product of the two dice,
and let $E$ be the event that the two numbers rolled are {\em equal}.
The following three quantities are easy to compute:

\begin{eqnarray*}
\Ex(R)  & = &   \Ex(\text{Die 1}) \cdot \Ex(\text{Die 2}) \\
        & = &   \frac{7}{2} \cdot \frac{7}{2} \\
        & = &   \frac{49}{4} \\
\Pr(E)  & = &   \frac{6}{36} \\
        & = &   \frac{1}{6} \\
\Ex(R \mid E)
        & = &   \sum_{x \in \mathbb{N}} x \cdot \Pr(R = x \mid E) \\
        & = &   1^2 \cdot \frac{1}{6} + 2^2 \cdot \frac{1}{6} +
                3^2 \cdot \frac{1}{6} + 4^2 \cdot \frac{1}{6} +
                5^2 \cdot \frac{1}{6} + 6^2 \cdot \frac{1}{6} \\
        & = &   \frac{91}{6}
\end{eqnarray*}

We want to compute $\Ex(R \mid \overline{E})$, the expected value of
the product of the two rolls, given that they are distinct.  From the
identity in part(c), we have:

\begin{eqnarray*}
\Ex(R \mid \overline{E})
        & = &   \frac{\Ex(R) - \Pr(E) \cdot \Ex(R \mid E)}{\Pr(\overline{E})} \\
        & = &   \frac{\frac{49}{4} - \frac{1}{6} \cdot \frac{91}{6}}
                        {\frac{5}{6}} \\
        & = &   \frac{35}{3}
\end{eqnarray*}
}

\end{problemparts}

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

\problem {\bf (10 points)} Suppose that I start throwing balls uniformly
and mutually independently at random into $n$ bins.

\begin{problemparts}

\problempart Suppose that at some stage, exactly $k$ of the bins
contain at least one ball.  Now I throw additional balls until exactly
$k+1$ of the bins contain at least one ball.  What is the expected
number of additional balls that I throw?

\solution{Let the random variable $A_k$ equal the number of additional
balls that I throw.  The expected value of $A_k$ can be computed as follows.

\begin{eqnarray*}
\Ex(A_k)
        & = & \sum_{i=0}^{\infty} \Pr(A_k > i) \\
        & = & \sum_{i=0}^{\infty} \left(\frac{k}{n}\right)^i \\
        & = & \frac{1}{1 - \frac{k}{n}} \\ & = & \frac{n}{n-k}
\end{eqnarray*}

The first equation holds because $B$ is a random variable taking on
non-negative integer values.  In the second step, more than $i$ balls
are required if the first $i$ balls all fall into the $k$ non-empty
bins; this happens with probabilty $(\frac{k}{n})^i$.  The formula for
the sum of an infinite geometric series is used in the third step.  The final
step is simplification.
}

\problempart Suppose that the bins start out empty, and I throw balls
until every bin has at least one ball.  What is the expected number of
balls that I throw?

\solution{Let the random variable $B$ equal the number of balls that I
must throw to put at least one ball in every bin.  The number of balls
required is the number of balls required to fill one bin plus the
number of balls required to fill a second bin and so forth.  That is,
$B = A_0 + A_1 + \ldots + A_{n-1}$.  We can compute the expected value
of $B$ as follows.

\begin{eqnarray*}
\Ex(B)  & = &   \Ex(A_0 + A_1 + \ldots + A_{n-1}) \\
        & = &   \Ex(A_0) + \Ex(A_1) + \ldots + \Ex(A_{n-1}) \\
        & = &   \frac{n}{n-0} + \frac{n}{n-1} + \ldots + \frac{n}{1} \\
        & = &   n \cdot \left(\frac{1}{n} + \frac{1}{n-1} + \ldots + \frac{1}{1} \right) \\
        & = &   n H_n
\end{eqnarray*}

The first step follows by taking expectations on both sides of the
equation $B = A_0 + A_1 + \ldots + A_{n-1}$.  The second step uses
linearity of expectation, and the third uses the result of part (a).
The remaining steps are simplifications.}

\end{problemparts}

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

\problem {\bf (15 points)} Let $R$ be a random variable taking on
non-negative integer values.  Let $r$ be the probability generating
function for $R$; that is, define

\begin{eqnarray*}
r(x)    & = &   \Pr(R = 0) + \Pr(R = 1) \cdot x + \Pr(R = 2) \cdot x^2 +
                \Pr(R = 3) \cdot x^3 + \ldots.
\end{eqnarray*}

\begin{problemparts}

\problempart Write an expression involving $r$ that is equal to the expected value of $R$.

\solution{
\begin{eqnarray*}
r'(x)   & = &   1 \cdot \Pr(R = 1) + 2 \cdot \Pr(R = 2) \cdot x +
                3 \cdot \Pr(R = 3) \cdot x^2 + \ldots \\
r'(1)   & = &   1 \cdot \Pr(R = 1) + 2 \cdot \Pr(R = 2) +
                3 \cdot \Pr(R = 3) + \ldots \\
        & = &   \Ex(R)
\end{eqnarray*}
}

\problempart Suppose that $\Pr(R = k) = \frac{2}{3^{k+1}}$ for
all $k \geq 0$.  Find a closed-form expression for $r$, the
probability generating function for $R$.

\solution{
\begin{eqnarray*}
r(x)    & = &   \frac{2}{3^1} +
                \frac{2}{3^2} \cdot x +
                \frac{2}{3^3} \cdot x^2 +
                \frac{2}{3^3} \cdot x^3 +
                \ldots \\
        & = &   \frac{\frac{2}{3}}{1 - \frac{x}{3}} \\
        & = &   \frac{2}{3 - x}
\end{eqnarray*}

The first equation follows from the definition of the probability
generating function $r$.  The second equation uses the formula for the
sum of an infinite geometric series, and the third equation is
obtained by simplification.
}

\problempart Using your solution to part (a), determine the expected value
of the random variable $R$ as defined in part (b).

\solution{
\begin{eqnarray*}
r'(x)   & = &   \frac{2}{(3 - x)^2} \\
r'(1)   & = &   \frac{2}{(3 - 1)^2} \\
        & = &   \frac{1}{2}
\end{eqnarray*}
} 
\end{problemparts}

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

\problem {\bf (10 points)} 6.042 TA Eric Lehman has offered to play a
``fun game'' with Theory Pig, who rarely comes out of his drawer
anymore after all the abuse that he has suffered this term.

Here are the rules.  Eric flips a coin until he gets a heads.  Let $n$
be the number of tails preceding the first heads.  For example, if he
flips $TTTH$, then $n = 3$, and if he flips just $H$, then $n = 0$.
Now Eric offers to pat Theory Pig on each of the next $3^n$ days.  If
Theory Pig declines the offer, then Eric repeats the coin-tossing
experiment and instead pats Theory Pig on each of next $3^m$ days where
$m$ is the number of tails before the first heads in the second trial.

As usual, this game sounds great, but Theory Pig is understandably
nervous.  He wants to determine his best strategy.

\begin{problemparts}
\problempart As a warmup, consider the following simpler variant of
the game.  Suppose that Eric rolls a fair, 6-sided die.  He offers to
pat Theory Pig for the number of days indicated on the die.  If Theory
Pig rejects the offer, then Eric rolls again and pats Theory Pig for
the number of days shown on the second roll.  What is expected number
of patting-days, if Theory Pig uses an optimal strategy?

\solution{If Theory Pig always declines the initial offer, then his
expected payoff is $\frac{7}{2}$, the expected roll on a fair, 6-sided
die.  Let $p_k$ be the probability that Theory Pig accepts the initial
offer, given that $k$ is rolled.  Then Theory Pig's expected payoff is

\begin{eqnarray*}
\Ex(\text{patting days})
        & = & \sum_{i=1}^6 \frac{1}{6} (p_i \cdot i +
                (1 - p_i) \cdot \frac{7}{2}).
\end{eqnarray*}

This sum is maximized by maximizing each term.  Consequently, we
should choose $p_1 = p_2 = p3 = 0$ and $p_4 = p_5 = p_6 = 1$.  That
is, Theory Pig should decline an offer of 3 or less and accept an
offer of 4 or more.  In this case, his expected payoff is
$\frac{17}{4}$.}

\problempart Now return to the original coin-flipping game.  Describe
a strategy that maximizes the expected number of patting days.

\bigskip

{\em WARNING: If less than 80\% of the class solves this problem part
correctly, then Eric will withdraw his offer to play the game, and THE
PIG GETS NOTHING!}

\solution{If Theory Pig declines the initial offer, then his expected
payoff is

\begin{eqnarray*}
\Ex(\text{patting days if decline})
        & = & \sum_{i=0}^\infty \frac{1}{2^{i+1}} \cdot 3^i.
\end{eqnarray*}

This summation is infinite.  Therefore, if there is a positive
probability that Theory Pig decines the initial offer, his expected
payoff is infinite.  On the other hand, suppose that there is zero
probability that Theory Pig declines the initial offer; that is, he
always accepts.  Then his expected payoff is

\begin{eqnarray*}
\Ex(\text{patting days if accept})
        & = & \sum_{i=0}^\infty \frac{1}{2^{i+1}} \cdot 3^i.
\end{eqnarray*}

This is the same infinite sum.  Therefore, every strategy is optimal
and gives an infinite expected number of patting days.

We are still tallying up the precentage of students that solved this
problem correctly.
}
\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps10
% ( expectation, substrings)

Suppose a length $n$ string of 0's and 1's is chosen uniformly
randomly (e.g., by $n$ independent tosses of fair coin)
and then wrapped around to form a circle.

\begin{problemparts}
\problempart
What is the maximum number of occurrences of the string
$0^k$ ($k$ 0's) in this circle?
What is the expected number of occurrences of $0^k$?
(Note: A string of $k+1$ 0's counts as \emph{two} strings of length
$k$ -- starting in the first position of the string and starting in
the second position. Also remember that there is no particular start
or end of the circle.)

\solution{
The maximum number of $0^k$ substrings is $n$ -- in a string of all 0's,
a new such substring occurs at every position.
The expected number can be found by simply adding up probabilities of 
the separate
events that the string occurs starting at position $i$, which should be
$\frac{n}{2^k}$. While the events are not independent, we are
`overcounting' in exactly the correct way. This concept is referred to,
of course, as \emph{linearity of expectation}.

To be more rigorous, define random variables $X_i$ for $i = 1, 2, \ldots n$,
where $X_i = 1$ if a string of $k$ 0's starts at position $i$ and 0 if it 
does not. Then, we are looking for $E[X_1+X_2+\ldots+X_n]$, which by linearity
of expectation must be $E[X_1] + E[X_2] + \ldots + E[X_n]$. 

This can be envisioned as
a counting problem instead. There are $2^n$ possible strings. Each
position will begin a substring of $0^k$ for $2^{n-k}$ different
strings. Thus, the total number of such substrings divided by the
number of possible strings is $\frac{n2^{n-k}}{2^n}$, which simplifies
to $\frac{n}{2^k}$.
}

\problempart
Suppose $k$ is even.
What is the expected number of occurrences of
$0^{\frac{k}{2}}1^{\frac{k}{2}}$ (total length $k$)?

\solution{
This is the same as in the previous part, since the reasoning
does not change (perhaps surprisingly).
}

\problempart
Now fix $n = 8$, $k = 4$.
Is the probability that $0000$ appears in the circle equal to the
probability that $0011$ appears?

\solution{

%This can be done with inclusion-exclusion, with much pain.
%Else, it can be done with more ad-hoc methods. For instance, the
%$0011$ substrings may not overlap at all. There may only be $4$ at most
%in a particular string. However, there are $8$ substrings of $0000$ in
%the all-zero string. Since the expectations are the same, this implies
%that there are less strings with substring $0000$, but with a greater
%average number of occurrences for those that have it.

This can be reasoned out by counting the strings in each case. 

For 
$0000$, there is one string that contains 8 copies, $00000000$.
The rest of the strings containing $0000$ can be ordered by the number
of copies of $0000$ that they contain; each one can also have the long
string of 0's begin at any of the 8 positions:
\[
\begin{array}{rcr}
 \text{1 string}   & 00000000 & \text{(8 copies)} \\
 \text{8 strings}  & 00000001 & \text{(4 copies)} \\
 \text{8 strings}  & 00000011 & \text{(3 copies)} \\
 \text{16 strings} & 000001x1 & \text{(2 copies)} \\
 \text{32 strings} & 00001xx1 & \text{(1 copy)} \\
\end{array}
\]
Thus, in total, 65 of the 256 possible strings contain a copy of $0000$. 
(Note that there are 128 copies in total; this agrees with the expectation
of $\frac{n}{2^k}$ multiplied by the number of possible strings, $2^n$).
So the probability of a random string containing a copy of $0000$ is
\[
\frac{65}{256}
\]

%(We could have done the problem with inclusion-exclusion.
%We then get, for each digit:
%\[
%\begin{array}{rrcr}
%8 copies: &  1 string  & 00000000 & (i, i+1, i+2, i+3, i+4, i+5, i+6, i+7) \\
%4 copies: &  2 strings & 0000000X & (i, i+1, i+2, i+3)   \\
%          &  1 string  & 00000000 & (any other combo)   \\
%3 copies: &  4 strings & 000000XX & (i, i+1, i+2) \\
%          &  2 strings & 0000000X & (i, i+1, i+3), (i, i+2, i+3) \\
%          &  1 string  & 00000000 & (i, i+1, i+3), (i, i+2, i+3) \\
%2 copies: & 64 strings & 00000XXX & (2 copies or more) \\
%1 copies: &128 strings & 0000XXXX & (1 copy or more) \\
%% sorry, this is a disaster!
%\end{array}
%\]
%Then, we have the total number of such strings as $ = $ 

For 
$0011$, we get the following:
\[
\begin{array}{rcr}
  \text{4 strings} & 00110011 & \text{(2 copies)} \\
\text{120 strings} & 0011xxxx & \text{(1 copy)} \\
\end{array}
\]
The number of strings with one copy is a bit complex; the $0011$ sequence
can start in any of $8$ places, and the other four characters can be 
any of the $16$ possibilities except $0011$.
Altogether, 124 of the 256 possible strings contain a copy of $0000$. 
(Note that there are again 128 copies in total).
The probability of a random string containing a copy of $0011$ is
\[
\frac{124}{256}
\]


Thus, the probability is not the same; it is significantly more likely
that a substring of $0011$ will appear.
}

\problempart
Justify your answer for the previous part. If your answers in the previous
parts seem to be ``contradictory'',
explain.

\solution{
Although the expectations are the same, the extra overlapping
possibilities for 0000 make the conditional probability
of a second occurrence, conditioned on a first occurrence, higher than
it is for 0011. Since it is more likely that there will be a second
occurrence, the expectation must be composed of less situations in which
the target string occurs at all.
}

\end{problemparts}

\problem %source: spring00 ps10
%[[[Something with MTTF?]]]

Every day in Boston, a rainstorm occurs with probability 1/3 (independently
of any other day).
Each day it rains, the radar system at the Nashua airport breaks with
probability 1/25. The system never breaks on fair days.

\begin{problemparts}
\problempart
Assuming that the radar was working yesterday (but may break today, if it
happens to rain),
how many days can we expect the Nashua radar system to work correctly
before it next breaks?

\solution{
This can be done with a simple recurrence:
\begin{eqnarray*}
w  & =  & \frac{2}{3}(1+w)+\frac{1}{3}(\frac{24}{25}(1+w))  \\
w  & =  & \frac{2}{3}+\frac{2}{3}w+\frac{8}{25}+\frac{8}{25}w  \\
\frac{1}{75}w & = & \frac{74}{75} \\
w & = & 74
\end{eqnarray*}
Notice that in this case, we could have tried to predict the expected time
the system will work as simply $\frac{1}{p}$, where $p$ is the probability
of failure on any given day, because it never
breaks on non-rainy days. However, this would technically be off by $1$,
since it counts the day that the system breaks as well.
}

\problempart
\emph{Optional question:}
Suppose that the first time the radar system breaks (on a rainy day
with probability 1/25), it is only patched-up with a quick hack to
keep it working. (As a computer science student, you should be able
to relate to this). After being patched-up, it will fail on future
rainy days with probability 1/10, after which the system will need
major repairs.
Calculate the expected number of days until the radar system needs
\emph{major} repairs.
\solution{
\begin{eqnarray*}
w  & =  & \frac{2}{3}(1+w)+\frac{1}{3}(\frac{24}{25}(1+w)+ \frac{1}{25}(1+v))  \\
v  & =  & \frac{2}{3}(1+v)+\frac{1}{3}(\frac{9}{10}(1+v))  \\
v  & =  & \frac{2}{3}+\frac{2}{3}v+\frac{3}{10}+\frac{3}{10}v  \\
\frac{1}{30}v & = & \frac{29}{30} \\
v & = & 29  \\
w  & =  & \frac{2}{3}(1+w)+\frac{1}{3}(\frac{24}{25}(1+w)+ \frac{1}{25}(30))  \\
w  & =  & \frac{2}{3}+\frac{2}{3}w+\frac{8}{25}+\frac{8}{25}w + \frac{30}{75}  \\
\frac{1}{75}w & = & \frac{104}{75} \\
w & = & 104
\end{eqnarray*}
Although you could have also seen these as independent events that occur 
sequentially. The first breakage is expected on day $1/\frac{1}{75}$, and the 
second is expected on day $1/\frac{1}{30}$. Thus, we expect their sum to be
$75+30 = 105$, by linearity of expectation. Depending on how you interpret the
day on which it needs the repairs, this gives either 104 or 105 days.
}

\end{problemparts}

%END   Joe's problems

%BEGIN Ray's problems


%%%%%%%%%%%%%%%%%%%% S99 ps11

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

\problem {\bf (10 points)} Compute the expected value for each of the
following random variables.  (Assume that all dice are fair and
six-sided and that dice rolls are mutually independent.)

\begin{problemparts}
\problempart The sum of the rolls of three dice.

\solution{
The expected value of one die roll is
\begin{eqnarray*}
1 \cdot \frac{1}{6} +
2 \cdot \frac{1}{6} +
3 \cdot \frac{1}{6} +
4 \cdot \frac{1}{6} +
5 \cdot \frac{1}{6} +
6 \cdot \frac{1}{6}
        & = & \frac{7}{2}.
\end{eqnarray*}

By linearity of expectation, the sum three rolls is
\begin{eqnarray*}
\frac{7}{2} + \frac{7}{2} + \frac{7}{2} & = & \frac{21}{2}.
\end{eqnarray*}
}

\problempart The product of the rolls of three dice.

\solution{For independent random variables, the expectation of the
product is the product of the expectations.  Therefore, the expected
product is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} \cdot \frac{7}{2} & = & \frac{343}{8}.
\end{eqnarray*}
}

\problempart The sum of the rolls of a number of dice that is given by
the roll of a single die.  (For example, if you roll a 3 on the single
die, then you take the sum of 3 dice rolls; if you roll a 5 on the
single die, then you take the sum of 5 dice rolls.)

\solution{By Wald's Theorem, the answer is the expected number of dice
rolled multiplied by the expected roll of one die, which is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} & = & \frac{49}{4}.
\end{eqnarray*}
}

\problempart Suppose now that the dice rolls are not guaranteed to be
mutually independent.  Which of your answers above must still be
correct?

\solution{The first answer remains valid because linearity of
expectation does not require independence.  Neither of the remaining
answers is necessarily correct, however; both make use of
independence.}
\end{problemparts}

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

\problem {\bf (15 points)} Compute your expected payoff for the
following two games.

\begin{problemparts}
\problempart You roll two fair, independent, six-sided dice.  If the sum
is one of the five values 5, 6, 7, 8 or 9, then you pay me $\$1$.  If
the sum is one of the six values 2, 3, 4, 10, 11, or 12, then I pay
you $\$1$.

\solution{
\begin{eqnarray*}
\lefteqn{\expect{\text{payoff in dollars}}}\\
        & = &   -1 \cdot (\frac{4}{36} + \frac{5}{36} + \frac{6}{36} + 
                                \frac{5}{36} + \frac{4}{36} ) + 
                1 \cdot (\frac{1}{36} + \frac{2}{36} + \frac{3}{36} + 
                        \frac{3}{36} + \frac{2}{36} + \frac{1}{36}) \\
        & = &   -1/3.
\end{eqnarray*}
So you expect to lose 33 1/3 cents on each roll.}

\problempart You flip a fair coin until you get a head.  For each tail
that you flipped, you are allowed to roll a fair, six-sided die.  I
pay you a number of dollars equal to the sum of all your dice rolls.
The catch is that I charge you 3 dollars initially just to play this
game.  (Assume that all coin flips and dice rolls are mutually
independent.)

\solution{The expected number of tails is 1.  The expected outcome of a
die roll is $3 1/2$.  Therefore, by Wald's Theorem, the expected dollar
payoff is $1 \cdot 3 1/2 - 3 = 1/2$, namely 50 cents.}
\end{problemparts}

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

\problem {\bf (10 points)} There is a dinner party for $n \geq 2$
couples.  The hostess chooses a seating arrangement for the $2n$
people around a circular table uniformly at random.  What is the
expected number of couples such that the husband and wife are sitting
next to each other?

\solution{Let $I_k$ be an indicator variable for the event that couple
$k$ is sitting together.  Then the number of couples sitting together
is $I_1 + I_2 + \ldots + I_n$.  The probability that a couple is
seated together is $2 / (2n-1)$, since a wife is equally likely to
occupy each of the $2n-1$ positions relative to her husband and there
are 2 positions right next to him.  Consequently, $\prob{I_k = 1} = 2 /
(2n-1)$, and we can reason as follows:
\begin{eqnarray*}
\lefteqn{\expect{\text{number of couples sitting together}}}\\
 & = &   \expect{\sum_{k=1}^n I_k} \ = \ \sum_{k=1}^n \expect{I_k} \\
        & = &   \sum_{k=1}^n \prob{I_k = 1} \ = \ \sum_{k=1}^n \frac{2}{2n-1}
         \ = \  \frac{2n}{2n-1}
\end{eqnarray*}

Thus, regardless of the size of the party, the expected number of
couples seated together is always close to 1.}

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

\problem {\bf (10 points)} Suppose that I roll $n$ dice that are
six-sided, fair, and mutually independent.  What is the expected value
of the largest number that comes up?

\solution{Let the random variable $M$ be the largest number that comes
up.  We will use the identity
\begin{eqnarray*}
\expect{M}      & = &   \sum_{i=0}^{\infty} \prob{M > i}.
\end{eqnarray*}

We must compute the probability of the event $M > i$; that is, the
event that some die shows a value greater than $i$.
\begin{eqnarray*}
\expect{M}
        & = &   \sum_{i=0}^5 \prob{M > i} \\
        & = &   \sum_{i=0}^5 1 - \prob{\text{every die $\leq i$}} \\
        & = &   \sum_{i=0}^5 1 - (\prob{\text{one die $\leq i$}})^n \\
        & = &   \sum_{i=0}^5 1 - \left(\frac{i}{6}\right)^n \\
        & = &   6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}
\end{eqnarray*}
}

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

\problem {\bf (10 points)} Stas, Zully, and Jared play the following
game before 6.042 lecture.  Each player puts $\$2$ on the table and
covertly writes down a number in the range 1 to 6.  Then Stas rolls a
fair, six-sided die.  Everyone reveals their hidden numbers, and the
money on the table is divided evenly among the players who correctly
predicted the die roll.  If no player correctly predicted the roll,
then everyone takes their $\$2$ back.

Stas and Jared guess numbers in the range 1 to 6 uniformly and
independently at random.  However, Zully peeks at Jared's guess and
picks a {\em different} number uniformly at random, independent of
Stas's guess.

\begin{problemparts}

\problempart What is each player's expected payoff?

\solution{Jared and Zully's situations are symmetric.  Between them,
they pick a pair of distinct numbers uniformly at random and
independently of Stas.  We compute Stas's expected payoff and derive
Jared and Zully's.
\begin{eqnarray*}
\lefteqn{\expect{\text{Stas's payoff}}} \quad \quad \\
        & = &   4 \cdot \prob{\text{Stas alone is right}} \\
&&\mbox{}       + 1 \cdot \prob{\text{Stas and one other player are right}} \\
&&\mbox{}       + 0 \cdot \prob{\text{All or none of the players are right}} \\
&&\mbox{}       - 2 \cdot \prob{\text{Stas is wrong, another player is right}} \\
        & = &   4 \cdot \frac{1}{6} \cdot \frac{4}{6}
                + 1 \cdot \frac{1}{6} \cdot \frac{2}{6}
                - 2 \cdot \frac{5}{6} \cdot \frac{2}{6} \\
        & = &   - \frac{1}{18} \ \text{dollars}
\end{eqnarray*}

Since the sum of all expected payoffs is zero, and Jared and Zully
have the same expected payoff, their expected payoff must be $1/36$
dollars.}

\problempart Subject to the restriction that Stas's guess remain
independent of Zully and Jared's guesses, is there any guessing
strategy Stas can use to increase his expected payoff?  No proof is
required, but explain your reasoning.

\solution{No.  The calculation above remains valid no matter which
number Stas guesses and even if he employs a randomized guessing
strategy.}

\end{problemparts}

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

\problem {\bf (15 points)} In the board game Monopoly, the number of
squares that a player advances in a single turn is determined by up to
three rolls of dice as follows.

\begin{itemize}
\item Initially, the player rolls two dice, sums the results, and
advances that many squares.

\item If the same number comes up on both dice---this is called
\emph{rolling a double}---then the player rolls the dice a second time,
sums the results, and advances that many additional squares.

\item If the player rolled on double on the second roll, then the player
rolls the dice a third time, sums the results, and advances that many
additional squares.

\item However, if third roll was a double, then the player ``goes to
jail''.  We will treat this as though he had to reset his position to
where he was just before the first roll, so the total number of squares
advanced by the player in this case is zero.
\end{itemize}

What is the expected number of squares that a player advances in a single
turn?  Assume that the dice are fair and six-sided and that rolls are
mutually independent.

\solution{Here is one approach to the problem.

It's convenient to assume the dice are \emph{always} rolled three times,
with the player simply ignoring results of any roll which was preceded by
a non-double roll.

Let the random variable $R_i$ be the sum of the two dice on the $i$th
roll, and let $I_i$ be an indicator for the event that the $i$th roll was
a double.

We can express the random variable $R$, the number of squares advanced by
the player, as follows:
\[
R = R_1 + I_1 R_2 + I_1 I_2 R_3 - I_1 I_2 I_3 (R_1 + R_2 + R_3)
\]

Since the dice rolls are independent, we know that $R_i$'s and $I_j$'s at
different rolls are independent.  We can take expectations of both sides
and reason as follows:
\begin{eqnarray*}
\expect{R}      & = &   \expect{R_1}
                 + \expect{I_1 R_2}
                 + \expect{I_1 I_2 R_3} \\
        & & \mbox{}
                 - \expect{I_1 I_2 I_3 R_1}
                 - \expect{I_1 I_2 I_3 R_2}
                 - \expect{I_1 I_2 I_3 R_3} \\
        & = &   \expect{R_1}
                 + \expect{I_1} \cdot \expect{R_2}
                 + \expect{I_1} \cdot \expect{I_2} \cdot \expect{R_3} \\
&&\mbox{}        - \expect{I_2} \cdot \expect{I_3} \cdot \expect{I_1 R_1} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_3} \cdot \expect{I_2 R_2} \\
&&\mbox{}        - \expect{I_1} \cdot \expect{I_2} \cdot \expect{I_3 R_3}
\end{eqnarray*}

Note that the expectation of $R_i$ is $7$, and the expectation of $I_i$ is
$1/6$.  Finally, note that $\expect{I_i R_i} = 7/6$ by direct calculation.
Substituting into the formula above gives:
\begin{eqnarray*}
\expect{R}      & = &   \frac{595}{72}.
\end{eqnarray*}

}

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

\problem {\bf (15 points)} Suppose that $R$ is a random variable.  Let
$E$ be an event.  The {\em conditional expectation} of $R$ given that
event $E$ occurs is denoted $\expect{R \mid E}$ and is defined to be
\[
\expect{R \mid E}  ::= \sum_{x \in \text{range}(R)} x \cdot \prob{R = x \mid E}.
\]

\begin{problemparts}

\problempart Compute the expected value of the number rolled on a
fair, six-sided die, given that the outcome is even.

\solution{Let the random variable $R$ be the number rolled, and let
$E$ be the event that the number rolled is even.
\begin{eqnarray*}
\expect{R \mid E}       & = &   \sum_{x=1}^{6} x \cdot \prob{R = x \mid E} \\
                & = &   1 \cdot 0 + 2 \cdot \frac{1}{3} + 
                        3 \cdot 0 + 4 \cdot \frac{1}{3} + 
                        5 \cdot 0 + 6 \cdot \frac{1}{3} \\
                & = &   4
\end{eqnarray*}
}

\problempart Compute the expected value of the number rolled on a
fair, six-sided die, given that the outcome is odd.

\solution{Define $R$ and $E$ as before.
\begin{eqnarray*}
\expect{R \mid \overline{E}}
        & = &   \sum_{x=1}^{6} x \cdot \prob{R = x \mid \overline{E}} \\
        & = &   1 \cdot \frac{1}{3} + 2 \cdot 0 + 
                3 \cdot \frac{1}{3} + 4 \cdot 0 + 
                5 \cdot \frac{1}{3} + 6 \cdot 0 \\
        & = &   3
\end{eqnarray*}
}

\problempart Prove the following identity, assuming that all
expectations exist.
\begin{eqnarray*}
\expect{R}      & = &   \prob{E} \cdot \expect{R \mid E} +
                        \prob{\overline{E}} \cdot \expect{R \mid \overline{E}}
\end{eqnarray*}

\solution{We transform the right side into the left side.  All
summations are over $x \in \text{Range}(R)$.
\begin{eqnarray*}
\lefteqn{\prob{E} \cdot \expect{R \mid E} +
        \prob{\overline{E}} \cdot \expect{R \mid \overline{E}}} \\
        & = &   \prob{E} \cdot ( \sum_{x}
                        x \cdot \prob{R = x \mid E} )
                + \prob{\overline{E}} \cdot  ( \sum_{x}
                        x \cdot \prob{R = x \mid \overline{E}} ) \\
        & = &   \prob{E} \cdot ( \sum_{x}
                        x \cdot \frac{\prob{[R = x] \cap E}}{\prob{E}} )
                + \prob{\overline{E}} \cdot  ( \sum_{x}
                        x \cdot \frac{\prob{[R = x] \cap \overline{E}}}
                        {\prob{\overline{E}}} ) \\
        & = &   \sum_{x} x \cdot (
                        \prob{[R = x] \cap E} + \prob{[R = x] \cap \overline{E}}
                        ) \\
        & = &   \sum_{x} x \cdot (
                        \prob{([R = x] \cap E) \cup ([R = x] \cap \overline{E})}
                        ) \\
        & = &   \sum_{x} x \cdot \prob{R = x} \\
        & = &   \expect{R}
\end{eqnarray*}

The first step uses the definition of conditional expectation.  The
second step uses the definition of conditional probability.  The third
step is simplification.  The fourth step uses the fact that the
probability of a disjoint union of events is equal to the sum of the
event probabilities.  The fifth step is simplification, and the final
step uses the definition of expected value.}

\end{problemparts}


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

\problem
Each bag of Doritos contains a cool sticker. There are $n$~different
kinds of sticker, and I want to collect at least one sticker of each
kind. (Assume that sticker kinds in Dorito bags are uniformly random
and mutually independent.)

\begin{problemparts}
\problempart Suppose that I have already collected $k$~kinds of
sticker.  What is the expected number of additional bags of Doritos
that I must eat to collect one additional kind of sticker?

\solution{\ssl We can view this as a mean time to failure problem
  where ``failure'' is the same thing as getting a kind of sticker
  that is not already in the bag. Using the standard approach from the
  lecture notes,
  \begin{eqnarray*}
    \lefteqn{\expect{\text{number of bags to get new kind}}}\\
    & = &   \sum_{i=0}^{\infty} \prob{\text{number of bags to get new kind} > i} \\
    & = &   \sum_{i=0}^{\infty} \prob{\text{only old kinds in first $i$ bags}} \\
    & = &   \sum_{i=0}^{\infty} \left(\frac{k}{n} \right)^i \\
    & = &   \frac{n}{n-k}
\end{eqnarray*}
}

\problempart What is the expected number of bags of Doritos that I
must eat to collect at least one sticker of each kind?

\solution{\ssl We sum the expected number of bags to get the first
  kind, the expected number to get the second kind, and so forth.
  (This is possible because expectation is a linear operator.)
  \begin{eqnarray*}
    \lefteqn{\expect{\text{number of bags to get all kinds}}}\\
    & = &   \sum_{k=0}^{n-1} \frac{n}{n-k} \ = \   n \cdot
    \sum_{k=0}^{n-1} \frac{1}{n-k} \\
    & = &  n \cdot \sum_{j=1}^{n} \frac{1}{j} 
    \ = \   n H_n.
  \end{eqnarray*}
}

\end{problemparts}




%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem4 spring98
\problem{\bf [15 points]}
Chuck-A-Luck is played in many casinos. One version of it is as
follows.  There is a cage with three dice in it.  The player pays
$\$1$ to guess a number between 1 and 6. The three dice are then
rolled. If one die shows the player's number, he wins $\$2$ (i.e., he
wins his old dollar back plus a dollar profit). If two dice show his
number, he wins $\$3$. If three dice show his number, he wins
$\$4$. If no die shows the number, he wins nothing.

If Bobo spends his last dollar on a game of Chuck-A-Luck, what is his
total expected wealth after the game?

\solution{
{\bf Solution}

Let random variable $Y$ be the number of dice showing the chosen number, and
$X$ be his wealth after one play.  Then $X=0$ if $Y=0$ and $X=i+1$, if
$Y=i$, for $i=1,2,3$. 
$P(Y=i) = \displaystyle {3 \choose i} \left( \frac{1}{6} \right)^i
                        \left( \frac{5}{6} \right)^{3-i} $, $i=0,1,2,3$.
Therefore, 
\begin{eqnarray*}
E(X) &=& 0 \cdot P(Y=0) + \sum_{i=1}^{3}(i+1) \cdot P(Y=i) \\
     &=& \sum_{i=1}^{3}(i+1) \cdot {3 \choose i} \left( \frac{1}{6} \right)^i
                        \left( \frac{5}{6} \right)^{3-i} \\
     &=& \frac{1}{216} (2 \cdot 75 + 3 \cdot 15 + 4 \cdot 1) \\
     &=& 199/216 = .921
\end{eqnarray*}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem7 spring98
\problem {\bf [12 points]} An airport bus deposits 8 passengers at 6
stops.  Assume that each passenger is as likely to get off at any stop
as another and that they act independently.  The bus stops only if
someone wants to get off.  What is the probability that nobody gets
off at the third stop?  What is the expected number of stops it will
make?

\solution{
{\bf Solution}

For each individual, the probability he {\em does not} get off at the
third stop is $\frac{5}{6}$.  Therefore, the probability
that no one gets off at the third stop is $(\frac{5}{6})^{8} = 
0.2326$.

Let $I_k$ be an indicator variable for whether the bus stops at the
$k$-th stop.  Then, $X=\sum_k I_k$ is the total number of stops.  By
linearity of expectation,
\[
E(X) = E(I_1) + E(I_2) + E(I_3) + E(I_4) + E(I_5) + E(I_6)
\]

For each $I_k$, the $E(I_k)$ is the probability the bus stops at the
$k$-th stop, or $1-0.2326=0.7674$.  Therefore, $E(X) = 6(0.7674) = 4.6044$.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset10 problem8 spring98 (not used)
\problem Let $S$ be the set of functions from $\{1,\ldots,n\}$ to
$\{1,\ldots,k\}$, and let $\Pr:S\rightarrow [0,1]$ be the uniform
probability distribution on $S$, so that $\Pr(f)=1/|S|$ for all $f\in
S$.

Define the random variable $R\colon S\to \nat$ as $R(f) =
|\mbox{range}(f)|$, that is the random variable $R$ expresses the size
of the range of a function selected uniformly at random from $S$.

Express the expected value of $R$ as a function of $n$ and $k$.

\solution{
{\bf Solution}

Let $I_a$ be the indicator variable for $a$ being in the $\mbox{range}(f)$.
Then, 
\[
R= I_1 + I_2 +\dots +I_k
\]
and
\[
E(R) = E(I_1) + E(I_2) + \dots + E(I_k) = kE(I_1)
\]
by symmetry.

$E(I_1)$ is the probability that $1$ is the $\mbox{range}(f)$.  This
probability is just 1 minus the probabilility that $1$ is {\em not} in
the $\mbox{range}(f)$.

The set of functions that do not have $1$ is the range is $(k-1)^n$.
Since $|S|$ is $k^n$, the probability that 1 is not in the range
is $(1-\frac{1}{k})^n$.  Therefore,
\[
E(R) = k (1- (1-\frac{1}{k})^n)
\]
For large $k$, this is approximately
$k(1- e^{-n/k})$.
}



\iffalse

% new version for fall 2001, see below

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem1 spring98; from fall 97 pset11 problem1
\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?

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

\fi






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem2 spring98; from pset11 problem3 fall97
\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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem4 spring98; from fall 97 pset11 problem5
%\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?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem5 spring98; from fall 97 pset11 problem6
\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
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem6 spring98; from fall 97 pset11 problem7
\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   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem8 spring98; from fall 97 pset11 problem9
\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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem9 spring98; from fall 96 pset12 problem5
\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$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset11 problem13 spring98; from spring 95 pset10 problem4
\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

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000  PS 11   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem Several statements involving probability
are listed below.  Assume that $A$ and $B$ are events, $S$ and $T$ are
random variables, and the underlying sample space is countable.
Furthermore, assume that all expectations exist.  For each statement,
describe restrictions on $A$, $B$, $S$, and $T$ sufficient to ensure
that the statement is true.  Make your restrictions as minimal as you
can.  No proofs are necessary.

\begin{problemparts}
%\begin{enumerate}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B)$
%\item[\textbf{(a)}] $\Pr(A \cup B) = \Pr(A) + \Pr(B)$

\solution{
\textbf{Solution:}\\
This statement is true provided that the event $A \cap B$
has probability zero.}

\problempart $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$
%\item[\textbf{(b)}] $\Pr(A \cup B) = \Pr(A) + \Pr(B) - \Pr(A \cap B)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}

\problempart $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$
%\item[\textbf{(c)}] $\Pr(A \cap B) = \Pr(A) \cdot \Pr(B)$

\solution{
\textbf{Solution:}\\
This statement is true provided that events $A$ and $B$ are independent.
}

\problempart $\Pr(A \cap B) < \Pr(A)$
%\item[\textbf{(d)}] $\Pr(A \cap B) < \Pr(A)$

\solution{
\textbf{Solution:}\\
This statement is true provided $\Pr(A \cap \overline{B}) > 0$.
}

\problempart $\Ex(S + T) = \Ex(S) + \Ex(T)$
%\item[\textbf{(e)}] $\Ex(S + T) = \Ex(S) + \Ex(T)$

\solution{
\textbf{Solution:}\\
This statement is always true.
}

\problempart $\Ex(S \cdot T) = \Ex(S) \cdot \Ex(T)$
%\item[\textbf{(f)}] $\Ex(S \cdot T) = \Ex(S) \cdot \Ex(T)$

\solution{
\textbf{Solution:}\\
This statement is true provided that random variables $S$
and $T$ are independent.}

\end{problemparts}
%\end{enumerate}   
%%%%%%%%%%%%%%  Fall 2000 PS 11    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem Suppose that I roll $n$ dice that are
6-sided, fair, and mutually independent.  What is the expected value
of the largest number among these dice that comes up?

\solution{
\textbf{Solution:}\\
Let the random variable $M$ be the largest number that comes
up.  We will use the identity

\begin{eqnarray*}
\Ex(M)  & = &   \sum_{i=0}^{\infty} \Pr(M > i)
\end{eqnarray*}

We must compute the probability of the event $M > i$; that is, the
event that some die shows a value greater than $i$.

\begin{eqnarray*}
\Ex(M)
    & = &   \sum_{i=0}^5 \Pr(M > i) \\
    & = &   \sum_{i=0}^5 1 - \Pr(\text{every die $\leq i$}) \\
    & = &   \sum_{i=0}^5 1 - (\Pr(\text{one die $\leq i$}))^n \\
    & = &   \sum_{i=0}^5 1 - \left(\frac{i}{6}\right)^n \\
    & = &   6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}
\end{eqnarray*}
}       
%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
 \problem Suppose that I choose a listing of the
numbers $1, 2, \ldots, n$ uniformly at random.  What is the expected
number of entries that are greater than all preceding entries?  For
example, in the listing 4, 2, 1, 5, 3, the numbers 4 and 5 are greater
than all preceding entries.

\solution{
\textbf{Solution:}\\
Let $i_k$ be an indicator for the event that the $k$-th entry is
greater than the preceding $k-1$ entries.  By linearity of expectation

\begin{eqnarray*}
\Ex(\text{\# new maxima})
    & = &   \sum_{k=1}^n \Ex(i_k) \\
    & = &   \sum_{k=1}^n 1 \cdot \Pr(i_k = 1) + 0 \cdot \Pr(i_k = 0) \\
    & = &   \sum_{k=1}^n \Pr(i_k = 1)
\end{eqnarray*}

All that remains is to compute $\Pr(i_k = 1)$, which is the
probability that the $k$-th entry is greater than all preceding
entries.  Note that each of the first $k$ entries is equally likely to
be the largest.  Therefore, $\Pr(i_k = 1) = \frac{1}{k}$.
Substituting into the equation above gives:

\begin{eqnarray*}
\Ex(\text{\# new maxima})
    & = &   \sum_{k=1}^n \Pr(i_k = 1) \\
    & = &   \sum_{k=1}^n \frac{1}{k} \\
    & = &   H_n
\end{eqnarray*}
}

              
%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem There is a dinner party for $n \geq 2$
couples.  The hostess chooses a seating arrangement for the $2n$
people around a circular table uniformly at random.  What is the
expected number of couples such that the husband and wife are sitting
next to each other?

\solution{
\textbf{Solution:}\\
Let $I_k$ be an indicator variable for the event that couple
$k$ is sitting together.  Then the number of couples sitting together
is $I_1 + I_2 + \ldots + I_n$.  The probability that a couple is
seated together is $2 / (2n-1)$, since a wife is equally likely to
occupy each of the $2n-1$ positions relative to her husband and there
are 2 positions right next to him.  Consequently, $\Pr(I_k = 1) = 2 /
(2n-1)$, and we can reason as follows:

\begin{eqnarray*}
\Ex(\text{couples sitting together})
    & = &   \Ex\left(\sum_{k=1}^n I_k\right) \\
    & = &   \sum_{k=1}^n \Ex(I_k) \\
    & = &   \sum_{k=1}^n \Pr(I_k = 1) \\
    & = &   \sum_{k=1}^n \frac{2}{2n-1} \\
    & = &   \frac{2n}{2n-1}
\end{eqnarray*}

Thus, regardless of the size of the party, the expected number of
couples seated together is always close to 1.}
 
%%%%%%%%%%%%%%  Fall 2000 PS 11    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem \textbf{Wald's Theorem.}
% Spring 99 Final. 

Suppose successive digits from zero to nine are generated independently
until the four digit sequence \textbf{9999} appears.

What is the expected number of digits generated? 

\hint Parse the sequence into consecutive ``tries to get 9999'', where a
``try'' is either a single digit other than 9, or a 9 followed by a single
digit other than 9, etc.  For example, the sequence 92349982999769999
parses into eight tries:
\[
/92/3/4/998/2/9997/6/9999/.
\]

\solution{
\textbf{Solution:}
11110.

By Wald's Theorem, the expected number is the mean time to a successful
try, namely $10^4$, times the expected length of a try.  Notice that a try
is of length four iff it begins with three nines, so the probability of a
length four try is $1/10^3$.  That means the expected length of a try is
\[
1 \cdot \frac{9}{10} + 2 \cdot \frac{1}{10}\frac{9}{10} + 3 \cdot
(\frac{1}{10})^2\frac{9}{10} + 4 \cdot (\frac{1}{10})^3
 =  (900 + 180 + 27 + 4)/1000 = 1111/1000
\]
Thus on average, we will have to read 11110 digits in order to see
``9999''.}
           
%%%%%%%%%%%%%% 
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%%%%%%%%%%% FALL 1999 %%%%%%%%%%
%% Problem Set 12
\begin{problems}

\problem Eight men and seven women, all single, happen randomly to have
purchased single seats in the same 15-seat row of a theater.

\bparts

\ppart
What is the probability that the first two seats contain a marriageable
couple, i.e., a single man next to a single woman?

\solution{

Here's one way to do it.  There are $\binom{15}{2} = 105$
possible pairs that could occupy the first two seats, but only $8\cdot7 =
56$ of them are marriageable couples.  So the probability is $56/105 =
8/15$.

}

\ppart What is the expected number of pairs of adjacent seats which
contain marriageable couples?  (For example, if the sequence of men and
women in the seats is
\begin{center}
MMMWMMMMWWWWWWM,
\end{center}
then there are four possible couples sitting in the pairs of adjacent
seats that start at the 3rd, 4th, 7th and 14th seats, respectively.)

\solution{

Let the random variable S be the number of pairs of seats containing a
marriageble couple; we want to find $\expect{S}$.  We can solve this problem
by introducing an indicator random variable $S_i$, where $S_i = 1$ if
there is a marriageable couple in seats $i$ and $i+1$, and $S_i = 0$
otherwise.  So we have $S = \sum_{i=1}^{14} S_i$.

Since each seat is like any other, the probability that seats $i$ and
$i+1$ contain a marriageable couple is the same as in the first
part, $8/15$.  Thus
\[
\expect{S_i} = 1\cdot\Pr(S_i=1) + 0\cdot\Pr(S_i=0) = \frac{8}{15}.
\]
Finally, because expectation is linear,
\[
\expect{S} =  \sum_{i=1}^{14} \expect{S_i}  =  14\cdot \frac{8}{15}.
\]

Note that this approach works despite the fact that the indicator random
variables $S_i$ are not independent.  That's the beauty of linearity of
expectation!

}

\eparts

\problem

% modifed from spring 97 Pset 13, 3

There are $n$ MIT students who are taking 6.042 and 6.003 this term.  To
make it easier on themselves, the professors in charge of these classes
have decided to randomly permute their class lists and then assign
students grades based on their rank in the permutation\footnote{\dots just
as many students have suspected \texttt{:-)}}.  Assume all permutations
are equally likely and that the ranking in each class is independent of
the other.

\bparts

\ppart
What is the expected number of students that have a higher rank
in 6.042 than 6.003?

\solution{

Let $X_i$ be random variable whose value is 1 if student i has higher rank
in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$ for
6.042 than the probability that student $i$ has higher rank on 6.042,
given that the student has rank $r$ in 6.042, is $(r-1)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the
probability that student $i$ has higher rank in 6.042 is
\[
\sum_{1\leq r \leq n}  \frac{1}{n} \frac{r-1}{n} = \frac{n-1}{2n}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x} = \expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{n-1}{2}.
\]

Another way to solve this problem is to observe that students with higher
rank in one class have lower rank in the other class, so by symmetry, the
expected number of higher- and lower-ranked students in either class is
the same.  The expected number of students with the same rank equals 1 by
linearity of expectation, since probability student ranked the same in
both schools is $1/n$.  These observations now yield same answer as above.

}

\ppart
What is the expected number of students that have a ranking at
least $k$ higher in 6.042 than in 6.003?

\solution{

This part can be done in the same way as the previous one.  Let $X_i$ be
the random variable whose value is 1 if student $i$ is ranked at least $k$
higher in 6.042 than 6.003 and 0 otherwise.  If student $i$ has rank of $r$
$(r>k)$ for 6.042 than the probability that student $i$ has at least $k$
higher rank in 6.042 given student ranked $r$ in 6.042 is $(r-k)/n$.  The
probability student $i$ has rank $r$ in 6.042 is $1/n$.  Thus, the probability
that student $i$ has at least $k$ higher rank in 6.042 is
\[
\sum_{k+1\leq r\leq n} \frac{1}{n} \frac{r-k}{n} = \frac{(n-k)(n-k+1)}{2n^2}.
\]
By linearity of expectation, the expected number of students with a higher
rank on 6.042 is
\[
\expect{x}=\expect{x_1}+\expect{x_2}+...+\expect{x_n} = \frac{(n-k)(n-k+1)}{2n}.
\]

}

\eparts


\problem

Ben Bitdiddle is asked to analyze a game in which a fair coin is tossed
until the first time a head turns up.  If this head occurs on the $n$th
toss, and $n$ is odd, then he wins $\$2^n/n$, but if $n$ is even, he loses
$\$2^n/n$.  Ben observes that the expected dollar win from this game is
the value of the series:
\[
(1/2) \cdot 2 - (1/4) \cdot 2 + (1/8) \cdot 8/3 + \cdots \pm (1/2^n) \cdot 2^n/n
 = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n.
\]
This is the \emph{alternating harmonic series}---a series whihc is known
to converge to a definite real number $r>0$.  Ben concludes that since $r
>0$, it's to his advantage to play this game.  As usual, Ben's
shoot-from-the-hip analysis is off the mark.  Explain.

\solution{

This series is convergent, but not \emph{absolutely} convergent.  The
definition of expectation requires absolute convergence, so the
expectation in this case is not defined.  The fact that the expectation is
undefined is no mere formality.  The number $r$ is not relevant to the
behavior of the game.  Indeed, we showed in a tutorial problem that by
reordering its terms, the series can be made to converge to any real value
or diverge to $\pm\infty$.

}


\problem 

In the Monte Carlo version of roulette there is only one green
slot---which is numbered 0---as opposed to the Las Vegas version, which
has 2 green slots numbered $0$ and $00$.  If you bet on red (or,
symmetrically, on black) and 0 comes up, one or more of these three
options may be offered:
\begin{enumerate}
\item[(a)] You get $1/2$ of your bet back, and the casino gets the other
half.

\item[(b)] Your bet is put ``in prison.''  If red comes up on the next
turn, you get your bet back (but don't win any money).  If black or 0
comes up, you lose your bet.

\item[(c)] Your bet is put in prison as before.  If red comes up on the
next turn, you get your bet back, and if black comes up on the next turn,
then you lose your bet.  If a 0 comes up on the next turn, then your bet
is put into ``double prison.''  If your bet is in double prison, and if
red comes up on the next turn, then your bet is moved back to ordinary
prison and the game proceeds as before.  If your bet is in double prison,
and if black or 0 come up on the next turn, then you lose your bet.

%(FIGURE).

\end{enumerate}
Note that all three of these options are better than Las Vegas roulette,
in which you simply lose your entire bet if 0 or 00 comes up.  But it
is not clear which is the best choice.  Find the expectation of a
one dollar bet on red under each option.  Which is best?

\solution{

Under option~(a), if red turns up you win 1 dollar, if black turns up
you lose one dollar, and if 0 turns up, you lose 1/2 dollar.  Thus, the
expected winnings are 
\[
1(\frac{18}{37}) + (-1)\frac{18}{37} + (\frac{-1}{2})(\frac{1}{37}) \approx
-0.0135.
\]

Under option~(b), if red turns up you win 1 dollar, if black turns up, you
lose 1 dollar, and if 0 followed by black or 0 turns up, you lose 1
dollar. Thus the expected winnings are
\[
1(\frac{18}{37}) + (-1)(\frac{18}{37}) + (-1)(\frac{1}{37})(\frac{19}{37})
\approx -0.0139.
\]

Under option (c), it is a bit more complicated.  Let $x$ be the
probability that you lose your money given that it is in prsion, and let
$y$ be the probability that you lose given that your money is in double
prison.  Then
\[
x = \frac{18}{37} + \frac{1}{37}y.
\]
Also, 
\[
y = \frac{19}{37} + \frac{18}{37}x.
\]
So, we have 
\[
x = \frac{18}{37} + \frac{1}{37}(\frac{19}{37} + \frac{18}{37}x).
\]
Solving, we have that $x = 685/1351$.  Thus, starting from the beginning,
the probability that you lose your bet is
\[
\frac{18}{37} + \frac{1}{37}x = \frac{25003}{49987}.
\]
Now, the only way you can win is if red comes up on the first turn, which
happens with probability $18/37$.  Thus the expected winnings are
\[
1 \cdot \frac{18}{37} - 1 \cdot \frac{25003}{49987} = -\frac{685}{49987}
\approx -0.0137.
\]

Thus, the simple option~(a) is actually the best.

}

\problem  %revised from S99 Final

Three hundred students take the 6.042 final exam.  The mean on the exam is
$90$ and the lowest score was 30.  You have no other information about the
students and the exam, e.g., you should not assume that the final is worth
100 points.

\bparts

\ppart State a best possible upper bound on the number of students who
scored at least $180$.  \hint Markov.

\solution{Let $R$ be the score.  Apply Markov's Bound to $R-30$:
\[
\prob{R \geq 180} = \prob{R-30 \geq 150} \leq \expect{R-30}/150 = 60/150 = 2/5,
\]
so at most $(2/5)300 = \textbf{120}$ students score $\geq 180$.}

\ppart Give an example set of scores which achieve your bound.

\solution{Of the 300 students, 120 score 180 and 180 score 30.  The mean
is
\[
(120 \cdot 180 + 180 \cdot 30)/300 = 90,
\]
as required.}


\eparts


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

\bparts

\ppart

What is the expectation and variance of the number of hearts that you
will have in your hand?

\solution{

Let $H$ be the number of hearts in your hand, and let $X_i$ be the
indicator variable that is 1 if card $i$ is a heart and is 0 otherwise, so
$H = \sum_{1\leq i\leq 13} X_i$.  Because $X_i$ is an indicator variable,
its expectation is the probability that card $i$ is a heart, namely, 1/4.
So
\[
\expect{H} = \sum_1^{13} 1/4 = 13/4.
\]

To compute variance, we use the definition:
\begin{eqnarray*}
\variance{\sum_{i=1}^{13} X_i} &=&
    \expect{(\sum_{i=1}^{13} X_i)^2} - \expect{\sum_{i=1}^{13} X_i}^2 \\
        &=& \expect{(\sum_{i=1}^{13} X_i)^2} - (13/4)^2 \\
        &=& \mathrm{E}[X_1^2 + X_1X_2 + X_1X_3 + \ldots + X_1X_{13} + \\
        &&   X_2X_1 + X_2^2 + X_2X_3 + \ldots + X_2X_{13} + \\
        &&        \vdots \\
        &&   X_{13}X_1 + X_{13}X_2 + \ldots + X_{13}^2] - (13/4)^2 \\
        &=& \expect{X_1^2} + \expect{X_1X_2} + \expect{X_1X_3} + \ldots + \expect{X_1X_{13}} + \\
        &&  \expect{X_2X_1} + \expect{X_2^2} + \expect{X_2X_3} + \ldots + \expect{X_2X_{13}} + \\
        &&        \vdots \\
        &&   \expect{X_{13}X_1} + \expect{X_{13}X_2} + \ldots + \expect{X_{13}^2} - (13/4)^2.
\end{eqnarray*}
Now we note that $\expect{X_i^2} = \expect{X_i}$ since $X_i$ is an
indicator variable, so $\expect{X_i^2} = 1/4$.  Also, when $i \neq j$,
$X_iX_j = 1$ if cards $i$ and $j$ are both hearts, and 0 otherwise.  The
probability that both cards are hearts is $(1/4)(12/51)$, and thus
$\expect{X_iX_j} = (1/4)(12/51) = 3/51$.  In the summation above, there
are 13 $\expect{X_i^2}$ terms, and $2\binom{13}{2} = 156$ terms of the
form $\expect{X_iX_j}$.  Thus,
\begin{eqnarray*}
 \variance{\sum_{i=1}^{13} X_i} &=& 13 \cdot \frac{1}{4} + 156 \cdot \frac{3}{51} - (\frac{13}{4})^2 \\
                &\approx& 1.863970588.
\end{eqnarray*}

}

% \textbf{REVISE TO SOLVE W/O COVARIANCE:}

% To compute variance we use the identity:
% \[
% \variance{\sum X_i} = \sum \variance{X_i} + \sum_{i\neq j} \covar{X_i,X_j}.
% \]
% where the second sum is taken over all possible ordered pairs of distinct
% $i$'s and $j$'s.  Now for each indicator variable we have
% \[
% \variance{X_i} = \expect{X_i^2} - \expectsq{X_i} = 1/4 - 1/16 = 3/8,
% \]
% and for each pair of distinct indicator variables we have
% \[
% \covar{X_i, X_j} = \expect{X_i X_j}-\expect{X_i}\expect{X_j} =
% \frac{1}{4} \frac{12}{51} - \frac{1}{16} = \frac{-1}{272}.
% \]
% Putting it all together,
% \begin{eqnarray*}
% \variance{H} & = & 
% \sum_{i=1}^{13}\variance{X_i} + 2\left(\sum_{1<=i<j<=13}\covar{X_i,X_j}\right)\\
%  &  = & 13 \frac{3}{8} + 2\binom{13}{2}\frac{-1}{272} = \frac{585}{136} = 4.30147.
% \end{eqnarray*}


\ppart What is the expectation and variance of the number of suits in
your hand?

\solution{

Similar to the first part: let $N$ denote the number of suits in a hand.
Let $X_s$ be the indicator variable which is 1 if there is a spade in the
hand and 0 otherwise. 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}} = 0.987209,
\]
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} = 4 \cdot 0.987209 = 3.94884.
\]
To compute variance:
\begin{eqnarray*}
 \variance{N} &=& \prob{N=1}(1 - \expect{N})^2 + \prob{N=2}(2- \expect{N})^2 + \\
              & & \qquad \prob{N=3}(3 - \expect{N})^2 + \prob{N=4}(4 - \expect{N})^2.
\end{eqnarray*}
Now we must calculate each of the probabilities.  First,
\[
\prob{N=1} = \frac{4} {\binom{52}{13}} = 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.

\[
\prob{N=2} = \frac{\binom{4}{2}[\binom{26}{13} - 2]}{\binom{52}{13}}
             = 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.  Thus $\binom{4}{2}(\binom{26}{13} -2)$ is the number of
hands with two suits.

\[
\prob{N=3} = \frac{\binom{4}{3}[\binom{39}{13} -
\binom{3}{2}\binom{26}{13} + 3]}{\binom{52}{13}} = 0.05097,
\]
because there are $\binom{4}{3}$ ways to choose the three suits.  There
are $\binom{39}{13}$ ways to choose 13 cards from the 39 cards of those
three suits.  But that also includes hands with two suits and one suit.
So, using Inclusion-Exclusion, we subtract the
$\binom{3}{2}\binom{26}{13}$ ways to choose two suits from the three suits
and then choose choose 13 cards from the 26 cards of those suits.  Next,
we add back the three ways to choose hands of one suit among the three.
Finally, we divide by the $\binom{52}{13}$ ways to choose a possible hand
of 13.

Of course, 
\[
\prob{N=4} = 1 - (\prob{N=1} +\prob{N=2} + \prob{N=3}) = 0.9489.
\]
This allows us to complete the calculation of the variance:
\[
\variance{N}=0.04874.
\]


%\textbf{REVISE TO SOLVE W/O COVARIANCE:}
% To compute variance, first compute variance of each of the indicator
% variables:
% \[
% \variance{X_i}=\expect{X_i^2} +\expectsq{X_i} = 0.987209 - 0.987209^2 =
% 0.0126273.
% \]
% Note: $\expect{X_i^2} = \expect{X_i}$ since $X_i$ is an indicator variable.


% To compute the covariance of any pair of the indicator variables, we
% need to compute $\expect{X_{i} X_{j}}$, in other words, the
% probability that a hand contains both suits $i$ and $j$. Let $I$ be
% event that the hand contains suit $i$, and $J$ be event that the hand
% contains suit $j$. Then
% \begin{eqnarray*}
% \prob{I \cap J} & = & 1 - \prob{\bar{I} \cup \bar{J}}\\ & = & 1 -
%  \prob{\bar{I}} - \prob{\bar{J}} + \prob{\bar{I} \cap \bar{J}}\\ & = &
%  1 - 2\frac{\binom{52-13}{13}}{\binom{52}{13}} +
%  \frac{\binom{52-13-13}{13}}{\binom{52}{13}} = 0.974434.
% \end{eqnarray*}

% Then covariance is
% \[
% \covar{X_{i},X_{j}} = \expect{X_{i} X_{j}} -
%            \expect{X_{i}}\expect{X_{j}} = 0.974434 - 0.987209^2 =
%            -0.00014723.
% \]

% Putting this all together we get that
% \begin{eqnarray*}
% \variance{N} & = & \variance{X_s} + \variance{X_h} + \variance{X_d} + \variance{X_c}
%        + \sum_{i \neq j \in \set{ s,h,d,c}} \covar{X_{i},X_{j}}\\
%      &  = & 4 \cdot 0.0126273 + 2\binom{4}{2}(-0.00014723) = 0.487424.
% \end{eqnarray*}

}

\eparts


\problem Suppose that $n$ 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$.

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

}

\ppart $\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)$.

}

\ppart $\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*}

}

\ppart $\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*}

}

\ppart  Using Chebyshev's
Inequality, show that $\prob{S_n \geq 11} \leq .01$ for any $n \geq
11$.

\solution{

\begin{eqnarray*}
\prob{S_n \geq 11} &=& \prob{S_n - \expect{S_n} \geq 11 - \expect{S_n}} \\
                 &=& \prob{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
%END   Tina's problems


%% Waiting for Godot
%% outcomes 6,8
%% Yu-Han, Fall 2001

\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


%% A Random Hat-Check
%% outcomes 6, 8
%% Yu-Han, Fall 2001

\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




%% Harry Potter mania, polling problem, estimation
%% new problem for fall 2001
%% outocmes 8,9
%% Yu-Han, Fall 2001

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


}



%% Unbiased Estimators
%% outcomes 8, mean, variance, mean as a random var
%% Yu-Han , Fall 2001
%% NEW PROBLEM 


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





%% Lost in Infinite Corridors
%% outcomes 8, 9, Wald's Thm, mean
%% Yu-Han, Fall 2001

\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








\end{problems}

\end{document}





