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

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

\begin{document}
\inclassproblems{12, Mon}


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

%% Carnival Dice
%% Prove Linearity formula
%% Hatcheck Game (play and collect stats, then solve)
%% Binomial Distribution

\begin{problem}
%%\begin{problemparts}
%%\problempart 
In the original 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. This is a losing proposition for the player.

\iffalse
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 
\fi

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

\solution{

%{\em NOTE TO TAs: Remove before solutions are released. Get them to
%write it on the board, and be methodical about it (define a random
%variable R that is the expected profit)}



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}
There is a dinner party where $N$ people check their hats.  The hats
are mixed up during dinner, so that afterward each person receives a
random hat.  In particular, each person gets their own hat with
probability $1/N$.  What is the expected number of people who get
their own hat?

\solution{
%{\em NOTES FOR TAs (comment out before solutions are
%released): We will play the game and collect stats first, by writing
%names on paper and putting them in a hat and then passing the hat
%around. If they finish the analysis quickly ask them how they might
%consider doing it without using linearity of expectations.}

Also from the Course Notes.

Let the random variable $R$ be the number of people 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
person gets their own hat. That is, $R_i = 1$ is the event that they
gets their own hat, and $R_i = 0$ is the event that they gets the
wrong hat.  The number of people 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$ people all get their own hats, then the last person
is certain to receive their 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 person gets his own hat, which is just
$1/N$.  We can now compute the expected number of people 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 person to get the right hat!
}
\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{

%{\em NOTES FOR TAs (comment out before solutions are released): First
%make sure that they understand (and can explain) the relation between
%the two definitions of expectation. The basic idea is to group the
%sample points according to their R value}

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}
Let $R$ be the number of heads that come up when we toss $n$
independent coins, where each coin comes up heads with probability
$p$. The random variable $R$ has a binomial distribution. Prove that
the expected value of $R$ is $np$.

\solution{

%{\em NOTES FOR TAs (comment out before solutions are released): If you
%need time to discuss quiz results, etc, then punt this question but
%make sure they udnerstand they are responsible for it (it is directly
%from the notes)}

Let $H_{n,p}$ be the number of heads after the flips.  Then $H_{n,p}$ has
the binomial distribution with parameters $n$ and $p$.  Now let $I_k$ be
the indicator for the $k$th coin coming up heads.  By
Lemma~\ref{defexp2}, we have
\[
\expect{I_k} = p.
\]
But
\[
H_{n,p} = \sum_{k=1}^n I_k,
\]
so by linearity
\[
\expect{H_{n,p}} = \expect{\sum_{k=1}^n I_k} = \sum_{k=1}^n \expect{I_k} =
\sum_{k=1}^n p = pn.
\]

That is, the expectation of a $n,p$-binomially distributed variable is
$pn$.
}


\end{problem}

%---------------------------------------------------------------------%


\iffalse
\begin{problem} Calculate the expected number
of ``triples'' of people having the same birthdate\footnote{By
birthdate we mean born on the same day of the same month. Assume that
all birthdates are equally likely and independently chosen (by a
higher force).} in a classroom with $m$ people on a planet with $N$
days in a year. How many such triples would you expect to see in this
class ($m=100,N=365$)?

\solution{
The probability that a triple of students has the same birthday is
$1/N^2$. The number of possible triples is $\binom{m}{3}$ which is
$\frac{m(m-1)(m-2)}{6}$. Problem is that these triples are not
independent of each other, so computing the probability of $i$ triples
is very hard. However if we use the linearity of expectations, then we
get to ignore this thorny issue. As in the part(b), each triple gets
assigned an indicator random variable and the expected value of that
variable is $1/N^2$ (feel free to verify rigorously). Let $T$ be the
random variable representing the number of triples with the same
birthdate. Then,

$$\expect{T} = \frac{m(m-1)(m-2)}{6N^2}$$

For this class that is $100.99.98/6.365.365 = 1.2 (approx)$
}
\end{problem}
\fi

\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

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



