\documentclass[11pt,twoside]{article}

\usepackage{latex-macros/course}

\begin{document} 
\inclassproblems{14, Wed.}

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

\begin{problem}
Amy, Bill, and Poor Pete play a game:
\begin{itemize}
\item Each player puts \$2 on the table.
\item Each player secretly writes a number between 1 and 6.
\item They roll a fair die.
\item The money on the table is divided among the players that guessed
correctly.  If no one guessed correctly everyone gets their money back.
\end{itemize}

Suppose Amy and Bill cheat by picking a pair of \textit{distinct}
numbers uniformly at random.  What is Poor Pete's expected payoff?

%(One approach is to use a tree diagram that branches first on whether
%Pete guessed correctly and second on whether Amy or Bill guessed
%correctly.)

\solution{
A tree diagram is worked out below.

\bigskip
\centerline{\resizebox{!}{2in}{\includegraphics{poor-pete}}}
\bigskip

Poor Pete's expected payoff is:

\begin{equation*}
\frac{2}{36} \cdot 1 + \frac{4}{36} \cdot 4 + \frac{10}{36} \cdot (-2) + \frac{20}{36} \cdot 0 = - \frac{1}{18} \text{ dollars}
\end{equation*}
}
\end{problem}

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

\instatements{\newpage}

\begin{problem}
Every time I purchase a kid's meal at Taco Bell, I am graciously
presented with a miniature ``Racin' Rocket'' car together with a
launching device which enables me to project my new vehicle across any
tabletop or smooth floor at high velocity.  Truly, my delight knows no
bounds.

There are $n$ different types of Racin' Rocket car (blue, green, red,
gray, etc.).  The type of car presented to me each day by the kind
woman at the Taco Bell register appears to be selected uniformly and
independently at random.  The goal of this problem is to compute the
expected number of kids meals that I must purchase in order to acquire
at least one of each type of Racin' Rocket car.

(This is traditionally called the {\em coupon collector problem}.  It
arises frequently in the analysis of randomized algorithms and
systems.)

\bparts

\ppart Suppose that I have acquired $k$ cars already.  Let the random
variable $X_k$ equal the number of additional kid's meals I must
purchase in order to obtain a type of car that I do not already have.
What is the expected value of $X_k$?

\solution[\vspace{2in}]{Each kid's meal contains a type of car that I
already have with probability $k / n$.  Therefore, each meal contains
a new type of car with probability $1 - k / n = (n - k) / n$.
Therefore, the expected number of meals until I get a new kind of car
is $n / (n - k)$ by the ``expected time to success'' formula.}

\ppart Let the random variable $T$ be the total number of kids' meals
that I must purchase.  Express $T$ in terms of the random variables
$X_k$.

\solution[\vspace{1in}]{
\begin{eqnarray*}
T & = & X_0 + X_1 + X_2 + \ldots + X_{n-1}
\end{eqnarray*}
}

\ppart What is the expected value of $T$?  Also, give an approximate
answer using the fact that:
\begin{equation*}
\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}
= H_n \sim \ln n
\end{equation*}

\solution{By the solutions to the preceding parts and linearity of
expectation, we have:


\begin{eqnarray*}
\expect{T}
	& = & \expect{X_0 + X_1 + X_2 + \ldots + X_{n-1}} \\
	& = & \expect{X_0} + \expect{X_1} + \expect{X_2} +
		\ldots + \expect{X_{n-1}} \\
	& = & \frac{n}{n} + \frac{n}{n-1} + \frac{n}{n-2} +
		\ldots + \frac{n}{1} \\
	& = & n \cdot \left(\frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2} +
		\ldots + \frac{1}{1}\right) \\
	& = & n H_n \\
	& \sim & n \ln n
\end{eqnarray*}
}

\eparts
\end{problem}

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

\instatements{\newpage}

\begin{problem}
Let's debunk another common, but incorrect analysis of the
two-envelope problem.  First, we need a mathematical model of Eric.
Let $e_k$ be the probability that Eric puts $k$ dollars in one
envelope and $2k$ in the other.  Assume the Carlos picks one of the
two envelopes uniformly at random.

\bparts

\ppart What is the expected amount of money in the envelope that
Carlos picks?

\solution[\vspace{1.5in}]{From the definition of expectation:
\begin{equation*}
\expect{\text{money in envelope picked}}
    = \sum_{k=1}^{\infty} \frac{e_k}{2} \cdot k + \frac{e_k}{2} \cdot 2k
    = \sum_{k=1}^{\infty} \frac{3}{2} k e_k
\end{equation*}
}

\ppart What is the expected amount of money in the envelope that
Carlos does not pick?

\solution[\vspace{0.75in}]{We get the same answer as before:
\begin{equation*}
\expect{\text{money in envelope not picked}}
    = \sum_{k=1}^{\infty} \frac{e_k}{2} \cdot 2k + \frac{e_k}{2} \cdot k
    = \sum_{k=1}^{\infty} \frac{3}{2} k e_k
\end{equation*}
}

\ppart Suppose that Carlos finds \$8 in the envelope he chooses.  Here
is a fallacious argument:

\begin{quotation}
\noindent Since he picked an envelope at random, the other envelope is
equally likely to contain either \$4 or \$16.  Therefore, the expected
amount of money in the other envelope is:
\begin{equation*}
\frac{1}{2} \cdot \$4 + \frac{1}{2} \cdot \$16 = \$10
\end{equation*}
\noindent Therefore, he should switch!
\end{quotation}

What is the probability that the other envelope contains \$4, given
that Carlos sees \$8?  Why is the above argument wrong?

\solution[\vspace{1.5in}]{
\begin{align*}
\prcond{\text{other has \$4}}{\text{sees \$8}}
    & = \frac{\pr{\text{other has \$4} \cap {\text{sees \$8}}}}
             {\pr{\text{sees \$8}}} \\
    & = \frac{e_4 / 2}{e_4 / 2 + e_8 / 2} \\
    & = \frac{e_4}{e_4 + e_8}
\end{align*}

The error in the argument is that the other envelope is not equally
likely to contain \$4 or \$16.  Instead, the probability depends on
Eric's strategy for placing money in the envelopes.}

\ppart Let $E$ be the event that the other envelope contains \$4.  Use
the law of total expectation to compute the expected amount of money
in the other envelope

\solution{
\begin{align*}
\expect{\text{\$ in other}} & =
    \expect{\text{\$ in other} \mid E} \cdot \pr{E} +
    \expect{\text{\$ in other} \mid \bar{E}} \cdot \pr{\bar{E}} \\
    & = 4 \cdot \frac{e_4}{e_4 + e_8} + 16 \cdot \frac{e_8}{e_4 + e_8} \\
    & = \frac{4 e_4 + 16 e_8}{e_4 + e_8}
\end{align*}

Notice that this quantity could be anywhere between \$4 and \$16,
depending on the values of $e_4$ and $e_8$.}

\eparts

\end{problem}

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

\end{document}
