\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\begin{document}
%\pset{11}{April 29, 1999}{Thursday, May 6}
\psol{11}{May 7, 1999}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\bigskip #1}
\newcommand{\Ex}{\text{Ex}}

% \reading{Lecture notes 22 and 23.}

\begin{problems}

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

\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*}
\Ex(\text{payoff})
	& = &	-1 \cdot \left(\frac{4}{12} + \frac{5}{12} + \frac{6}{12} + 
				\frac{5}{12} + \frac{4}{12} \right) \\
	& & \mbox{}
		+1 \cdot \left(\frac{1}{12} + \frac{2}{12} + \frac{3}{12} + 
			\frac{3}{12} + \frac{2}{12} + \frac{1}{12} \right) \\
	& = &	-1 \ \text{dollar}
\end{eqnarray*}
}

\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\frac{1}{2}$.  Therefore, by Wald's Theorem, the
expected payoff is $1 \cdot 3\frac{1}{2} - 3 = \frac{1}{2}$ dollar.}
\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, $\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.}

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

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

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

\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{\Ex(\text{Stas's payoff})} \quad \quad \\
	& = &	4 \cdot \Pr(\text{Stas alone is right}) \\
&&\mbox{}	+ 1 \cdot \Pr(\text{Stas and one other player are right}) \\
&&\mbox{}	+ 0 \cdot \Pr(\text{All or none of the players are right}) \\
&&\mbox{}	- 2 \cdot \Pr(\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 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, then the player rolls
the dice a second time, sums the results, and advances that many
additional squares.

\item If the same number comes up on both dice the second time, then the
player rolls the dice a third time, sums the results, and advances
that many additional squares.

\item If the same number comes up on both dice the third time, then
the player ``goes to jail''.  In this special case, we define the
total number of squares advanced by the player to be 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.

Let the random variable $R_1$ be the sum of the two dice on the first
role, and let $I_i$ be an indicator for the event that the dice come
up the same on the first roll.  We can express the random variable
$R$, the number of squares advanced by the player, as follows.

\begin{eqnarray*}
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)
\end{eqnarray*}

We can take expectations of both sides and reason as follows:

\begin{eqnarray*}
\Ex(R)	& = &	\Ex(R_1)
		 + \Ex(I_1 R_2)
		 + \Ex(I_1 I_2 R_3) \\
	& & \mbox{}
		 - \Ex(I_1 I_2 I_3 R_1)
		 - \Ex(I_1 I_2 I_3 R_2)
		 - \Ex(I_1 I_2 I_3 R_3) \\
	& = &	\Ex(R_1)
		 + \Ex(I_1) \cdot \Ex(R_2)
		 + \Ex(I_1) \cdot \Ex(I_2) \cdot \Ex(R_3) \\
&&\mbox{}	 - \Ex(I_2) \cdot \Ex(I_3) \cdot \Ex(I_1 R_1) \\
&&\mbox{}	 - \Ex(I_1) \cdot \Ex(I_3) \cdot \Ex(I_2 R_2) \\
&&\mbox{}	 - \Ex(I_1) \cdot \Ex(I_2) \cdot \Ex(I_3 R_3)
\end{eqnarray*}

Note that the expectation of $R_i$ is $7$, and the expectation of
$I_i$ is $\frac{1}{6}$.  Futhermore, $\Ex(I_i R_i) = \frac{7}{6}$ by
direct calculation.  Substituting into the formula above gives:

\begin{eqnarray*}
\Ex(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 $\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, 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*}
\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, six-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.}

\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{\Ex(\text{\# bags to get new kind})} \quad \\
	& = &	\sum_{i=0}^{\infty} \Pr(\text{\# bags to get new kind} > i) \\
	& = &	\sum_{i=0}^{\infty} \Pr(\text{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{\Ex(\text{\# bags to get all kinds})} \quad \\
	& = &	\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{problems} \end{document}
