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

\begin{document}
%\pset{11}{April 29, 1999}{Thursday, May 6}
\psol{11}{May 11, 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 values 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 the roll of one die 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{21}{6} \\
	& = & \frac{7}{2}.
\end{eqnarray*}

By linearity of expectation, the sum of the rolls of three dice is

\begin{eqnarray*}
\frac{7}{2} + \frac{7}{2} + \frac{7}{2} & = & \frac{21}{2}.
\end{eqnarray*}
}

\problempart The product of the rolls on three dice.

\solution{For independent random variables, the expectation of a
product is the product of the expectations.  Therefore, the expected
product is

\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} & = & \frac{49}{4}.
\end{eqnarray*}
}

\problempart The sum of the rolls on a number of dice given by the roll
of a die.

\solution{ By Wald's Theorem, the expectation is again

\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{Only the first; the other answers use 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{5}{12} + \frac{6}{12} + \frac{7}{12} + 
				\frac{6}{12} + \frac{5}{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 heads.  For each
tails that you flip, 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$ 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 / (n-1)$, since a wife is equally likely to
occupy each of the $n-1$ positions relative to her husband and there
are two positions right next to him.  Consequently, $\Pr(I_k = 1) = 2
/ (n-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}{n-1} \\
	& = &	\frac{2n}{n-1}
\end{eqnarray*}
}

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

\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 > 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)} Stas, Zully, and Jared like to 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 at random,
and independently of one another.  However, Zully always peeks a
Jared's guess and picks a {\em different} number uniformly at random.

\begin{problemparts}

\problempart Each player's expected payoff?

\solution{
Stas's payoff is:

\begin{eqnarray}
\Ex(\text{Stas's payoff})
	& = &	4 \cdot \Pr(\text{Stas alone right}) +
		1 \cdot \Pr(\text{Stas and another right}) \\
&&\mbox{}	+ 0 \cdot \Pr(\text(All or none right)) +
		-2 \cdot \Pr(\text(Stas wrong, another right)) \\
	& = &	4 \cdot \Pr\left(\frac{1}{6}\right) \cdot
			\Pr\left(\frac{4}{6}\right)
		1 \cdot \Pr\left(\frac{1}{6}\right) \cdot
			\Pr\left(\frac{2}{6}\right) \\
&&\mbox{}	-2 \cdot \Pr\left(\frac{5}{6}\right) \cdot
			\Pr\left(\frac{2}{6}\right) \\
	& = &	- \frac{1}{18} \ \text{dollars}
\end{eqnarray}

Jared and Zully's situations are actually symmetric; therefore, their
expected payoffs are both $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 number
of squares advanced 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{This problem can be solved by many methods, including brute
force.  Here we use indicator variables and make extensive use of
expectation identitities.

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.  We can express the random variable $R$, the number of
squared advanced by the player, as follows.

\begin{eqnarray*}
R	& = &	R_1 + I_1 (R_2 + I_2 (R_3 - I_3 (R1 + R2 + R3)))
\end{eqnarray*}

We can now take the expected value of both sides.  Note that $R_i$ and
$I_i$ are dependent.

\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 R1)
		 - \Ex(I_1 I_2 I_3 R2)
		 - \Ex(I_1 I_2 I_3 R3) \\
\Ex(R)	& = &	\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 R1)
		 - \Ex(I_1) \cdot \Ex(I_3) \cdot \Ex(I_2 R2)
		 - \Ex(I_1) \cdot \Ex(I_2) \cdot \Ex(I_3 R3)
\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, 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.}

\end{problemparts}


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

\problem {\bf (15 points)} Each bag of Doritos contains a cool
sticker.  There are $n$ different types of sticker, and I want to
collect at least one sticker of each type.  Assume that the types of
sticker in bags of Doritos are uniformly random and mutually
independent.

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

\solution{

}

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

\solution{

}

\end{problemparts}

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

\problem {\em Alternate.}  There are 28 people in a room.  What is the
expected number of pairs of people with the same birthday?

\problem {\em Alternate.} Analyze $\Ex(X^2) - \Ex(X)^2$ for a few
random variables $X$ to get some advance intuition about variance.

\problem {\em Alternate.} What is the expected number of inversions in
a random permutation?

\problem {\em Alterate.} What is the expected number of length-k
cycles in a random graph with edge probability $1/2$?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems} \end{document}
