\documentclass[12pt]{article}
\input{macros-course}

%%\showsolutionstrue
\askaboutsolutions

\begin{document}

\ifshowsolutions
  \tutsol{11.5}{November 21, 2001}{\stamp}
\else
  \tutprobn{11.5}{November 21, 2001}{\stamp}
\fi

%% TUTORIAL 12: In class tutorial

\begin{problems}


\problem Eight men and seven women, all single, happen randomly to have
purchased single seats in the same 15-seat row of a theater.

\bparts

\ppart
What is the probability that the first two seats contain a marriageable
couple, i.e., a single man next to a single woman?

\solnospace{ 
Here's one way to do it.  There are $\binom{15}{2} = 105$
possible pairs that could occupy the first two seats, but only
$8\cdot7 = 56$ of them are marriageable couples.  So the probability
is $56/105 = 8/15$.
}

\ppart What is the expected number of pairs of adjacent seats which
contain marriageable couples?  (For example, if the sequence of men and
women in the seats is
\begin{center}
MMMWMMMMWWWWWWM,
\end{center}
then there are four possible couples sitting in the pairs of adjacent
seats that start at the 3rd, 4th, 7th and 14th seats, respectively.)

\solnospace{The approach that we are going to use is to assign an
indicator random variable (i.e. value 0 or 1) to each event that we
want to count, and then use the expectation of sum formula to compute
the expected number of events that occur.

Let the random variable S be the number of pairs of seats
containing a marriageble couple; we want to find $\expect{S}$.  We can
solve this problem by introducing an indicator random variable $S_i$,
where $S_i = 1$ if there is a marriageable couple in seats $i$ and
$i+1$, and $S_i = 0$ otherwise.  So we have $S = \sum_{i=1}^{14} S_i$.

Since each seat is like any other, the probability that seats $i$ and
$i+1$ contain a marriageable couple is the same as in the first
part, $8/15$.  Thus
\[
\expect{S_i} = 1\cdot\Pr(S_i=1) + 0\cdot\Pr(S_i=0) = \frac{8}{15}.
\]
Finally, because expectation is linear,
\[
\expect{S} =  \sum_{i=1}^{14} \expect{S_i}  =  14\cdot \frac{8}{15}.
\]

Note that this approach works despite the fact that the indicator random
variables $S_i$ are not independent.  That's the beauty of linearity of
expectation!

}

\problempart Use a similar approach to 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 chosen (by a higher force)
independently.} 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$)?

\solnospace{

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)$
}

\eparts

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

\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 before the first failure

\solnospace{

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. This is also explained in detail in
\href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l12.pdf}
{Lecture Notes 12} Section 7.5.

(e) Let $T$ be a random variable representing the number of trials before
the first failure. The best way to solve this sort of problem is to
calculate the probability that it takes more than $k$ 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.
}

\problem 

\bparts

\ppart Suppose we flip a fair coin until two heads in a row come up.  What
is the expected number, $F$, of flips we perform?  

\hint Let
$F_{\text{T}}$ be the expected number of further flips until two heads
comes up, given that the previous flip was T, and likewise let
$F_{\text{H}}$ be the expected number of further flips until two heads
comes up given that the previous flip was H.  Argue that $F_{\text{T}}$
will equal 1 plus the average of $F_{\text{T}}$ and $F_{\text{H}}$.

\solnospace{Clearly $F=F_{\text{T}}$.  Assuming the hint
\[
F_{\text{T}} = 1 + \frac{F_{\text{T}}+ F_{\text{H}}}{2}.
\]
Similarly,
\[
F_{\text{H}} = 1 + \frac{F_{\text{T}}+ 0}{2}.
\]
Solving for $F_{\text{T}}$ yields $F=6$.
}

\ppart Suppose we flip a fair coin until a head followed by a tail come
up.  What is the expected number, $G$, of flips we perform?

\solnospace{Clearly $G=G_{\text{T}}$.  As above
\begin{eqnarray*}
G_{\text{T}} &=& 1 + \frac{G_{\text{T}}+ G_{\text{H}}}{2},\\
G_{\text{H}} &=& 1 + \frac{0+G_{\text{H}}}{2}.
\end{eqnarray*}
So $G=G_{\text{T}}=4$.
}

\ppart Suppose we now play a game: flip a fair coin until either HH or HT
first occurs.  You win if HT comes up first, lose if HH comes up first.
What odds should you offer an opponent to make this a fair game?

\solnospace{Even money odds.  Although the expected time for HH is larger
than for HT, the game of waiting for one or the other to come up first is
fair!

To prove this, let W be the probability of winning.  Clearly,
\[
W = (1/2)\prob{W \mid \text{first roll is }T} + (1/2)\prob{W \mid \text{first
roll is }
H} = (1/2)W + (1/2)(1/2)
\]
so $W = 1/2$.
}

\eparts

\end{problems}

\end{document}
