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

\renewcommand{\coursecopyrightnames}
{\href{http://theory.lcs.mit.edu/~meyer}{Prof.~Albert~R.~Meyer}}

\begin{document} 
\inclassproblems{10, Fri}



%nikos
%TUT10s - last used Spring 99 Tutorial 11, Problem 2
%LEARNING OUTCOMES:8 (calculate probabilities)
%                  10 (study in a small group)
%New problem added S02

\begin{problem} [Carried over from Wednesday]

You are organizing a neighborhood census and instruct your census takers
to knock on doors and note the sex of any child that answers the knock.
Assume that there are two children in a household and that girls and boys
are equally likely to be children and to open the door.

A sample space for this experiment has outcomes that are triples whose
first element is either \texttt{B} or \texttt{G} for the sex of the elder
child, likewise for the second element and the sex of the younger child,
and whose third coordinate is \texttt{E} or \texttt{Y} indicating whether
the \emph{e}lder child or \emph{y}ounger child opened the door.  For
example, $(\mathtt{B},\mathtt{G},\mathtt{Y})$ is the outcome that the elder
child is a boy, the younger child is a girl, and the girl opened the door.

\bparts

\problempart Let \emph{T} be the event that the household has two girls,
and \emph{O} be the event that a girl opened the door.  List the outcomes
in \emph{T} and \emph{O}.

\solution{$T=\set{GGE,GGY}, O=\set{GGE,GGY,GBE,BGY}$}

\ppart What is the probability $\prcond{T}{O}$, that both children are
girls, given that a girl opened the door?
\solution{1/2}

\problempart Where is the mistake in the following argument?

\begin{quote}
If a girl opens the door, then we know that there is at least one girl in
the household.  The probability that there is at least one girl is
\begin{equation}
1 - \prob{\text{both children are boys}} = 1 - (1/2 \times 1/2) = 3/4.
\end{equation}
So,
\begin{eqnarray}
\lefteqn{\prcond{T}{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T \intersect \text{there is at least one girl in the household}}}
{\pr{\text{there is at least one girl in the household}}}\\
& = & \frac{\prob{T}}{\pr{\text{there is at least one girl in the household}}}\\
& = & (1/4) / (3/4) = 1/3.
\end{eqnarray}
Therefore, given that a girl opened the door, the probability that there
are two girls in the household is \textup{1/3}.
\end{quote}


\solution{The argument is a correct proof that 
\[
\prcond{T}{\text{there is at least one girl in the household}} = 1/3.
\]
The problem is that the event, $H$, that the household has at least one girl,
namely,
\[
H \eqdef \set{\mathtt{GGE,GGY,GBE,GBY,BGE,BGY}},
\]
is not equal to the event, \emph{O}, that a girl opens the door.  These
two events differ:
\[
H-O = \set{\mathtt{BGE,GBY}},
\]
and their probabilities are different.  So the fallacy is in the final
conclusion where the value of $\prcond{T}{H}$ is taken to be the same as
the value $\prcond{T}{O}$.  Actually, $\prcond{T}{O} = 1/2$.  }

\eparts
\end{problem}


\textbf{(WE DIDN'T GET TO THE NEXT TWO PROBLEMS IN CLASS ON FRIDAY.)}

%% S02 cp9F

\begin{problem} [More Birthdays]
Suppose there are 100 people in a room.  Assume that their birthdays are
independent and uniformly distributed. As stated in lecture notes, with
probability $> 99\%$ there will be two that have the same birthday.

Now suppose you find out the birthdays of all the people in the room 
except one---call her ``Jane''---and find all 99 dates to be different.

\begin{problemparts}

\ppart 
What's wrong with the following argument:
\begin{quotation}\noindent
With probability greater than 99\%, some pair of people in the room have
the same birthday.  Since the 99 people we asked all had different
birthdays, it follows that with probability greater than~99\% Jane has the
same birthday as some other person in the room.
\end{quotation}

\solution{
Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
99 people we asked all have different birthdays.

It is true that $\pr{A} > 0.99$ (that is indeed the probability
spoken about in the lecture notes). However, that is the \emph{a
priori} probability, i.e., assuming all the birthdays are
uniform and independent, with no other constraints. The argument
above makes the erroneous assumption that event $A$ has
probability of at least $99\%$ even once we know that event $B$
holds. But once we know that event $B$ holds, the birthdays are
no longer independent. Thus $\pr{A \mid B}$ is not necessarily
equal to $\pr{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).
}

\ppart 
What is the actual probability that Jane has the same birthday
as some other person in the room?

\solution{
Let $S$ be the set of birthdays of the 99 people in the room
other than Jane. By assumption, $|S| = 99$. Let $b$ be the date
of Jane's birthday. Since $b$ is uniformly distributed over a
set of size 365, and $b$ is independent of all the birthdays in
$S$, we have
\[
\pr{A\mid B} = \pr{b\in S} = 
\frac{\card{S}}{365} = 
\frac{99}{365} \approx 27.1\%,
\]
where $B$ is the event that the 99 people we asked all have
different birthdays.
}

\end{problemparts}
\end{problem}


\iffalse

\begin{problem}

There is a course---not 6.042, naturally---in which $10 \%$ of the
assigned problems contain errors.  If you pick a random problem and ask
your TA and your Lecturer whether the problem has an error, then your TA
will answer correctly $80\%$ of the time.  This $80 \%$ accuracy holds
regardless of whether or not a problem has an error.  Likewise for your
Lecturer, but with only $75 \%$ accuracy.  (This is consistent with the
view that Lecturers are chosen for their theatrical personalities, not
their mastery of the material \texttt{:-)}

Furthermore, \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.}

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''?

In writing your solution, designate events as follows:
\begin{eqnarray*}
T & \eqdef & \mbox{``the TA says the problem has an error,''}\\
L & \eqdef & \mbox{``the lecturer says the problem has an error.''}\\
E & \eqdef & \mbox{``the problem has an error,''}
\end{eqnarray*}

\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 verify this informal argument by actually calculating the probability
of each of these events and their intersection, and then observing that
the probability that the two events occur is different from the product of
the probabilities.

The assumptions above tell us:
\begin{align}
\pr{E}        = & \frac{10}{100} = \frac{1}{10},\label{E10}\\
\prcond{T}{E} = & \prcond{\bar{T}}{\bar{E}} = \frac{80}{100} =
     \frac{4}{5},\label{TE}\\
\prcond{L}{E}  = & \prcond{\bar{L}}{\bar{E}}
       = \frac{75}{100} = \frac{3}{4}\label{LE}.
\end{align}

Also, $T$ and $L$ are independent given $E$, and given $\bar{E}$:
\begin{align}
\prcond{T \intersect L}{E}  = & \prcond{T}{E} \prcond{L}{E}\label{TLE}\\
\prcond{T \intersect L}{\bar{E}}  = & \prcond{T}{\bar{E}}
                      \prcond{L}{\bar{E}}  \label{TLbarE}. 
\end{align}

Note that while we know that $T$ and $L$ are independent \emph{given} $E$
or \emph{given} $\bar{E}$, we will show that they are not independent by
themselves.  In fact, we will show:
%\begin{claim*}
\[
\pr{L \intersect T} > \pr{L}\pr{T}.
\]
%\end{claim*}

We have:

\begin{align*}
\pr{T} = & \pr{T \cap E} + \pr{T \cap \bar{E}}
        & \text{(Law of Total Probability)}\\
 = & \prcond{T}{E} \pr{E}  + \prcond{T}{\bar{E}} \pr{\bar{E}}
        & \text{(Product Rule)} \\
 = & \prcond{T}{E} \pr{E}  + (1- \prcond{\bar{T}}{\bar{E}})(1- \pr{E})
        & \text{(Complement Rule)} \\
 = & \prcond{T}{E} \pr{E}  + (1- \prcond{T}{E})(1- \pr{E})
        & \text{(by~(\ref{TE}))} \\
 = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})(1 - \frac{1}{10})
        = \frac{13}{50}, & \text{(by~(\ref{TE}) and~(\ref{E10}))}\\
\end{align*}

A similar argument proves that
\begin{equation}
\pr{L} =  \pr{L \cap E} + \pr{L \cap \bar{E}}
  = \frac{3}{4} \frac{1}{10} + (1 -\frac{3}{4})(1 - \frac{1}{10}) = \frac{3}{10}.
\end{equation}

Finally,
\begin{align*}
\pr{L \cap T} = & \pr{L \cap T \cap E} + \pr{L \cap T \cap \bar{E}}
        & \text{(Law of Total Probability)}\\
= & \prcond{L \cap T}{E} \pr{E} + \prcond{L \cap T}{\bar E} \pr{\bar E}
        & \text{(Product Rule)} \\
= & \prcond{L}{E}      \prcond{T}{E}       \pr{E} + 
      \prcond{L}{\bar{E}} \prcond{T}{\bar{E}} \pr{\bar E} &
        \text{(by~(\ref{TLE}) and~(\ref{TLbarE}))}\\
= & \frac{3}{4} \cdot \frac{4}{5} \cdot \frac{1}{10}
        + (1 - \frac{3}{4}) (1 - \frac{4}{5}) (1 - \frac{1}{10}) =
        \frac{105}{1000} = 0.105. & \text{(by~(\ref{LE}) and~(\ref{TE}))}
\end{align*}
which is higher than 
\[
\pr{L}\pr{T} = \frac{3}{10} \cdot \frac{13}{50} = .078.
\]
}

\end{problem}
\fi

\begin{problem}
\iffalse

\bparts

\ppart Suppose you repeatedly flip a fair coin until you see the sequence
\texttt{HHT} or the sequence \texttt{TTH}.  What is the probability you
will see \texttt{HHT} first? \hint Symmetry between Heads and Tails.

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

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 \texttt{H} is replaced by a
\texttt{T} and vice versa.  For example $g(\mathtt{HHT}) =
\overline{\mathtt{HHT}} = \mathtt{TTH}$.

To show that $g$ is a bijection, we first observe that $g:A \rightarrow
B$.  This follows from the fact that \texttt{HHT} precedes \texttt{TTH} in
$w$ iff $\overline{\mathtt{HHT}} = \mathtt{TTH}$ precedes
$\overline{\mathtt{TTH}} = \mathtt{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{\mathtt{H}} = \prob{\mathtt{T}}$ and $g(w)$ has the same length as
$w$.  Hence,
\[
\prob{A} = \sum_{w \in A} \prob{w} = \sum_{w\in A} \prob{g(w)}
= \sum_{w' \in B} \prob{w'}  =  \prob{B}.
\]
The second equality is valid because $g$ preserves the probability, and
the third by the bijection property with $w' = g(w)$.  Note that the fact
that \texttt{H} and \texttt{T} are equally likely is critical in these
calculations; this analysis would fail for a biased coin.

Finally we have to show that $\prob{A \cup B} = 1$.  This follows from the
fact that the only way never to throw either pattern is to throw all
\texttt{H}'s or all \texttt{T}'s after the first toss, and we know that
the probability of there being an unbounded number of tosses of only H or
only T is zero.  That is, $\prob{\overline{A \cup B}} = 0$ and so $\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}.
\]
}


\ppart
\fi
Suppose you repeatedly flip a fair coin until you see the sequence
\texttt{HHT} or the sequence \texttt{HTT}.
What is the probability you see the sequence \texttt{HTT} before
you see the sequence \texttt{HHT}?
\hint Try to find the probability that \texttt{HHT} comes before
\texttt{HTT} conditioning on whether you first toss an \texttt{H} or a
\texttt{T}.  The answer is not $1/2$.

\solution{

\iffalse
First, we intuitively see that HHT is more likely than HTT,
because the sequence HHTT has HHT right one toss before HTT
so the appearance of HTT depends in a way in the appearance
of HHT before it. The inverse does not hold, since throwing
HHT is independent of HTT coming before it.
\fi

Let $A$ be the event that \texttt{HTT} appears before \texttt{HHT}, and let
$p \eqdef \prob{A}$.

Suppose our first toss is \texttt{T}.  Since neither of our patterns
starts with \texttt{T}, the probability that $A$ will occur from this
point on is still $p$.  That is, $\prcond{A}{\mathtt{T}} = p$.

Suppose our first toss is \texttt{H}.  To find the probability that $A$
will now occur, that is, to find $r \eqdef \prcond{A}{\mathtt{H}}$, we
consider different cases based on the subsequent throws.

Suppose the next toss is \texttt{H}, that is, the first two tosses are
\texttt{HH}.  Then neither pattern appears if we continue flipping
\texttt{H}, and when we eventually toss a \texttt{T}, the pattern
\texttt{HHT} will then have appeared first.  So in this case, event $A$
will never occur.  That is $\prcond{A}{\mathtt{HH}} = 0$.

Suppose the first two tosses are \texttt{HT}.  If we toss a \texttt{T}
again, then we have tossed \texttt{HTT}, so event $A$ has occurred.
If we next toss an \texttt{H}, then we have tossed \texttt{HTH}.  But this
puts us in the same situation we were in after rolling an \texttt{H} on
the first toss.  That is, $\prcond{A}{\mathtt{HTH}} = r$.

Summarizing this we have:
\begin{align}
\pr{A} &=
\prcond{A}{\mathtt{T}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{H}}\pr{\mathtt{H}}
& \text{(Law of Total Probability)}\\
p & = p\frac{1}{2} + r\frac{1}{2} & \text{so}\\
p & = r.\label{peq}
\end{align}

Continuing, we have
\begin{align}
\prcond{A}{\mathtt{H}} &=
\prcond{A}{\mathtt{HT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HH}}\pr{\mathtt{H}} &
\text{(Law of Total Probability)}\\
r &= \prcond{A}{\mathtt{HT}}\frac{1}{2} + 0\cdot\frac{1}{2}\label{here}\\
\prcond{A}{\mathtt{HT}} & =
\prcond{A}{\mathtt{HTT}}\pr{\mathtt{T}}+\prcond{A}{\mathtt{HTH}}\pr{\mathtt{H}}
& \text{Law of Total Probability}\\
\prcond{A}{\mathtt{HT}} & = 1\cdot\frac{1}{2} + r\frac{1}{2} \label{there}\\
r & = (\frac{1}{2} + \frac{r}{2})\frac{1}{2} & \text{by~(\ref{here}) \&~(\ref{there})}\\
r & = \frac{1}{3}.
\end{align}

So \texttt{HTT} comes before \texttt{HHT} with probability $p=r =\cfrac{1}{3}$.

It is an amazing fact that these kind of events are another example of
\emph{intransitivity} of the kind we saw with some
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln10.pdf}
{ln10}{intrans-dice}{special dice in Notes 10}.  Namely, if you may pick
\emph{any} pattern of three tosses such as \texttt{HTT}, then I can pick a
pattern of three tosses such as \texttt{HHT}.  If we then bet on which
pattern will appear first in a series of tosses, the odds will be in my
favor.  In particular, even if you instead picked the ``better'' pattern
\texttt{HHT}, there is another pattern I can pick that has a more than
even chance of appearing before \texttt{HHT}.  So this intransitivity
phenomenon comes up for real---you could make money on it betting in a
bar---and not just for some contrived dice.}

\iffalse \eparts \fi

\end{problem}


\instatements{
%\newpage
\appendix

\section*{Probability Rules}

\subsection*{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} = & \sum_{n \in \naturals} \pr{A_n}
\mbox{ for pairwise disjoint } A_n  \tag{Sum Rule}\\
\pr{A-B}  = &  \pr{A} - \pr{A \intersect B} \tag{Difference Rule}\\
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  = &  1 - \pr{B} & \tag{Complement Rule}\\
\pr{A \union B}  = &  \pr{A} + \pr{B} - \pr{A \intersect B}
        \tag{Inclusion-Exclusion}\\
\pr{A \union B}  \leq & \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} \le & \pr{A \union B} \tag{Monotonicity}
%
%\item $\pr{\lgintersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\end{align}

[Law of Total Probability] Suppose the sample space is the disjoint union
of $B_0, B_1, \dots$.  Then for all events $A$,
\begin{equation*}
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\end{equation*}


\subsection*{Conditional Probability}
\begin{align}
\prcond{A}{B} \eqdef &  \frac{\pr{A \intersect B}}{\pr{B}} \notag\\
\pr{A \intersect B} = & \prcond{A}{B} \pr{B} \tag{Product Rule}\\
\prcond{A}{B} = & \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

[Law of Total Probability - Conditional form]
Suppose the sample space is the disjoint union
of $B_0, B_1, \dots$.  Then for all events $A$,
\begin{equation*}
\pr{A} =  \sum_{i \in \naturals} \prcond{A}{B_i}\pr{B_i}.
\end{equation*}


\subsection*{Independence}
\begin{definition*}
Events $A$ and $B$ are \emph{independent} iff
\[
\pr{A \intersect B} = \pr{A}\pr{B}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{mutually independent} iff for all
subsets $J \subset \naturals$,
\[
\pr{\lgintersect_{i\in J} A_i} = \prod_{i \in J} \pr{A_i}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{$k$-wise independent} iff $\set{A_i
\suchthat i\in J}$ are mutually independent for all subsets $J \subset
\naturals$ with $\card{J} = k$.
\end{definition*}

\subsubsection*{Birthday Probabilities}

Suppose there are $s$ students and $d$ days in the year.  Let $D$ be the
event that all the students have \emph{\textbf{d}}ifferent birthdays.  Then
\begin{equation*}%\label{birthapprox}
\pr{D}  \sim  e^{-(s^2/2d)}.
\end{equation*}
as long as $s = o(\sqrt[3]{d^2})$.
}

\end{document}
