\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{9}

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

\begin{problem}
The course notes describe a useful formula for computing the
expectation of a {\em natural-valued} random variable $R$:

\begin{eqnarray*}
\expect{R} & = & \sum_{i=0}^{\infty} \pr{R > i}
\end{eqnarray*}

Suppose that we roll $n$ fair, mutually independent dice.  Let $R$ be
the {\em largest} number that comes up.

\bparts

\ppart What is $\pr{R \leq i}$ where $i$ is a nonnegative integer?

\solution{The probability that one die is less than or equal to $i$ is
$i/6$ for $i \leq 5$ and 1 for all larger $i$.  Since the $n$ dice are
independent, we have:

\begin{eqnarray*}
\pr{R \leq i} & = & \left\{
\begin{array}{ll}
(i/6)^n & \text{for $i \leq 5$} \\
1 & \text{for $i > 5$}
\end{array}
\right.
\end{eqnarray*}
}

\ppart What is $\pr{R > i}$ where $i$ is a nonnegative integer?

\solution{This is the complement of the preceding event, so we have:

\begin{eqnarray*}
\pr{R > i} & = & \left\{
\begin{array}{ll}
1 - (i/6)^n & \text{for $i \leq 5$} \\
0 & \text{for $i > 5$}
\end{array}
\right.
\end{eqnarray*}
}

\ppart What is $\expect{R}$?

\solution{
Applying the expectation formula given at the start of the problem gives:

\begin{eqnarray*}
\expect{R}
	& = &	\sum_{i=0}^{\infty} \pr{R > i} \\
	& = &	\sum_{i=0}^5 \left(1 - (i/6)^n\right) \\
	& = &	6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}
\end{eqnarray*}
}

\eparts

\end{problem}

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

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

\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{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{
\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{align*}
\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}
        & = H_n & \text{(the $n$-th harmonic number)} \\
        & \sim \ln n
\end{align*}

\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

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

\end{problem}

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

\begin{problem}
The number of squares that a piece advances in one turn of the game
Monopoly is determined as follows:

\begin{itemize}

\item Roll two dice, take the sum of the numbers that come up, and
advance that number of squares.

\item If you roll {\em doubles} (that is, the same number comes up on
both dice), then you roll a second time, take the sum, and advance
that number of additional squares.

\item If you roll doubles a second time, then you roll a third time,
take the sum, and advance that number of additional squares.

\item However, as a special case, if you roll doubles a third time,
then you go to jail.  Regard this as advancing zero squares overall
for the turn.

\end{itemize}

You may find the law of total probability useful for this problem.  If
$E_1, E_2, \ldots, E_n$ are disjoint events whose union is the whole
sample space, then:

\begin{eqnarray*}
\expect{R} & = & \sum_{i=1}^n \expect{R \mid E_i} \cdot \pr{E_i}
\end{eqnarray*}

\bparts

\ppart What is the expected sum of two dice, given that the same
number comes up on both?

\solution{There are six equally-probable sums: 2, 4, 6, 8, 10, and 12.
Therefore, the expected sum is:

\begin{eqnarray*}
\frac{1}{6} \cdot 2 + \frac{1}{6} \cdot 4 + \ldots + \frac{1}{6} \cdot 12
	& = &	7
\end{eqnarray*}
}

\ppart What is the expected sum of two dice, given that different
numbers come up?

\solution{Let the random variables $D_1$ and $D_2$ be the numbers that
come up on the two dice.  Let $E$ be the event that they are equal.
The law of total expectation says:

\begin{eqnarray*}
\expect{D_1 + D_2}
	& = &	\expect{D_1 + D_2 \mid E} \cdot \pr{E} + 
		\expect{D_2 + D_2 \mid \overline{E}} \cdot \pr{\overline{E}} \\
\end{eqnarray*}

Two dice are equal with probability $\pr{E} = 1 / 6$, the expected sum
of two independent dice is 7, and we just showed that $\expect{D_1 +
D_2 \mid E} = 7$.  Substituting in these quantities and solving the
equation, we find:

\begin{eqnarray*}
7	& = &	7 \cdot \frac{1}{6} + 
		\expect{D_2 + D_2 \mid \overline{E}} \cdot \frac{5}{6} \\
\expect{D_2 + D_2 \mid \overline{E}}
	& = &	7
\end{eqnarray*}
}

\ppart To simplify the analysis, suppose that we always roll the dice
three times, but may ignore the second or third rolls if we didn't
previously get doubles.  Let the random variable $X_i$ be the sum of
the dice on the $i$-th roll, and let $E_i$ be the event that the
$i$-th roll is doubles.  Write the expected number of squares a piece
advances in these terms.

\solution{
From the total expectation formula, we get:

\begin{eqnarray*}
\expect{\text{advance}}
	& = &	\expect{X_1 \mid \overline{E_1}}
			\cdot \pr{\overline{E_1}} \\
	&&	+ \expect{X_1 + X_2 \mid E_1 \cap \overline{E_2}}
			\cdot \pr{E_1 \cap \overline{E_2}} \\
	&&	+ \expect{X_1 + X_2 + X_3 \mid E_1 \cap E_2 \cap
			  \overline{E_3}}
			\cdot \pr{E_1 \cap E_2 \cap \overline{E_3}} \\
	&&	+ \expect{0 \mid E_1 \cap E_2 \cap E_3}
			\cdot \pr{E_1 \cap E_2 \cap E_3} \\
\end{eqnarray*}
}

\ppart What is the expected number of squares that a piece advances in
Monopoly?

\solution{
We begin with the preceding equation, use linearity of expectation,
and then plug in values from parts (a) and (b).

\begin{eqnarray*}
\expect{\text{advance}}
	& = &	\expect{X_1 \mid \overline{E_1}}
			\cdot \pr{\overline{E_1}} \\
	&&	+ \expect{X_1 + X_2 \mid E_1 \cap \overline{E_2}}
			\cdot \pr{E_1 \cap \overline{E_2}} \\
	&&	+ \expect{X_1 + X_2 + X_3 \mid E_1 \cap E_2 \cap
			  \overline{E_3}}
			\cdot \pr{E_1 \cap E_2 \cap \overline{E_3}} \\
	&&	+ \expect{0 \mid E_1 \cap E_2 \cap E_3}
			\cdot \pr{E_1 \cap E_2 \cap E_3} \\
	& = &	7 \cdot \frac{5}{6}
		+ 14 \cdot \frac{1}{6} \cdot \frac{5}{6}
		+ 21 \cdot \frac{1}{6} \cdot \frac{1}{6} \cdot \frac{5}{6} +
		+ 0 \\
	& = &	\frac{301}{36}
\end{eqnarray*}
}

\eparts

\end{problem}

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

\begin{problem}
Let $R$ and $T$ be independent, real-valued random variables, and let
$f, g: \reals \to \reals$ be any two functions on the real numbers.
Prove that $f(R)$ and $g(T)$ are independent random variables.

\solution{Let's begin by stating what we know.  Since $R$ and $T$ are
independent, for every pair of real numbers $x$ and $y$, we have:

\begin{eqnarray}
\label{eqn:know}
\pr{R = x \cap T = y} & = & \pr{R = x} \cdot \pr{T = y}
\end{eqnarray}

Now let's state what we have to prove.  We must show that $f(R)$ and
$g(T)$ are independent random variables; that is, we must show that
for every pair of real numbers $u$ and $v$:

\begin{eqnarray}
\label{eqn:show}
\pr{f(R) = u \cap g(T) = v} & = & \pr{f(R) = u} \cdot \pr{g(T) = v}
\end{eqnarray}

We know about events of the form $R = x$, but must prove something
about events of the form $f(R) = u$.  These two are closely related,
however.  In particular, we have:

\begin{eqnarray}
\label{eqn:equiv}
[f(R) = u]
    & = & \bigcup_{x: f(x) = u} R = x
\end{eqnarray}

Taking the probability of each side of this equation gives:

\begin{eqnarray}
\label{eqn:probequiv}
\pr{f(R) = u}
    & = & \sum_{x: f(x) = u} \pr{R = x}
\end{eqnarray}

Now we can solve the problem by transforming the left side of
equation~\ref{eqn:show} into the right side.

\begin{eqnarray*}
\pr{f(R) = u \cap g(T) = v}
    & = & \pr{\left(\bigcup_{x:\ f(x) = u} R = x\right) \cap
              \left(\bigcup_{y:\ g(y) = v} T = y\right)} \\
    & = & \pr{\bigcup_{(x,y):\ f(x) = u,\ g(y) = v} R = x \cap T = y} \\
    & = & \sum_{(x,y):\ f(x) = u,\ v(y) = v} \pr{R = x \cap T = y} \\
    & = & \sum_{(x,y):\ f(x) = u,\ v(y) = v} \pr{R = x} \cdot \pr{T = y} \\
    & = & \left(\sum_{x:\ f(x) = u} \pr{R = x}\right) \cdot
          \left(\sum_{y:\ g(x) = v} \pr{T = y}\right) \\
    & = & \pr{f(R) = u} \cdot \pr{g(T) = v}
\end{eqnarray*}

The first step uses equation~\ref{eqn:equiv}, the second uses a set
identity, and the third uses the sum rule.  In the fourth step, we use
the independence of the random variables $R$ and $T$.  We break the
sum into a product of two sums in the fifth step and then apply
equation~\ref{eqn:probequiv} in the last step.}
\end{problem}
\end{document}
