\documentstyle[12pt,twoside]{article}

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

\begin{document}


\begin{problems}

%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
%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 {\bf (15 points)} 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{The probability that I must eat $i$ or more bags is:
\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{number of 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{We sum the expected number of bags to get the first kind,
the expected number to get the second kind, and so forth.
\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)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

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

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



