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

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

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

\iffalse
\begin{problem} 
Mir's main computer has probability $p$ of failing every hour (assume
that failures occur independently). The main cosmonaut is wondering
how long to expect the main computer to last. Let $T$ be the timestep
at which the main computer fails. Prove that the expected time of
failure is $1/p$.

\solution{ 
%{\em NOTES to TAs (comment out before publishing
%solutions). Write solution on the board. Encourage your students to
%solve this using the usual expectation formula $\expect{R} = \sum
%r\prob{R=r}$. This produces a series that they should be able to
%derive. Point out that the notes shows an alternate way of computing
%mean time to failure.}

Let $R$ be a random variable denoting the timestep at which the first
failure occurs.  This means that if $R=i$, then no failure occurred
for $(i-1)$ steps and then there was a failure at the $i$th step.
So $\prob{R=i} = p(1-p)^{i-1}$.

Using equation~\ref{expsum2} from the appendix, we have the following:

\begin{eqnarray*}
\expect{R} &=& \sum_{r \in \range{R}} r \cdot \pr{R = r}\\
	&=& \sum_{i=0}^\infty ip(1-p)^{i-1}\\
	&=& \frac{p}{1-p}\sum_{i=0}^\infty i(1-p)^i\\
	&=& \frac{p}{(1-p)}\frac{(1-p)}{(1-(1-p))^2}\\
	&=& \frac{p}{p^2}\\
	&=& \frac{1}{p}
\end{eqnarray*}


There is also a solution in the notes which gives an alternate formula
for this expectation but uses a simpler series.  There is often more than one
way to solve a problem about expectations.

}
\end{problem}
\fi

\begin{problem}
What are each of the following quantities when $n$ independent Bernoulli
trials are carried out with probability of success $p_s$?  (Note: at most
you are allowed $n$ trials, not an infinite number of trials)

\begin{problemparts}
\problempart The probability of no failures.
\problempart The probability of at least one failure.
\problempart The probability of at most one failure.
\problempart The expected number of failures in $n$ trials.
\problempart The expected number of trials for the first failure.

\solution{

%{\em NOTES for TAs (comment out before releasing solutions): Get them
%to write answers on the board. Make sure that they are able to defend
%their answers.}

Let $F$ be a random variable equal to the number of failures in $n$
trials.

\begin{eqnarray*}
\prob{F=0}  &=& {p_s}^n \\
\prob{F>0}  &=& 1-\prob{\text{No failure}} = 1-{p_s}^n\\
\prob{F\leq 1} &=& \prob{F=0}+\prob{F=1}\\
            &=& {p_s}^n + n(1-{p_s}){p_s}^{n-1}
\end{eqnarray*}

\begin{eqnarray*}
\expect{F} &=& \sum_{i=0}^{n} i\prob{F=i} \\
           &=& \sum_{i=0}^{n} i \binom{n}{i}(1-{p_s})^i {p_s}^{n-i}\\
           &=& n(1-{p_s})
\end{eqnarray*}

The expectation of a binomial distribution is worth remembering.  But you
can always derive it easily by using the linearity of expectations, \ie by
assigning a random variable $R_j$ to each trial $j$ that has the value 1
if the trial is a success and 0 if not, and then summing those
expectations.  You can verify that you get the same answer.

(e) Let $T$ be a random variable representing the number of trials
before the first failure.  There are several ways to solve this
problem.  One is to calculate the probability that it takes more than
$i$ trials before a failure occurs and use the corresponding
expectation formula. This is similar to the Mean Time to Failure
problem.

\begin{eqnarray*}
\expect{T} &=& \sum_{i=0}^{n} \prob{T>i} \\
           &=& \sum_{i=0}^{n} {p_s}^i\\
           &=& \frac{1-{p_s}^{n+1}}{1-{p_s}}
\end{eqnarray*}

The last line uses the formula for the sum of a geometric series.  Note
that unlike the Mean Time to Failure example, the series is not from 0 to
infinity.

Another method would be to calculate the probability that the first
failure occurs at exactly $i$ trials.  This uses the usual definition
of expectation.
\begin{eqnarray*}
\expect{T} &=& \sum_{i=0}^{n} i \prob{T=i} \\
           &=& \sum_{i=0}^{n} i {p_s}^{i-1} (1 - p_s) \\
           &=& (1-p_s) \sum_{i=0}^{n} i {p_s}^{i-1}
\end{eqnarray*}

We can derive the formula for the series $\sum_{i=0}^{n}ix^{i-1}$ by
differentiating the formula for $\sum_{i=0}^{n}x^i$. The end result
is the same.
}

\end{problemparts}

\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. $E[T] = 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}



% \problemdata     
% {S01-PS10-3}           
% {probability-expectation}              
% {} 		
% {S01-PS10}
% {S01 Karger}

\begin{problem}
\begin{problemparts}
\problempart Suppose that I roll a 4-sided die, a 6-sided die, an
8-sided die, a 10-sided die, a 12-sided die, and a 20-sided die.  What
is the expected number of 6's that come up?  (Assume that all of the
dice are fair.)  

\solution{
  Let $X_i$~be the number of 6's on the $i$-sided die for $i \in
  \{4,6,8,10,12,20\}$. Then the number of 6's on all dice is $X_4 +
  X_6 + X_8 + X_{10} + X_{12} + X_{20}$ and by linearity of expectation
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    \expect{X_4} + \expect{X_6} + \expect{X_8}
    + \expect{X_{10}} + \expect{X_{12}} + \expect{X_{20}}.
  \end{displaymath}
  Since every die has exactly one 6, $\expect{X_i} = 1 / i$, which gives
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    \frac{0}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{10} +
    \frac{1}{12} + \frac{1}{20}
    = \frac{21}{40}\,.
  \end{displaymath}
}

\problempart Suppose that I roll $n$ dice that are 6-sided, fair, and
mutually independent.  What is the expected value of the largest
number that comes up?

\hint You may want to use the ``alternative" formula for expectation:
$\expect{M} = \sum_{i=0}^{\infty} \pr{M > i}$. (This formula is valid
since the random variables involved are non-negative.)

\solution{  
  Let the random variable $M$ be the largest number that comes up. To
  use the identity $\expect{M} = \sum_{i=0}^{\infty} \pr{M > i}$ we
  must compute the probability of the event $M > i$; that is, the
  event that some die shows a value greater than $i$.
  \begin{displaymath}
    \pr{M > i}
    = 1 - \pr{\text{every die $\leq i$}}
    = 1 - \prod_{k=1}^n \pr{\text{$k$th die $\leq i$}}
    = 1 - (i/6)^n,
  \end{displaymath}
  where the second equality holds since the dice are independent. Therefore,
  \begin{displaymath}
    \expect{M}
    = \sum_{i=0}^5 \Pr(M > i)
    = \sum_{i=0}^5 1 - (i/6)^n
    = 6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}.
  \end{displaymath}
}
\end{problemparts}
\end{problem}

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

\instatements{

\appendix
\section{Appendix}
\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}
If $R$ has range $\naturals$, then this definition can also be written
as
\begin{equation*}
\expect{R}= \sum_{r \in \naturals} \pr{R > r}
\end{equation*}
{\bf Series:}
\begin{eqnarray*}
\sum_{i=0}^\infty x^i & = & \frac{1}{1-x}, \mbox{ if } \abs{x} < 1\\
\sum_{i=0}^{n} x^i & = & \frac{1-x^{n+1}}{1-x}\\
\sum_{i=1}^{\infty} i x^i & = & \frac{x}{(1-x)^2}\\
\sum_{i=0}^{n} i \binom{n}{i} p^i (1-p)^i & = & np\\
H_n & = & \sum_{j=1}^{n} \frac{1}{j} \sim \ln n
\end{eqnarray*}
}

\end{document}

\problemdata     
{S01-PS10-3}           
{probability-expectation}              
{} 		
{S01-PS10}
{S01 Karger}

\begin{problem}

\problempart Suppose that I roll a 4-sided die, a 6-sided die, an
8-sided die, a 10-sided die, a 12-sided die, and a 20-sided die.  What
is the expected number of 6's that come up?  (Assume that all of the
dice are fair.)  \solution{
  
  Let $X_i$~be the number of 6's on the $i$-sided die for $i \in
  \{4,6,8,10,12,20\}$. Then the number of 6's on all dice is $X_4 +
  X_6 + X_8 + X_{10} + X_{12} + X_{20}$ and by linearity of expectation
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    \expect{X_4} + \expect{X_6} + \expect{X_8}
    + \expect{X_{10}} + \expect{X_{12}} + \expect{X_{20}}.
  \end{displaymath}
  Since every die has exactly one 6, $\expect{X_i} = 1 / i$, which gives
  \begin{displaymath}
    \expect{X_4 + X_6 + X_8 + X_{10} + X_{12} + X_{20}} = 
    \frac{0}{4} + \frac{1}{6} + \frac{1}{8} + \frac{1}{10} +
    \frac{1}{12} + \frac{1}{20}
    = \frac{21}{40}\,.
  \end{displaymath}
}

\problempart Suppose that I roll $n$ dice that are 6-sided, fair, and
mutually independent.  What is the expected value of the largest
number that comes up?

\hint You may want to use the ``alternative" formula for expectation:
$\expect{M} = \sum_{i=0}^{\infty} \Pr(M > i)$. (This formula is valid
since the random variables involved are non-negative.)

\solution{  
  Let the random variable $M$ be the largest number that comes up. To
  use the identity $\expect{M} = \sum_{i=0}^{\infty} \Pr(M > i)$ we
  must compute the probability of the event $M > i$; that is, the
  event that some die shows a value greater than $i$.
  \begin{displaymath}
    \Pr(M > i)
    = 1 - \Pr(\text{every die $\leq i$})
    = 1 - \prod_{k=1}^n \Pr(\text{$k$th die $\leq i$})
    = 1 - (i/6)^n,
  \end{displaymath}
  where the second equality holds since the dice are independent. Therefore,
  \begin{displaymath}
    \expect{M}
    = \sum_{i=0}^5 \Pr(M > i)
    = \sum_{i=0}^5 1 - (i/6)^n
    = 6 - \frac{1^n + 2^n + 3^n + 4^n + 5^n}{6^n}\,.
  \end{displaymath}}
