\documentclass[twoside,12pt]{article}

\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\topmargin}{0 in}
\setlength{\headheight}{0.25 in}
\setlength{\headsep}{0.25 in}
\setlength{\evensidemargin}{0 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\parskip}{1ex}

\newcommand{\heading}[1]{\vspace{3ex} {\Large {\em #1}}}
\newcommand{\subheading}[1]{\vspace{3ex} {\large {\em #1}}}

\usepackage{graphics}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}

\newenvironment{comment}[1]{}{}
\newenvironment{proof}{\noindent {\em Proof.}}{$\Box$}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\pr}[1]{\Pr\{#1\}}

\begin{document}

\begin{center}
{\Large Notes for Tutorial 2} \\
6.042 - February 14 and 18, 2003 \\
\bigskip
\end{center}

% Half the tutorial sections were unable to meet because of a snowstorm.
% So we're distributing notes for this tutorial only.

There are four topics.

\begin{itemize}
\item Proving set identities.
\item Generalized Monty Hall
\item The basis for tree diagrams.
\item Bayes' rule
\end{itemize}

\section{Proving Set Identities}

In the homework, we gave you the following problem:

Let $A$, $B$, and $C$ be sets.  Assume that $A \cap B \cap C =
\emptyset$.  Prove that:

\begin{eqnarray*}
A \cup B \cup C = (A - B) \cup (B - C) \cup (C - A)
\end{eqnarray*}

\noindent We didn't tell you how to approach this problem, and we got
a lot of different answers!

\subsection{Venn Diagrams and the Meaning of ``Proof''}

One common approach was to use Venn diagrams as shown in
Figure~\ref{fig:tut2-venn}.  You draw three overlapping circles and
shade in the regions covered by the expression on the left.  You draw
three more circles and shade in the regions covered by the expression
on the right.  Then you note that these diagrams differ only in the
center region, which is empty by assumption.  Therefore, we have
equality!

\begin{figure}[htpb]
\centerline{\resizebox{!}{2.0in}{\includegraphics{tut2-venn.eps}}}
\caption{A Venn Diagram approach to the set identity problem.}
\label{fig:tut2-venn}
\end{figure}

One can argue whether or not a Venn diagram argument constitutes a
proof.  One camp says, ``A proof is a sequence of assertions, each of
which follows from axioms or previous assertions via inference
rules.''  To this camp, a picture is obviously not a proof.  Where are
the axioms?  Where are the rules of inference?  A Venn diagram is just
a bunch of squiggly lines.  There is good reason to distrust proofs
based on pictures: they are often wrong.  There is one famous argument
based on pictures--- Kempe's purported proof of the four-color
theorem--- that was accepted for 11 years before someone pointed out
an error was not evident in the pictures.

Some other mathematicians say that a valid proof has to be {\em
really} formal: reams of mathematical symbols.  English is for poetry,
not for rigorous mathematics.  These people may have a point.  In
certain areas of research, such as the analysis distributed network
protocols, such rigor seems to be essential; time and again, informal
arguments have overlooked quirky special cases, resulting in buggy
protocols.  But in most situations, most mathematicians would say,
``We could translate our proofs into ultra-formal style anytime we
want to, and so our less-formal proofs are valid.  But we don't want
to use so much formalism, because then reading proofs would become so
difficult that the field could not advance.''

On the other hand, some might argue, ``Yes, but we could also
translate a Venn diagram into a formal proof anytime we want to, and
so Venn diagram arguments are valid proofs.  Furthermore, a Venn
diagram is instantly convincing, but a formal proof might require ten
minutes to methodically check.''

You can decide where you stand on the issue of proof formality.  But
this is an introductory course.  We do not take it as a given that you
can translate a Venn diagram into a traditional proof anytime you want
to.  If you're asked to prove a set identity on an exam, a Venn
diagram is great for clarifying your own thinking, but {\em is not
considered a valid proof}.  We want sentences and equations, not
pictures.

\subsection{A Traditional Proof}

The proof of the set identity given below is lifted straight from the
solution set.  The important thing to take away is the method.

Let $S$ and $T$ be sets, and suppose that we want to prove that $S =
T$.  To do this, it is sufficient to show that {\em each set contains
the other}.  Therefore, a proof using this method contains {\em two
parts}: first, we prove $S \subseteq T$ and then we prove $T \subseteq
S$.  Each of these two parts is handled in the same basic way: to
prove that one set is contained in a second set, we take an arbitrary
element of the first set and prove that it is also contained in the
second.  Often this requires quite a bit of case analysis, as in proof
below.

\begin{proof}
We prove the equality by showing that the left set contains the right
set and vice versa.  Let $S$ be the set on the left, $A \cup B \cup
C$, and let $T$ be the set on the right, $(A - B) \cup (B
- C) \cup (C - A)$.  In these terms, our objective is
to prove that $S = T$.

First, we show that $S$ is contained in $T$.  Let $x$ be an element of
$S = A \cup B \cup C$.  There are then six cases:

\begin{itemize}
\item $x \in A, x \not\in B, x \not\in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A - B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B - C$, and so $x \in T$.

\item $x \not\in A, x \not\in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C - A$, and so $x \in T$.

\item $x \in A, x \in B, x \not\in C$: Since $x \in B$ and
$x \not\in C$, we have $x \in B - C$, and so $x \in T$.

\item $x \in A, x \not\in B, x \in C$: Since $x \in A$ and
$x \not\in B$, we have $x \in A - B$, and so $x \in T$.

\item $x \not\in A, x \in B, x \in C$: Since $x \in C$ and
$x \not\in A$, we have $x \in C - A$, and so $x \in T$.
\end{itemize}

\noindent In every case, $x \in T$ as well; therefore, every element
of $S$ is also an element of $T$, and so $S \subseteq T$.  (Note that
the case $x \in A, x \in B, x \in C$ does not exist, since $A \cap B
\cap C = \emptyset$ by assumption.)

Now we show that $T$ is contained in $S$.  Let $x$ be an element of $T
= (A - B) \cup (B - C) \cup (C - A)$.  There
are then three cases:

\begin{itemize}
\item $x \in A - B$:  This implies that $x \in A$, and so $x \in S$.
\item $x \in B - C$:  This implies that $x \in B$, and so $x \in S$.
\item $x \in C - A$:  This implies that $x \in C$, and so $x \in S$.
\end{itemize}

\noindent In every case, $x \in S$ as well; therefore, every element of $T$ is
also an element of $S$, and so $T \subseteq S$.  Since set $S$
contains set $T$ and vice versa, $S$ and $T$ must be the same set;
that is, $S = T$.
\end{proof}

This method for proving two sets equivalent is also described in
Rosen, and you can find an additional example there.

\subsection{Other Methods}

Set identities can be proved in other ways as well.  For example,
Rosen suggests transforming one side into the other using
previously-established set identities.  This is a completely valid
type of proof that you should feel free to use.

Rosen also suggests using ``membership tables''.  They're essentially
a careful, tabular way of presenting a Venn diagram argument.  They
have the advantage that they work equally well with identities
involving more than three sets.  On the other hand, they don't
demonstrate that you know how to write a traditional proof any more
than a Venn diagram does.  So we prefer that you not use table-based
arguments on exams without a supporting explanation.

We'll talk more about what ``proof'' means as the term goes on.  And,
in any case, on quizzes we'll try to be very clear about what is
acceptable as a proof and what is not.  If you're not sure, ask!

\section{Generalized Monty Hall}

In lecture, we played the {\em Let's Make a Deal} game, which works as
follows.  You are shown three doors.  You know there is a prize behind
one door and there are goats behind the other two.  You pick a
door.  To build suspense, Carol always opens a \emph{different} door,
revealing a goat.  You can then stick with your original door or
switch to the other unopened door.  You win whatever is behind the
door you now select.  We showed that you should always switch to the
other door; by doing so, you win the prize with probability
$\frac{2}{3}$.

The game we played in lecture differed from the television game show
in several respects.  On the game show, Monty did not always reveal a
goat and give the contestant the option to switch doors.  Sometimes
the contestant was immediately awarded whatever lay behind the door he
picked initially.

This suggests a new game, which we might call {\em generalized Monty
Hall}.  As before, you are shown three doors.  You know there is a
prize behind one door and there are goats behind the other two.  You
pick a door.  Now, at Monty's discretion, one of two things happens:

\begin{enumerate}

\item Carol opens the door you picked and you win whatever lies behind
it.

\item Carol opens a different door to reveal a goat.  You can then
stick with your original door or switch to the other unopened door.
You win whatever is behind the door you now select.

\end{enumerate}

\noindent Suppose that you are playing this game.  What should you do
in the latter case, where you're given the option to stick with your
current door or to switch to the other?

In order to analyze this problem, let's introduce some variables that
capture the range of possible strategies for Monty and yourself:

\begin{itemize}

\item Let $r$ be the probability that Monty reveals a goat and lets
you switch when your initial guess is {\em right}.

\item Let $w$ be the probability that Monty reveals a goat and lets
you switch when your initial guess is {\em wrong}.

\item Let $p$ be the probability that you switch when given the option
to do so.

\end{itemize}

Now we can compute the probability of the event that you win the game
using a tree diagram.  Since the tree is rather large, we've drawn
only one of the three main subtrees in Figure~\ref{fig:tut2-monty}.
Fortunately, the other two subtrees are symmetric to the first; only
the door numbers are permuted.  Therefore, we can compute the
probability of the event that you win by adding the probabilities of
winning outcomes in the first subtree and multiplying the answer by 3.

\begin{figure}[htpb]
\centerline{\resizebox{!}{3.5in}{\includegraphics{tut2-monty.eps}}}
\caption{A tree diagram for the generalized Monty Hall game.}
\label{fig:tut2-monty}
\end{figure}

From the tree diagram, we have:

\beqn
\pr{\text{you win}}
	& = & 3 \cdot \left(
		\frac{r(1-p)}{18} + \frac{r(1-p)}{18} +
		\frac{1-r}{9} + \frac{wp}{9} + \frac{wp}{9}
		\right) \\
	& = &	\frac{1 + p(2w-r)}{3}
\eeqn

Let's interpret this solution by considering some special cases.

\begin{itemize}

\item If you never switch ($p = 0$), then your probability of winning
is $\frac{1}{3}$, regardless of Monty's strategy.

\item If Monty always gives you the option to switch ($r = w = 1$) and
you always do ($p = 1$), then your probability of winning is
$\frac{2}{3}$.  This is precisely what our analysis in lecture showed.

\item Suppose that you employ the ``switch'' strategy ($p = 1$), but
Monty is trying to make you lose.  Then he can give you the option to
switch only when your initial guess is right ($r = 1, w = 0$).  In
this case, your probability of winning is zero!

\item On the other hand, suppose that you employ the ``switch''
strategy ($p = 1$), but Monty is trying to make you win.  Then he can
give you the option to switch only when your initial guess is wrong
($r = 0, w = 1$).  Then you always win!

\end{itemize}

So what is the solution?  If you're on the game show, what do you do?
By always sticking, you can assure yourself a $1/3$ chance of winning,
regardless of what Monty does.  The rest is psychology; probability
does not give us the answer!

\begin{itemize}

\item If you think Monty is trying to make you lose, never switch.

\item If you think Money trying to help you win, always switch.

\end{itemize}

There are simpler games that come down to psychology in this way.
Suppose I borrow your wallet and count how much money is inside.  Then
I say, ``Want to switch the money in my wallet for the money in your
wallet?!''  If you think I'm out to cheat you, then you should say
``no''.  After all, if I had more money in my wallet, I wouldn't have
offered to switch!  On the other hand, if you think I'm a nice guy
trying to give you a leg up in this harsh world, then you should say
``yes''.  If you want to be conservative and avoid mind games, stick
with your own wallet.  Probability doesn't give us a full answer in
this simple game in the same sense that it doesn't tell us the whole
story in Monty Hall.

\section{Tree Diagrams and Conditional Probability}

We talked some big talk about how Venn diagrams are just a bunch of
squiggles and how we want mathematics not pictures.  This is somewhat
awkward, because we've been using tree diagrams--- mere pictures!---
to work out probability problems all along.  In particular, we've
asserted that the probability of an outcome is the product of the edge
probabilities on the path from the root to that outcome.  But why
should this be true?  For example, in Figure~\ref{fig:tut2-monty}, we
concluded that the probability of the outcome that the prize is behind
door 1, your initial guess is door 2, door 3 is revealed, and then you
switch is equal to the product of edge probabilities on the
highlighted path:

\beqn
\frac{1}{3} \cdot \frac{1}{3} \cdot w \cdot p
	& = & \frac{wp}{9}
\eeqn

\noindent Let's at least understand the mathematical justification for
this conclusion!  Define the following events:

\begin{itemize}

\item Let $A$ be the event that the prize is behind door 1.

\item Let $B$ be the event that your initial guess is door 2.

\item Let $C$ be the event that Carol reveals door 3.

\item Let $D$ be the event that you switch.

\end{itemize}

\noindent Our goal is to find the probability of the outcome in which
all these events occur, namely $\pr{A \cap B \cap C \cap D}$.

We can interpret the edge probabilities along the highlighted path in
Figure~\ref{fig:tut2-monty} in terms of these variables.

\begin{itemize}

\item The first edge probability on the highlighted path,
$\frac{1}{3}$, is simply $\pr{A}$, the probability that the prize is
behind door 1.

\item The second edge probability, $\frac{1}{3}$, is $\pr{B \mid A}$,
the probability that your initial guess is door 2, given that the
prize is behind door 1.

\item The third probability, $w$, is $\pr{C \mid A \cap B}$, the
probability that Carol reveals door 3, given that the prize is behind
door 1 and your initial guess is door 2.

\item The final edge probability, $p$, is $\pr{D \mid A \cap B \cap
C}$, the probability that you switch, given that the prize is behind
door 1, your initial guess is door 2, and Carol reveals door 3.

\end{itemize}

In general, we can interpret an experiment as a random walk from the
root of a tree diagram to one of the leaves.  Under this
interpretation, the probability on an edge in a tree diagram is the
conditional probability that you traverse that edge, given that you
reach its parent node in the tree.

Now let's dinf out what the product of the edge probabilities really
is:

\beqn
\lefteqn{\pr{A} \cdot
	\pr{B \mid A} \cdot
	\pr{C \mid A \cap B} \cdot
	\pr{D \mid A \cap B \cap C}} \hspace{1in} \\
& = &	\pr{A} \cdot
	\frac{\pr{B \cap A}}{\pr{A}} \cdot
	\frac{\pr{C \cap A \cap B}}{\pr{A \cap B}} \cdot
	\frac{\pr{D \cap A \cap B \cap C}}{\pr{A \cap B \cap C}} \\
& = &	\pr{A \cap B \cap C \cap D}
\eeqn

\noindent The first step uses the definition of conditional
probability, and the second uses only cancellation of terms.

Amazingly enough, the product of the conditional probabilities on the
edges of the tree diagram is exactly the outcome probability that we
were looking for!  The method of multiplying edge probabilities in a
tree diagram to compute outcome probabilities can be justified in
general by extending the argument above.

With this formal justification in hand, you are free to continue using
tree diagrams in your solutions and proofs in this class.

\section{Bayes' rule}

What is the relationship between $\Pr\{A \mid B\}$ and $\Pr\{B \mid
A\}$?  Are they the same thing?  Can you give an example where it is
clear that these probabilities are different?  Some simple examples
suggest that the answer is ``no''.  For example, the probability that
you are a female given that you are an MIT student is now about
$\frac{1}{2}$.  On the other hand, the probability that you are an MIT
student given that you are a female is very small.  But we can write
one conditional probability in terms of the other pretty easily:

\begin{eqnarray*}
\Pr\{B \mid A\} & = & \Pr\{ A \mid B \} \cdot \frac{\Pr\{B\}}{\Pr\{A\}}
\end{eqnarray*}

This is called {\em Bayes' rule} and is a neat way of turning around
cause and effect.  Here $A$ and $B$ are events with nonzero
probability.  You can verify the equation above for yourself using the
definition of conditional probability.

Let's work an example that uses Bayes' rule.  A weatherman walks to
work each day.  Some days it rains:

\begin{eqnarray*}
\Pr\{\text{rains}\} & = & 0.30
\end{eqnarray*}

\noindent Sometimes the weatherman brings his umbrella.  Usually this
is because he predicts rain, but he also sometimes carries it to ward
off bright sunshine.

\begin{eqnarray*}
\Pr\{\text{carries umbrella}\} & = & 0.40
\end{eqnarray*}

\noindent As a weatherman, he usually doesn't get caught out in a
storm without protection:

\begin{eqnarray*}
\Pr\{\text{carries umbrella} \mid \text{rains} \} & = & 0.80
\end{eqnarray*}

\noindent Suppose you see the weatherman walking to work, carrying an
umbrella.  What is the probability of rain?

\begin{eqnarray*}
\Pr\{\text{rains} \mid \text{carries umbrella} \}
	& = &	\Pr\{\text{carries umbrella} \mid \text{rains} \} \cdot
		\frac{\Pr\{\text{rains}\}}{\Pr\{\text{carries umbrella}\}} \\
	& = &	0.80 \cdot \frac{0.30}{0.40} \\
	& = &	0.60
\end{eqnarray*}

We're turned around cause and effect.  Risk of rain has the effect of
making the weatherman carry his umbrella.  Yet we've shown that if he
carries his umbrella, it is pretty likely to rain!
\end{document}
