%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 10: Applications of Discrete Random Variables }

{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}

{\bf \large The bins and balls problem } \\

\smallskip
Suppose we throw $m$ balls into $n$ bins randomly. \\
On average, how many bins will be empty? \\
On average, how many bins will have one ball in them?

\vspace{1cm}
{\large \bf The coupon collectors problem} \\

\smallskip
Suppose we have a bin containing $n$ types of coupons and we draw coupons
one at a time from the bin at random.  Assume the probability of drawing each type
of coupon is $1/n$ and the bin has a very large number of coupons.
On average, how many draws do we need to make until we get all $n$ coupons?

\vspace{2cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{definition}
Let $S$ be a sample space and $X$ a random variable on $S$. Let $x$ be a value from the range of $X$. The probability of $x$, denoted by $Pr(X=x)$ is the sum of the probabilities of all outcomes $s$ of $S$ such that $X(s)=x$.
\end{definition}

Example 1 \ Let $S$ be the set of all binary sequences of size $n=3$ bits. \\
Let $X(s)$ be the number of 1 bits in a binary string $s \in S$. \\
Here the range of $X$ denoted $r(X)$ is $\{0,1,2,3\}$.

\bigskip
$\Pr( X = 0 )$ =                 % s = 000

\medskip
$\Pr( X = 1)$ =                  % s = 100 or 010 or 001

\medskip
$\Pr( X = 2 )$ =                 % s = 110 or 101 or 011 

\medskip
$\Pr( X = 3 )$ =                 % s = 111

\bigskip
$\Pr( X = k )$ =

\vspace{2cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{definition}
The \textbf{expected value} of a random variable $X$ on a sample 
space $S$ is defined by
$$E(X) = \sum_{x \in r(X)} xPr(X=x) = \sum_{s\in S} X(s)Pr(s).$$
\end{definition}

\bigskip
Example 1 (cont.) \quad
\begin{tabular}{c|ccccc}
$x$       &  0   &   1  &  2   &  3  \\ \hline
$Pr(X=x)$ & $\ds \frac{1}{8}$ & $\ds \frac{3}{8}$ & $\ds \frac{3}{8}$ & $\ds \frac{1}{8}$ 
\end{tabular}

\bigskip
\medskip
{ $\ds E[X] = \sum_{x \in r(X)} x Pr(X=x) =$ }

\vspace{5cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{theorem}[ Linearity of Expection ]
Let $X$ and $Y$ be two random variables on the same sample space $S$ and $a \in \mathbb{R}$.
Then
\begin{itemize}
\item[(1)] $E(aX) = aE(X)$ and
\item[(2)] $E(X+Y) = E(X) + E(Y)$.
\end{itemize}

\end{theorem}

\bigskip
{\bf Proof}

\vspace{6cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{The bins and balls problem}

Suppose we throw $m$ balls into $n$ bins randomly. \\
Question 1: What is the probability that bin $i$ has $k$ balls?

\vspace{12cm}
% Let $X$ be the number of balls in bin $i$.
% Binomially distributed with $p=1/n$ and $n=m$.
% Pr( X=k ) C(n,k) p^k (1-p)^(n-k) and E(X) = np = m/n
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Question 2: On average, how many bins are empty?

\vspace{8.2cm}
Exercise: On average, how many bins have one ball?
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%
%Exercise: What is the expected number of bins with one ball?
%
%\vspace{12cm}
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{The coupon collectors problem}

Suppose a large bin contains many copies of $n=10$ coupons.
Assuming there are an equal number of each coupon, if we draw coupons at random
from the bin, on average, how many draws will it take to get all $n$ coupons?

\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\large The coupon collectors problem continued.}

\vspace{7.7cm}

Exercise: On average, how many times must you toss a fair coin before you get a head and a tail?

\end{frame}
