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

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

\begin{document}
\inclassproblems{11W}

\begin{problem} An urn contains red and blue colored balls. 
The fraction of red balls is $r$ where $0 \leq r \leq 1$. A gambler
repeatedly pulls a ball at random from the urn. That is, at any point
during succesive pulls, each ball in the urn is equally likely to be
the next one pulled. The gambler puts the ball back into the urn
before making the next pull. He keeps pulling balls until he pulls
\emph{two red balls in a row}. We want to determine the expected
number of pulls the Gambler must make.

We can analyze this using Wald's Theorem. The sequence of pulls by the
Gambler can be regarded as a sequence of \emph{tries}, where the first
try begins with the first ball pulled.  Each try consists of a
sequence of pulled balls continuing until either a blue ball, or two
red balls in a row, are pulled.  For example, if the colors of pulled
balls are RBBBRBRR, then there are five tries which we indicate with
slashes: /RB/B/B/RB/RR/.  Note that each try consists of one or two
consecutive balls.

\begin{problemparts}

\problempart What is the expected length of the $i$th try, assuming
that there are at least $i$ tries?

\solution{Given that there is an $i$th try, it is of length 1 iff it
starts with a blue ball.  It is of length 2 iff it starts with a red
ball.  Hence,
\[\expect{\mbox{length of $i$th try} \mid \mbox{there is an
$i$th try}} = 1\cdot (1-r) + 2 \cdot r = 1 + r.
\]
}

\problempart What is the expected number of tries?

\solution{A series of tries ends iff only the last try consists of two
reds. We know from lecture that the ``mean time to failure'' is the
reciprocal of the probability of failure, so $\expect{\mbox{num
tries}}$ is the $1/\pr{\mbox{2 reds}}= 1/r^2$.}

\problempart What is the expected number of pulls the Gambler makes?

\solution{By Wald's Theorem we can just multiple the expected length
of the try by the the expected number of tries.}
\end{problemparts}
\end{problem}

\begin{problem}
What are each of the following quantities when $n$ independent
Bernoulli trials are carried out with probability of success $p_s$?

\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
(note: at most you are allowed $n$ trials, not an infinite number of trials)
\end{problemparts}

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

It is worthwhile to remember the expectation of a binomial
distribution. But you can always derive it easily by using the
linearity of expectations, i.e. 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 is assuming that this is 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} i x^{i-1}$ by
differentiating the formula for $\sum_{i=0}^{n} x^i$. The end result
is the same.
}
\end{problem}

\begin{problem} 
Compute the expected value for each of the following random variables.
(Assume that all dice are fair and six-sided and that dice rolls are
mutually independent.)

\begin{problemparts}
\problempart The sum of the rolls of three dice.

\solution{
The expected value of one die roll is
\begin{eqnarray*}
1 \cdot \frac{1}{6} +
2 \cdot \frac{1}{6} +
3 \cdot \frac{1}{6} +
4 \cdot \frac{1}{6} +
5 \cdot \frac{1}{6} +
6 \cdot \frac{1}{6}
        & = & \frac{7}{2}.
\end{eqnarray*}

By linearity of expectation, the sum three rolls is
\begin{eqnarray*}
\frac{7}{2} + \frac{7}{2} + \frac{7}{2} & = & \frac{21}{2}.
\end{eqnarray*}
}
\problempart The product of the rolls of three dice.

\solution{For independent random variables, the expectation of the
product is the product of the expectations.  Therefore, the expected
product is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} \cdot \frac{7}{2} & = & \frac{343}{8}.
\end{eqnarray*}
}

\problempart The sum of the rolls of a number of dice that is given by
the roll of a single die.  (For example, if you roll a 3 on the single
die, then you take the sum of 3 dice rolls; if you roll a 5 on the
single die, then you take the sum of 5 dice rolls.)

\solution{By Wald's Theorem, the answer is the expected number of dice
rolled multiplied by the expected roll of one die, which is
\begin{eqnarray*}
\frac{7}{2} \cdot \frac{7}{2} & = & \frac{49}{4}.
\end{eqnarray*}
}

\problempart Suppose now that the dice rolls are not guaranteed to be
mutually independent.  Which of your answers above must still be
correct?

\solution{The first answer remains valid because linearity of
expectation does not require independence.  Neither of the remaining
answers is necessarily correct, however; both make use of
independence.}
\end{problemparts}
\end{problem}

\begin{problem} What is wrong in Herbert Simon's analysis in ``The
Architecture of Complexity''?

\solution{Waiting to hear from you...}

\end{problem}

\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}
%, \mbox{ if } \abs{x} < 1 
\\
\sum_{i=0}^{n} i {n \choose i} p^i (1-p)^i &=& np
\end{eqnarray}

\end{document}



