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

%\hidesolutions         
%\showsolutions
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document}
\inclassproblems{11M}


%%%% MONDAY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% NOTES FOR THE FUTURE: carnival dice took a long time for people who
%% had not done 041, and very few got to cool stickers at all. cool
%% stickers was too much for the first class - should instead have one
%% a straightforward mean time to failure example that wpould have
%% allowsed them to work through the series.

%% 
%% Carnival Dice
%% Prove Linearity formula
%% Hatcheck
%% Couples
%% Cool stickers?

\begin{problem}
\begin{problemparts}
\problempart In the game of Carnival Dice, the player chooses a number
from 1 to 6.  She then throws three fair and mutually independent
dice.  She wins one dollar if any die matches, and loses a dollar
otherwise. Let R be a random variable equal to her profit in one
round. What is $\expect{R}$?

\solution{
Let the random variable $R$ be the amount of money won or lost by the
player in a round.  We can compute the expected value of $R$ as
follows:
\begin{eqnarray*}
\expect{R}  & = &   -1 \cdot \pr{\mbox{0 matches}} +
                     1 \cdot \pr{\mbox{any match}}\\
            & = &   -1 \cdot \left(\frac{5}{6}\right)^3 +
                     1 \cdot \left(1 - \frac{5}{6}\right)^3\\
            & = &   \frac{-34}{216}
\end{eqnarray*}
The player can expect to lose approx 16 cents any round.
}

\problempart Consider a modified version of Carnival Dice. The game is
the same except she wins one dollar for \emph{each} die that matches
her number, and she loses one dollar if no die matches. What is
her expected profit now?

\solution{At first glance the new game appears to be fair; after all,
the player is now ``justly compensated'' if she rolls her number on
more than one die. But its not much better.

Let the random variable $R$ be the amount of money won or lost by the
player in a round.  We can compute the expected value of $R$ as
follows:
\begin{eqnarray*}
\expect{R}  & = &   -1  \cdot \pr{\mbox{0 matches}} +
                     1 \cdot \pr{\mbox{1 match}} +
                     2  \cdot \pr{\mbox{2 matches}} +
                     3 \cdot \pr{\mbox{3 matches}} \\
        & = &   -1 \cdot \left(\frac{5}{6}\right)^3 +
                1 \cdot 3\left(\frac{1}{6}\right)\left(\frac{5}{6}\right)^2+
                2 \cdot 3\left(\frac{1}{6}\right)^2\left(\frac{5}{6}\right)+
                3 \cdot \left(\frac{1}{6}\right)^3 \\
        & = &   \frac{-125 + 75 + 30 + 3}{216} \\
        & = &   \frac{-17}{216}
\end{eqnarray*}

Even with a \$3 payoff for three matching dice, the player can expect
to lose $17/216$ of a dollar, or about 8 cents, in every round. This
is still a horrible game for the player! }
\end{problemparts}
\end{problem}

\begin{problem}
Prove that $\expect{R_1 + R_2} = \expect{R_1} + \expect{R_2}$, where $R_1$
and $R_2$ are two random variables defined on the same sample space, but
not necessarily independent. (\hint Start from Definition~\ref{defexp1}).

\solution{
From the Course Notes:

\begin{proof}
Let $T \eqdef R_1+R_2$.  The proof follows straightforwardly by
rearranging terms using Definition~\ref{defexp1} of $\expect{T}$.
\begin{align*}
\expect{R_1 + R_2} & \eqdef \expect{T}\\
        & \eqdef \sum_{s \in \sspace} T(s) \cdot \pr{s}
                       & \text{(Def.~\ref{defexp1})}\\
        & = \sum_{s \in \sspace} (R_1(s) + R_2(s)) \cdot \pr{s}
                         & \text{(Def. of $T$)}\\
        & = \sum_{s \in \sspace} R_1(s) \pr{s} + 
              \sum_{s \in \sspace} R_2(s) \pr{s} & \text{(rearanging terms)}\\
        & = \expect{R_1} + \expect{R_2}.  & \text{(Def.~\ref{defexp1})}
\end{align*}
\end{proof}
}
\end{problem}

\begin{problem}
There is a dinner party where $N$ men check their hats.  The hats
are mixed up during dinner, so that afterward each man receives a
random hat.  In particular, each man gets his own hat with probability
$1/N$.  What is the expected number of men who get their own hat?

\solution{Also from the Course Notes.

Let the random variable $R$ be the number of men that get
their own hat. The trick is to express $R$ as a sum of indicator
variables.  In particular, let $R_i$ be an indicator for the event
that the $i$th man gets his own hat. That is, $R_i = 1$ is the event
that he gets his own hat, and $R_i = 0$ is the event that he gets the
wrong hat.  The number of men that get their own hat is the sum of
these indicators:
\[
R = R_1 + R_2 + \cdots + R_N.
\]

These indicator variables are {\em not} mutually independent.  For
example, if $N-1$ men all get their own hats, then the last man is
certain to receive his own hat. But linearity of expectation, doesn't
require indicator variables are independent, because no matter what,
we can take the expected value of both sides of the equation above and
apply linearity of expectation:
\begin{equation*}
\expect{R} =  \expect{R_1 + R_2 + \cdots + R_N} 
           =  \expect{R_1} + \expect{R_2} + \cdots + \expect{R_N}.
\end{equation*}
The expected value of an indicator variable is always the probability
that the indicator is 1. In this case, the quantity $\pr{R_i = 1}$ is
the probability that the $i$th man gets his own hat, which is just
$1/N$.  We can now compute the expected number of men that get their
own hat:
\[\begin{array}{rcccccccccc}
\expect{R} &=&  \expect{R_1} &+& \expect{R_2} &+& \cdots &+& \expect{R_N} \\
           &=&  \cfrac{1}{N} &+& \cfrac{1}{N} &+& \cdots &+& \cfrac{1}{N} &=& 1.
\end{array}\]

We should expect exactly one man to get the right hat!
}
\end{problem}


\begin{problem}
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*}

Another way of thinking is that the probability of getting a new
sticker in a bag is $(n-k)/n$, so what you want is the time until the
first bag is opened that contains a new sticker which is just mean
time to failure i.e. $1/p = n/(n-k)$.
}

\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{problem}

\iffalse
\begin{problem} An airport bus deposits 8 passengers at 6
stops.  Assume that each passenger is as likely to get off at any stop
as another and that they act independently.  The bus stops only if
someone wants to get off.  What is the probability that nobody gets
off at the third stop?  What is the expected number of stops it will
make?

\solution{
For each individual, the probability he {\em does not} get off at the
third stop is $\frac{5}{6}$.  Therefore, the probability
that no one gets off at the third stop is $(\frac{5}{6})^{8} = 
0.2326$.

Let $I_k$ be an indicator variable for whether the bus stops at the
$k$-th stop.  Then, $X=\sum_k I_k$ is the total number of stops.  By
linearity of expectation,
\[
E(X) = E(I_1) + E(I_2) + E(I_3) + E(I_4) + E(I_5) + E(I_6)
\]

For each $I_k$, the $E(I_k)$ is the probability the bus stops at the
$k$-th stop, or $1-0.2326=0.7674$.  Therefore, $E(X) = 6(0.7674) = 4.6044$.
}
\end{problem}
\fi

\iffalse
\begin{problem}
Ben Bitdiddle is asked to analyze a game in which a fair coin is
tossed until the first time a head turns up.  If this head occurs on
the $n$th toss, and $n$ is odd, then he wins $\$2^n/n$, but if $n$ is
even, he loses $\$2^n/n$.  Ben observes that the expected dollar win
from this game is the value of the series:
\[
(1/2) \cdot 2 - (1/4) \cdot 2 + (1/8) \cdot 8/3 + \cdots \pm (1/2^n) \cdot 2^n/n
 = 1 - 1/2 + 1/3 - 1/4 + \cdots \pm 1/n.
\]
This is the \emph{alternating harmonic series}---a series whihc is known
to converge to a definite real number $r>0$.  Ben concludes that since $r
>0$, it's to his advantage to play this game.  As usual, Ben's
shoot-from-the-hip analysis is off the mark.  Explain.

\solution{ This series is convergent, but not \emph{absolutely}
convergent.  The definition of expectation requires absolute
convergence, so the expectation in this case is not defined.  The fact
that the expectation is undefined is no mere formality.  The number
$r$ is not relevant to the behavior of the game.  Indeed, we showed in
a tutorial problem {\bf(DID WE?)} that by reordering its terms,
the series can be made to converge to any real value or diverge to
$\pm\infty$.  }
\end{problem}
\fi

\appendix
\section{Appendix}

\begin{definition}\label{defexp1}
The \emph{expectation}, $\expect{R}$, of a random variable, $R$, on
the sample space $S$, is
defined as:
\begin{equation}\label{expsum1}
\expect{R} \eqdef \sum_{s \in \sspace} R(s) \cdot \pr{s}.
\end{equation}
\end{definition}

Another equivalent definition is:
\begin{definition}\label{defexp2}
The \emph{expectation} of random variable, $R$, is:
\begin{equation}\label{expsum2}
\expect{R} \eqdef \sum_{r \in \range{R}} r \cdot \pr{R = r}.
\end{equation}
\end{definition}


\begin{theorem}\label{R>i}
If $R$ is a random variable with range $\naturals$, then
\[
\expect{R} = \sum_{i=0}^{\infty} \pr{R > i}.
\]
\end{theorem}

\begin{theorem}(Expectation of a Sum)
For any random variables $R_1, \dots, R_k$,
\[
\expect{\sum_{i=1}^k R_i} = \sum_{i=1}^k \expect{R_i}.
\]
\end{theorem}


\begin{theorem}
\label{th:series}
If $\abs{x} < 1$, then
\[
\sum_{i=0}^\infty x^i = \frac{1}{1-x}.
\]
\end{theorem}

\end{document}



