\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}

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


\begin{document}

\tutprobn{11}{4/23/99}{April 22, 1999}

\iffalse
SEE HANDOUT 53, WHICH HAS AN IMPROVED VERSION OF ALL THE EXAMPLE AND
PROBLEMS BELOW.
\fi

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

Suppose that, in a course (not 6.042, naturally), $10\%$ of the problems
on problem sets contain errors.  If you ask a TA whether a problem has an
error, he or she will answer correctly $80\%$ of the time.  But if you ask
a lecturer, he/she will answer correctly $75\%$ of the time.  Making the
(unrealistic) assumption that \emph{the correctness of the lecturers'
answers and that of the TAs' answers are independent of each other,
regardless of whether there is an error}.

Now suppose you have a doubt 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\%$?

We formulate this as an experiment of choosing one problem randomly and
asking a particular TA and lecturer about it.  Let $E$ be the event ``the
problem has an error'', $T$ be the event ``the TA says the problem has an
error'', and $L$ be the event ``the lecturer says the problem has an
error''.

The assumptions above tell us:
\begin{eqnarray*}
\prob{E} & = & 10\%\\ 
\prob{T \mid E} & = & \prob{\bar{T} \mid \bar{E}} =  80\%\\
\prob{L \mid E} & = & \prob{\bar{L} \mid \bar{E}} = 75\%\\
\prob{T \cap L \mid  E} & = & \prob{T \mid  E} \prob{L\mid E}, \mbox{ and}\\
\prob{T \cap L \mid  \bar{E}} & = & \prob{T \mid  \bar{E}}\prob{L\mid \bar{E}}.
\end{eqnarray*}

We want to compute $\prob{E \mid T \cap \bar{L}}$.
We use Bayes' rule:
\begin{equation}\label{eq:p4b}
 \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 imply that: 
$\prob{T \cap \bar{L} \mid E} = \prob{T \mid E} \prob{\bar{L} \mid E}$ 
and 
$\prob{T \cap \bar{L} \mid \bar{E}} = 
 \prob{T \mid \bar{E}} \prob{\bar{L} \mid \bar{E}}$.

Now let's compute the probabilities we need:
$\prob{T\cap \bar{L}\mid E} = \prob{T\mid E}\prob{\bar{L}\mid E} = (8/10)(25/100)=2/10$, \\
$\prob{T\cap \bar{L}\mid \bar{E}} = 
 \prob{T\mid \bar{E}}\prob{\bar{L}\mid \bar{E}}
 = (2/10)(75/100) = 15/100$ \\
and 
\begin{eqnarray*}
 \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}} \\
 &=& (2/10)(1/10) + (15/100)(9/10) \\
 &=&  \frac {155}{1000} 
\end{eqnarray*}

Substituting these values in equation~\ref{eq:p4b}
we get:
\[
\prob{E\mid T\cap \bar{L}} = \frac{1}{10} \cdot \frac{2/10}{155/1000} =  0.12903
\]
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: a problem on a
problem set has an error with probability $10 \%$, the TA says whether or
not there is an error, answering correctly with probability $80 \%$, and
the lecturer answers correctly with probability $75 \%$.  The correctness
of the lecturers' answers and that of the TAs' answers are independent of
each other, regardless of whether there is an error or not.

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

\solution{The answer is no.  We will show that the probability that the
two events occur is different from the product of the probabilities.  As
above, let $E$ be the event ``the problem has an error''.

The probability of $T$ is 
\begin{eqnarray*}
\prob{T} &=& \prob{T\cap E} + \prob{T\cap \bar{E}} \\
 &=& \frac{80}{ 100}\frac{10}{100}+\frac{20}{ 100}\frac{90}{ 100} \\
 &=& \frac{26}{ 100} = 0.26
\end{eqnarray*}

The probability of $L$ is 

\begin{eqnarray*}
 \prob{L} &=& \prob{L\cap E} + \prob{L\cap \bar{E}} \\
 &=& \frac{75}{100}\frac{10}{100} + \frac{25}{100}\frac{90}{100} \\
 &=& \frac{30}{100} = 0.3
\end{eqnarray*}


The probability of $L \cap T$ is

\begin{eqnarray*}
\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{\bar E}
\prob{T \mid  \bar{E}} \prob{\bar E}\\
 &=& \frac{75}{ 100}\frac{80 }{ 100} \frac{10}{ 100}
        +\frac{25}{100} \frac{20}{100} \frac{90}{100} \\
 &=& \frac{105 }{1000} = 0.105
\end{eqnarray*}

Which is higher than 
\[
\prob{L}\prob{T} = .26 \times .3 = .078
\]
The intuition is that when the TA says that the problem has an error, that
it is more likely to have an error, and therefore the lecturer is more
likely to find the error himself.}

\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 prove
\[
\prob{E \mid \bar{T} \cap  L}.
\]
By Bayes' rule
\begin{equation}\label{eq:p4c}
 \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:
\[\prob{\bar T\cap {L}\mid E} = \prob{\bar T\mid E}\prob{{L}\mid E}\]
and 
\[\prob{\bar T\cap {L}\mid \bar{E}} = 
 \prob{\bar T\mid \bar{E}}\prob{{L}\mid \bar{E}}.\]

Then:
$\prob{\bar T\cap {L}\mid E} = \prob{\bar T\mid E}\prob{{L}\mid E}$ \\
$= (2/10)(75/100)=3/20$, \\
$\prob{\bar T\cap {L}\mid \bar{E}} = 
\prob{\bar T\mid \bar{E}} \prob{{L}\mid \bar{E}}$ \\
$= (8/10)(25/100)=1/5$,
and
\begin{eqnarray*}
 \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}} \\
 &=& (3/20)(1/10) + (1/5)(9/10) \\
 &=&  \frac {195}{1000} 
\end{eqnarray*}

Substituting these values in equation~\ref{eq:p4c}
we get
\[
\prob{E\mid T,\bar{L}} = \frac 1{10} \frac{15/100}{195/1000} \approx
0.076923
\]

So this time, the contradictory information has decreased the probability
of an error from $10\%$ to about $7.7 \%$.  These calculations confirm the
common sense rule that when two people make contradictory statements, we
should be influenced more by what the most ``authoritative'' person (the
one that is more often right) says.  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

\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 HHT before we see 
HTT. Our first observation is the following:

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

That is, the probability of seeing HHT before HTT is the same as
the probability of seeing HHT before HTT given that we have
seen a head (H).
 
\begin{proof}
$$\prob{A} = \prob{A \cap H} + \prob{A \cap T}$$
$$ = \prob{A \mid H} \prob{H} + \prob{A \mid T} \prob{T}$$

Now
$$\prob{A \mid T} = \prob{A}$$
since for any outcome $w$ of coin tosses
$Tw \in A$ iff $w \in A$.  Therefore
$$\frac{1}{2}\prob{A} = \frac{1}{2}\prob{A \mid H}$$
$$\implies \prob{A} = \prob{A \mid H}$$
\end{proof}

To evaluate $\prob{A \mid H}$ 
consider the outcomes of the two coin tosses immediately following the first
head. 
There are four possible outcomes for these two tosses: HH,HT,TH,TT.
From the result in last week's tutorial,
$$\prob{A \mid H} = \prob{A \cap HH \mid H} + \prob{A \cap HT \mid H} + \prob{A \cap TH \mid H} + \prob{A \cap TT \mid H}$$
$$ = \frac{1}{4}(\prob{A \mid HHH} + \prob{A \mid HHT} + \prob{A \mid HTH} + \prob{A \mid HTT})$$
$$ = \frac{1}{4}(\prob{A \mid HHH} + 1 + \prob{A \mid HTH} + 0)$$

Next we evaluate these terms:
\begin{lemma}
$$\prob{A \mid HHH} = 1$$
\end{lemma}
{\em Proof. }
If we ever see a T in the remaining flips, then HHT occurs before
HTT. The probability of never seeing a T is $\lim_{n \rightarrow \infty} \frac{1}{2^n} = 0$. Hence we see a T with probability 1.
\qed

\begin{lemma}
$$\prob{A \mid HTH} = \prob{A \mid H}$$
\end{lemma}

{\em Proof. }
For any string of outcomes $w$ of coin tosses,
$HTHw \in A$ iff $Hw \in A$.
\qed


Substituting in the equation,
$$\prob{A \mid H} = \frac{1}{4}(2+\prob{A\mid H})$$
That is 
$$\frac{3}{4}\prob{A \mid H} = \frac{1}{2}$$
$$\implies \prob{A \mid H} = \frac{2}{3}$$
So $$\prob{A} = \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 HHT
before TTH, and $B$ denote the event that you see TTH before HHT.  We will
define a bijection, $g$, between $A$ and $B$ so that the probability of
$g(w)$ is equal to the probability of $w$.  The bijection is quite simple.
Given a sample point $w \in A$, define $g(w) = \bar{w}$, where $\bar{w}$
is the outcome where every H is replaced by a T and vice versa. For
example $g(HHT) = \overline{HHT} = TTH$.  We first observe that $g:A
\rightarrow B$.  This follows from the fact that HHT precedes TTH in $w$
iff $\overline{HHT} = TTH$ precedes $\overline{TTH} = HHT$ in
$\bar{w}$. And $g$ is onto by the same reasoning.  Since $g$ is clearly an
injection, we can conclude that it is a bijection.

Then we observe that $\prob{w} = \prob{g(w)}$ for any $w$. This is because
$\prob{H} = \prob{T}$ and $g(w)$ has the same length as $w$. (Note: this is
a critical step in probability calculations.  Otherwise, step 2 below
can fail.)
Hence,
\begin{eqnarray}
\prob{A} &=& \sum_{w \in A} \prob{w} \\
&=&\sum_{w\in A} \prob{g(w)}\\
&=&\sum_{w' \in B} \prob{w'}\\
 = \prob{B}
\end{eqnarray}

Step 2 is valid because $g$ preserves the probability, and step 3 is
by the bijection property with $w' = g(w)$.

Finally we have to show that $\prob{A \cup B} = 1$. This follows
from the fact that 
$$\overline{A \cup B} = \{HHH\ldots, TTT\ldots, HTTT\ldots, THHH\ldots\}$$
Each of these strings has probability $0$ of occuring. 

Hence,
$$\prob{\overline{A \cup B}} = 0 \implies \prob{A \cup B} = 1$$
Since $A$ and $B$ are disjoint, this means that $\prob{A} + \prob{B} = 1$ 
and hence $\prob{A} = \frac{1}{2}$.
}

\eparts


\end{problems}

\end{document}

