\documentclass[11pt]{article}
%\usepackage{eepic}
\usepackage{psfig}
\usepackage{amsmath}
%\usepackage{graphics}
%\usepackage{eepic}
\input{macros-course}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersect}{\bigcap}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\newcommand{\underdash}{\_}

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\textbf{Solution}: \quad #1}


\begin{document}

\tutn{11}{4/23/99}{April 24, 1999}

\section{Predicting a diamond}

Consider the following game using a standard deck of 52 playing cards: the
dealer shuffles the deck and starts dealing them out one at a time, face
up.  The player is supposed to try to predict when a diamond will appear.
That is, at any time as the cards are being dealt, he is allowed to say
``stop!''.  Then if the next card is a diamond he wins, otherwise he
loses.

What is the best strategy for the player? What is the probability that 
the player wins? 

Since one quarter of the cards are diamonds, it is easy to find a strategy
that wins one quarter of the time---just predict that the first card is a
diamond.  But is it possible to do better by waiting and observing what
has happened?  For example, we might wait until the number of undealt
diamonds is disproportinately large before predicting that the next card
is a diamond.  Of course this may never happen for some arrangements of
the deck, and in such cases this strategy might do poorly.

We will argue that no strategy the player might use can make any
difference -- the probability is always the same, no matter how the player
chooses!  Actually, this is not quite true: a player who \emph{never} says
``stop'' can manage to lose always.  But we will not count this as a
genuine strategy of play: the player is required to say ``stop'' on the
last card if he hasn't done so before.  To verify that every strategy wins
with probability $1/4$, we prove a more general result:

\begin{theorem}
In the ``predict a diamond'' game, played with a deck of $n$ cards
containing $d$ diamonds, the probability that the player correctly
predicts a diamond is exactly ${d/n}$, no matter what strategy the player
uses.
\end{theorem}

\begin{proof}
By induction on $n$.

\emph{Base} $n=1$: There is only one card and one strategy, which is to
look at that card.  If $d = 1$, the player wins, so the probability of
winning is $1 = 1/1 = d/n$, as required.  If $d = 0$, the player loses, so
the probability of winning is $0 = 0/1 = d/n$, as required.

\emph{Inductive step:} We must prove the statement for $(n+1)$-card decks,
assuming it holds for all $n$-card decks.  So consider an $(n+1)$-card
deck with $d$ diamonds.  We must show that the probability that the player
wins is $d/(n+1)$.

\emph{Case 1}: The player's strategy is to stop at the first card.  So the
player wins exactly if the first card is a diamond.  Since this card is
chosen randomly with uniform probability, and there are $d$ out of $n+1$
diamonds in the deck, the probability of a diamond on the first card is $d
/ (n+1)$, so this strategy has exactly this probability of winning, as
required.

Case 2: The player's strategy is to look at the first card and proceed
from there.

Now the probability that the first card is a diamond is $d / (n+1)$.  If
it is a diamond, then the player is in a situation identical to playing a
reduced game with $n$ cards, of which $d-1$ are diamonds.  On the other
hand, if it is not a diamond, then the player is faced with a different
reduced game, this time with $n$ cards and $d$ diamonds.  By induction, we
know that whatever strategy the player uses, the probability that he wins
the reduced game after an initial diamond is $(d-1) / n$, while after an
initial non-diamond it is $d / n$.

So the probability of winning can be calculated straightforwardly using
conditional probabilities and products:
\begin{eqnarray*}
\prob{\mbox{player wins}} & = & \prob{\mbox{player wins} \mid \mbox{diamond first}}
                                \prob{\mbox{diamond first}}\\
          & & +                 \prob{\mbox{player wins} \mid \mbox{not diamond first}}
                                \prob{\mbox{not diamond first}}\\
 & = & \frac{d-1}{n} \cdot \frac{d}{n+1}  + \frac{d}{n} (1 - \frac{d}{n+1})\\
 & = & \frac{(d - 1) d + d(n+1) - d^2}{n(n+1)}\\
 & = & \frac{dn}{n(n+1)} =  \frac{d}{n+1}
\end{eqnarray*}
as required.
\end{proof}


\section{Independence facts}

\begin{lemma}
If events $A$ and $B$ are independent, then $A$ and $\bar{B}$ are also
independent.
\end{lemma}
\begin{proof}
\[\begin{array}{rclr}
\prob{A \intersect \bar{B}} & = & \prob{A} - \prob{A \intersect B}
             &\mbox{[from lecture]}\\
& = & \prob{A} - \prob{A}\prob{B} & \mbox{[because $A$ and $B$ are independent]}\\
& = & \prob{A}(1-\prob{B})\\
& = & \prob{A}\prob{\bar{B}})
\end{array}\]
\end{proof}

Like all such probabilistic identities, this lemma holds for conditional
probabilities as well.  That is, say that $A$ and $B$ are independent
\emph{given} $C$ when:
\[
\prob{A \intersect B \mid C} = \prob{A \mid C}\prob{B \mid C}.
\]
Now we can conclude that
\begin{theorem} \label{th:bar-ind}
If $A$ and $B$ are independent given $C$, then $A$ and $\bar{B}$ are also
independent given $C$.
\end{theorem}

\section{Whom do you trust?}\label{TA}

There is a course---not 6.042, naturally---in which $10 \%$ of the
assigned problems contain errors.  If you ask a TA whether a problem has
an error, then he or she will answer correctly $80\%$ of the time.  This
$80 \%$ accuracy holds regardless of whether or not a problem has an
error.  Likewise when you ask a lecturer, but with only $75 \%$ accuracy.

Now suppose you have doubts about a problem and ask a TA about it, and
he/she tells you that the problem has an error.  To double-check, you ask
a lecturer, who says that the problem is correct.  Now what is the
probability that there is an error?  In particular, is this probability
greater than the initial probability of $10 \%$?  It is not too hard to
answer these questions if we make the assumption that \emph{the
correctness of the lecturers' answer and the TA's answer are independent
of each other, regardless of whether there is an error}.\footnote{This
assumption is questionable: by and large, we would expect the lecturer and
the TA's to spot the same glaring errors and to be fooled by the same
subtle ones.}

We formulate this as an experiment of choosing one problem randomly and
asking a particular TA and lecturer about it.  Define the following events:
\begin{eqnarray*}
E & ::= & \mbox{``the problem has an error,''}\\
T & ::= & \mbox{``the TA says the problem has an error,''}\\
L & ::= & \mbox{``the lecturer says the problem has an error.''}
\end{eqnarray*}
The assumptions above tell us:
\begin{eqnarray*}
\prob{E}        & = & \frac{10}{100} = \frac{1}{10},\\ 
\prob{T \mid E} & = & \prob{\bar{T} \mid \bar{E}} = \frac{80}{100} = \frac{4}{5},\\
\prob{L \mid E} & = & \prob{\bar{L} \mid \bar{E}} = \frac{75}{100} = \frac{3}{4},
\end{eqnarray*}
$T$ and $L$ are independent given $E$, and also $\bar{T}$ and $\bar{L}$
are independent given $\bar{E}$.

\iffalse
IN THE FUTURE, MAKE THE REST A TEAM PROBLEM
\fi

We want to compute $\prob{E \mid T \cap \bar{L}}$.
We use Bayes' rule:
\begin{equation}\label{eq:B1}
\prob{E \mid T \cap \bar{L}}
    = \prob{E} \frac{\prob{T\cap \bar{L} \mid E}}{\prob{T\cap \bar{L}}}.
\end{equation}

The independence assumptions and Theorem~\ref{th:bar-ind} imply that: 
\begin{eqnarray*}
\prob{T \cap \bar{L} \mid E} & = & \prob{T \mid E} \prob{\bar{L} \mid E}
     = \frac{4}{5} (1 - \frac{3}{4}) = \frac{1}{5},\\
\prob{T \cap \bar{L}\mid \bar{E}} & = & \prob{T \mid \bar{E}}
      \prob{\bar{L} \mid \bar{E}}
        =  (1 - \frac{4}{5}) \frac{3}{4} = \frac{3}{20},\\
\prob{T \cap \bar{L}} & = &
         \prob{T \cap \bar{L} \mid E}       \prob{E} + 
         \prob{T \cap \bar{L} \mid \bar{E}} \prob{\bar{E}} \\
 & = & \frac{1}{5} \cdot \frac{1}{10} + \frac{3}{20}(1 - \frac{1}{10}) = \frac{31}{200}.
\end{eqnarray*}

Substituting these values in equation~(\ref{eq:B1}) we get:
\[
\prob{E \mid T \cap \bar{L}} = \frac{1}{10} \cdot \frac{1/5}{31/200} \approx 0.129.
\]
Thus, the contradictory information has increased the probability that
there is an error from $10 \%$ to almost $13 \%$.


\section{Team Problems}

\begin{problems}

\problem

Consider the scenario of lecturers and TA's: there is a $10 \%$
chance that an error will have crept into an assigned problem in a course.
The TA will correctly confirm or deny the presence of an error $80 \%$ of
the time.  This $80 \%$ accuracy holds regardless of whether or not a
problem has an error.  Likewise for the lecturer, but with only $75 \%$
accuracy.  We assume that the accuracy of the lecturer's answer and that
of the TA's answer are independent of each other, regardless of whether
there is an error in the problem.


\bparts

\iffalse
FOR THE FUTURE, SWAP THE TWO PARTS BELOW.  THIS WILL PUT THE VARIANT OF
SECTION 1 FIRST.
\fi

\ppart Is the event that ``the TA says that there is an error'',
independent of the event that ``the lecturer says that there is an
error''?

\solution{The answer is no.  Because the TA is usually right, when the TA
says that the problem has an error, the likelihood that there really is an
error is increased.  But the lecturer is also usually right, so increasing
the likelihood of there \emph{being} an error also increases the
likelihood that the lecturer will \emph{report} an error.

We will really verify this informal argument by actually calculating the
probability of each if these events and their conjunction, and observing
that the probability that the two events occur is different from the
product of the probabilities.  Let events $E,T,L$ be as above.

\begin{eqnarray*}
\prob{T} & = & \prob{T \cap E} + \prob{T \cap \bar{E}}\\
 & = & \prob{T \mid E} \prob{E}  + \prob{T \mid \bar{E}} \prob{\bar{E}}\\
 & = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})
 (1 - \frac{1}{10}) = \frac{13}{50},\\
& & \\
\prob{L} & = & \prob{L \cap E} + \prob{L \cap \bar{E}}\\
  & = & \frac{3}{4} \frac{1}{10} + (1 -\frac{3}{4})(1 - \frac{1}{10}) = \frac{3}{10},\\
& & \\
\prob{L \cap T} & = & \prob{L \cap T \cap E} + \prob{L \cap T \cap \bar{E}} \\
& = & \prob{L \cap T \mid  E} \prob{E} + \prob{L \cap T \mid  \bar E} \prob{\bar E}\\
& = & \prob{L \mid E}      \prob{T \mid  E}       \prob{E} + 
      \prob{L \mid \bar E} \prob{T \mid  \bar{E}} \prob{\bar E}\\
& = & \frac{3}{4} \cdot \frac{4}{5} \cdot \frac{1}{10}
        + (1 - \frac{3}{4}) (1 - \frac{4}{5}) \cdot (1 - \frac{1}{10}) = \frac{105}{1000} = 0.105,
\end{eqnarray*}
which is higher than 
\[
\prob{L}\prob{T} = \frac{3}{10} \cdot \frac{13}{50} = .078.
\]
}

\ppart Suppose that the situation in Section~\ref{TA} is reversed: the TA
says the problem does not contain an error, but the lecturer says that it
does.  Now what is the probability of error?  Is it lower or higher than
before?  Conceivably it will be lower since you trust the TA better than
the lecturer, but will it be lower than the original $10\%$?

\solution{The calculation is similar this time.
Now we want to calculate
\[
\prob{E \mid \bar{T} \cap  L}.
\]
By Bayes' rule
\begin{equation}\label{eq:B2}
 \prob{E \mid \bar T \cap L} = \prob{E}
 {\prob{\bar T\cap {L} \mid E}\over
 \prob{\bar T\cap {L}}}.
\end{equation}
By the independence assumptions, we have:
\begin{eqnarray*}
\prob{\bar{T} \cap L \mid E} & = & \prob{\bar{T} \mid E} \prob{L \mid E}
     = \frac{1}{5}\frac{3}{4}  = \frac{3}{20},\\
\prob{\bar{T} \cap L \mid \bar{E}} & = &
         \prob{\bar{T} \mid \bar{E}} \prob{L \mid \bar{E}}
     = \frac{4}{5} \cdot \frac{1}{4} = \frac{1}{5},\\
\prob{\bar{T} \cap L} & = & \prob{\bar{T} \cap L \mid E}      \prob{E} + 
                          \prob{\bar{T} \cap L \mid \bar{E}} \prob{\bar{E}}\\
 & = & \frac{3}{20} \cdot \frac{1}{10} + \frac{1}{5} \cdot \frac{9}{10}
       = \frac{39}{200}.
\end{eqnarray*}

Substituting these values in equation~(\ref{eq:B2}), we get
\[
\prob{E \mid T \intersect \bar{L}} = \frac{1}{10} \cdot \frac{3/20}{39/200} =
\frac{1}{13} \approx 0.077.
\]

So this time the contradictory information has decreased the probability
of an error from $10 \%$ to about $7.7 \%$.

The calculations here and earlier in Section~\ref{TA} confirm the common
sense rule that when two people make contradictory statements, you should
be influenced more by the most ``authoritative'' person---the one who is
right more often.  But note that this does not mean that you should {\em
believe} in what the most authoritative person says.  In the first
calculation, the TA's opinion raises the probability of an error from $10
\%$ to $13\%$, still way below $50 \%$!}

\eparts

\problem Suppose you repeatedly flip a fair coin.
\bparts

\iffalse
ALSO FOR THE FUTURE, SWAP THE TWO PARTS BELOW TO PUT EASIER ONE FIRST.
\fi

\ppart What is the probability you see the sequence \texttt{HTT} before
you see the sequence \texttt{HHT}, where \texttt{H} is a head and
\texttt{T} is a tail?  \hint First evaluate the conditional probability of
seeing \texttt{HHT} before \texttt{HTT} given that that the first toss
comes up \texttt{H}. Then show that this is the same as the required
probability.  $1/2$ is not the answer!

\solution{

Let $A$ be the event that we see the sequence \texttt{HHT} before we see
\texttt{HTT}.  Our first observation is the following:

\begin{lemma}
\[
\prob{A} = \prob{A \mid H}
\]
\end{lemma}

That is, the probability of seeing \texttt{HHT} before \texttt{HTT} is the
same as the probability of seeing \texttt{HHT} before \texttt{HTT} given
the event, $H$, that we have seen a head on the first roll.


\begin{proof}
\begin{eqnarray*}
\prob{A} & = & \prob{A \cap H} + \prob{A \cap T}\\
   & = & \prob{A \mid H} \prob{H} + \prob{A \mid T} \prob{T}.
\end{eqnarray*}
Now
\[
\prob{A \mid T} = \prob{A}
\]
since for any outcome, $s$, of coin tosses
$Ts \in A$ iff $s \in A$.  Therefore
\[
\frac{1}{2}\prob{A} = \frac{1}{2}\prob{A \mid H}.
\]
\end{proof}

To evaluate $\prob{A \mid H}$ consider the outcomes of the second and
third coin tosses.  Let $\underdash TH$ denote the event that the second
toss was a tail and the third toss was a head, and similarly for
$\underdash HT$, $\underdash HH$, and $\underdash TT$.

Now
\begin{eqnarray*}
\prob{H} \prob{A \cap \underdash TH \mid H} & = & \prob{A \cap HTH}\\
 & = & \prob{A \mid HTH} \prob{HTH},
\end{eqnarray*}
so
\[
\prob{A \cap \underdash TH \mid H}  =  \frac{1}{4} \prob{A \mid HTH}
\]
and similarly for the other outcomes.  Now, using the sum rule for
conditional probabilities (as in last week's tutorial),
\begin{eqnarray}
\prob{A \mid H} & =  & \prob{A \cap \underdash HH \mid H} + \prob{A \cap
                       \underdash HT \mid H} +
                       \prob{A \cap \underdash TH \mid H} + \prob{A \cap
                       \underdash TT \mid H}
                       \nonumber \\
 & =  & \frac{1}{4}(\prob{A \mid HHH} + \prob{A \mid HHT}
       + \prob{A \mid HTH} + \prob{A \mid HTT})
                       \nonumber \\
 & =  & \frac{1}{4}(\prob{A \mid HHH} + 1 + \prob{A \mid HTH} + 0) \label{eq:A|H}
\end{eqnarray}

Next we evaluate the terms in expression~(\ref{eq:A|H}):
\begin{lemma}
\[\prob{A \mid HHH} = 1.\]
\end{lemma}

\begin{proof}
If we ever see a \texttt{T} in the remaining flips, then \texttt{HHT}
occurs before \texttt{HTT}.  The probability of never seeing a \texttt{T}
is $\lim_{n \rightarrow \infty} 2^{-n} = 0$.  Hence we see a
\texttt{T} with probability 1.
\end{proof}

\begin{lemma}
\[
\prob{A \mid HTH} = \prob{A \mid H}.
\]
\end{lemma}
\begin{proof}
For any string of outcomes $s$ of coin tosses,
$\texttt{HTH}s \in A$ iff $\texttt{H}s \in A$.
\end{proof}

Now substituting into~(\ref{eq:A|H}) yields,
\[
\prob{A \mid H} = \frac{1}{4}(1 + 1 + \prob{A \mid H}).
\]
So
\[
\prob{A \mid H} =  \frac{2}{3}.
\]
}

\ppart
If you repeatedly flip a fair coin as above, what is the probability that
you see the sequence \texttt{HHT} before you see the sequence
\texttt{TTH}?  \hint There is an easier way to solve this part than the
previous one.

\solution{ In this case the answer is $1/2$.  The proof is by a bijection
argument on the sample space.  Let $A$ denote the event that you see
\texttt{HHT} before \texttt{TTH}, and $B$ denote the event that you see
\texttt{TTH} before \texttt{HHT}.  The sample points in $A$ will be the finite
sequences of tosses ending with \texttt{HHT} and not containing
\texttt{TTH}.  Likewise for $B$.

We will define a bijection, $g:A \to B$, so that the probability of $g(s)$
is equal to the probability of $s$ for every sequence, $s$, of tosses.

The bijection is quite simple.  For any sequence $s$ of tosses, define
$\bar{s}$ to be the sequence gotten by reversing the outcome of each toss
in $s$.  For example, $\overline{\texttt{HTHH}} = \texttt{THTT}$.  Define
\[
g(s) ::= \bar{s}.
\]

Clearly
\[
\prob{g(s)} = 2^{- \mbox{length}(s)} = \prob{s}
\]
because $g(s)$ has the same length as $s$, and heads and tails are equally
likely.  Fairness is a critical assumption here; the argument below
will not work for biased coins.

Now we confirm that $g$ defines a bijection from $A$ to $B$.  Since $g$ is
obviously an injection on sequences of tosses, we need only show that
$g(a) \in B$ for every $a \in A$, and that $g$ maps $A$ \emph{onto} $B$.
This follows because $\overline{\texttt{HHT}} = \texttt{TTH}$ and
$\overline{\texttt{TTH}} = \texttt{HHT}$.  So \texttt{HHT} precedes
\texttt{TTH} in $s$ iff $\texttt{TTH}$ precedes $\texttt{HHT}$ in
$\bar{s}$.  This means $a \in A$ iff $g(a) \in B$.  Also, $b \in B$ iff
$\bar{b} \in A$, so $g$ maps $A$ \emph{onto} $B$, because if $b \in B$,
then $g(a) = b$ where $a = \bar{b} \in A$.

Hence,
\begin{eqnarray}
\prob{A} & = & \sum_{a \in A} \prob{a} \nonumber \\
 & = & \sum_{a\in A} \prob{g(a)} \nonumber\\
 & = & \sum_{b \in B} \prob{b} \label{keystep} \\
 & = & \prob{B} \nonumber
\end{eqnarray}
Step~(\ref{keystep}) is valid by the bijection property with $b = g(a)$.

We have only to show that $\prob{A \cup B} = 1$ in order to complete the
proof that
\[
\prob{A} = \prob{B} = \frac{1}{2}.
\]

But $\prob{A \cup B} = 1$ because there are only six sample points not in
$A \union B$, and each of these points has zero probability.  The six
points are the four infinite sequences in which every coin toss after he
first is the same, namely,
\begin{center}
\texttt{HH}\dots,
\texttt{TT}\dots,
\texttt{HTT}\dots,
\texttt{THH}\dots,
\end{center}
and the two additional sequences in which heads and tails always
alternate, namely,
\begin{center}
\texttt{HTHTHT}\dots,
\texttt{THTHTH}\dots.
\end{center}
But every infinite sequence has probability zero of occurring, so
$\prob{\overline{A \cup B}} = 0$ which implies $\prob{A \cup B} = 1$.}

\eparts

\end{problems}

\end{document}
