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

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\begin{document} 
\inclassproblems{9F}

\begin{problem}
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.

\bparts

\ppart
Suppose you have doubts about a problem and ask a TA about it, and she
tells you that the problem is correct.  To double-check, you ask a
lecturer, who says that the problem has an error.  Assuming 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.}, what is the probability that there is an error in the
problem?

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

\solution{The assumptions above tell us:
\begin{eqnarray*}
\pr{E}        & = & \frac{10}{100} = \frac{1}{10},\\
\prcond{T}{E} & = & \prcond{\bar{T}}{\bar{E}} = \frac{80}{100} = \frac{4}{5},\\
\prcond{L}{E} & = & \prcond{\bar{L}}{\bar{E}} = \frac{75}{100} = \frac{3}{4},
\end{eqnarray*}

Also, $T$ and $L$ are independent given $E$, and given $\bar{E}$:
\begin{eqnarray}
\prcond{T \intersect L}{E} & = & \prcond{T}{E} \prcond{L}{E}\\
\prcond{\bar{T} \intersect L}{\bar{E}} & = & \prcond{\bar{T}}{\bar{E}} \prcond{L}{\bar{E}}\\
\end{eqnarray}
Note that T and L are not independent by themselves (see part b), but they are independent GIVEN E or GIVEN $\bar{E}$.  If we know there is an error, then the T.A. will say there's an error 3/4ths of the time, regardless of what the lecturer says.  But if we don't know whether there is an error or not, then the lecturer's response will give us information as to the T.A.'s likely response.

We want to calculate
\[
\prcond{E}{\bar{T} \intersect L}.
\]

From the definition of conditional probability (this is Bayes' rule):
\begin{equation}\label{eq:B2}
 \prcond{E}{\bar{T} \intersect L} = \pr{E}
 \frac{\prcond{\bar{T} \intersect L}{E}}
      {\pr{\bar{T} \intersect L}}.
\end{equation}

By the independence assumptions, we have:
\begin{eqnarray*}
\prcond{\bar{T} \intersect L}{E} & = & \prcond{\bar{T}}{E} \prcond{L}{E}
     = \frac{1}{5}\frac{3}{4}  = \frac{3}{20},\\
\prcond{\bar{T} \intersect L}{\bar{E}} & = &
         \prcond{\bar{T}}{\bar{E}} \prcond{L}{\bar{E}}
     = \frac{4}{5} \cdot \frac{1}{4} = \frac{1}{5},\\
\pr{\bar{T} \intersect L} & = & \prcond{\bar{T} \intersect L}{E}  \pr{E} + 
                          \prcond{\bar{T} \intersect L}{\bar{E}} \pr{\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
\[
\prcond{E}{\bar{T} \intersect L} = \frac{1}{10} \cdot \frac{3/20}{39/200} =
\frac{1}{13} \approx 0.077.
\]
So this contradictory information has decreased the probability of an error
from $10 \%$ to about $7.7 \%$.

The calculations here support 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, since the probability of an error remains
uncomfortably large.}

\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 verify this informal argument by actually calculating the probability
of each of 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*}
\pr{T} & = & \pr{T \cap E} + \pr{T \cap \bar{E}}\\
 & = & \pr{T \mid E} \pr{E}  + \pr{T \mid \bar{E}} \pr{\bar{E}}\\
 & = & \frac{4}{5} \frac{1}{10} + (1 - \frac{4}{5})
 (1 - \frac{1}{10}) = \frac{13}{50},\\
& & \\
\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},\\
& & \\
\pr{L \cap T} & = & \pr{L \cap T \cap E} + \pr{L \cap T \cap \bar{E}} \\
& = & \pr{L \cap T \mid  E} \pr{E} + \pr{L \cap T \mid  \bar E} \pr{\bar E}\\
& = & \pr{L \mid E}      \pr{T \mid  E}       \pr{E} + 
      \pr{L \mid \bar E} \pr{T \mid  \bar{E}} \pr{\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 
\[
\pr{L}\pr{T} = \frac{3}{10} \cdot \frac{13}{50} = .078.
\]
}

\eparts
\end{problem}


\begin{problem} (Carried over from Wednesday)
Prove that if $A$ and $B$ are independent events, then so are $\bar{A}$
and $B$.

\solution{From the Law of Total Probability we have
\[
\pr{B} = \pr{B \intersect \bar{A}} + \pr{B \intersect A},
\]
so
\begin{align}
\pr{B \intersect \bar{A}} & =  \pr{B} - \pr{B \intersect A}\\
 & = \pr{B} - \pr{B}\pr{A} & \text{because $A$ and $B$ are independent}\\
 & = \pr{B}(1 - \pr{A}) = \pr{B}\pr{\bar{A}}.
\end{align}
}

\end{problem}

%%%%%%%%%%%%%%  Fall 2000  PS 10   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%%new part (a) and all solns substantially revised by ARM Spring 02

\begin{problem}\label{ABC}
Let $A,B,C$ be events.  For each of the following statements, prove it or
give a counterexample.

\bparts

\ppart\label{ABCI} If $C$ is independent of $A$, and $C$ is independent of $B$, then
$C$ is independent of $A \intersect B$.

\solution{Any set of pairwise independent $A,B,C$ that are not mutally independent
will yield a counter-example.  But to be specific, let the sample space be
the set of four length-two bit strings.  Define $A$ to be the event that
the first bit is 1, $B$ to be the event that the second bit is 1, and $C$
to be the event that at exactly one of the bits is 1.

Note $A$, $B$ and $C$ each consist of two sample points, and the
intersection of any two of them consists of one point.  So each has
probability 2/4=1/2, while the intersection of any two of them has
probability $1/4$.  Therefore the product, $(1/2)\cdot(1/2)$, of the
probabilities of any two of these events equals the probability of their
intersection.  So any two among $A,B$ and $C$ are independent, \ie they are
\emph{pairwise} independent.

But there are no points in all of $A$, $B$ and $C$.  So 
\[
\pr{C \intersect (A \intersect B)} = 0 \neq \frac{1}{8} = \frac{1}{2}
\cdot \frac{1}{4} = \pr{C}\pr{A \intersect B}.
\]
Hence, $C$ is not independent of $A \union B$.
}

\ppart\label{ABOPLUS} If $C$ is independent of $A$, and $C$ is independent
of $B$, then $C$ is independent of $A \union B$.

\solution{
The statement is false.

The countexample from part~(\ref{ABCI}) works here too.

We already observed that $A$, $B$ and $C$ are pairwise independent.  We
claim that $C$ is not independent of the event $A \cup B$.  This follows
because $A \union B$ consists of the two points in $C$ as well as the point
\texttt{11}.  So
\[
\pr{C \intersect (A \union B)} = \pr{C} = \frac{1}{2} \neq \frac{1}{3} =
\frac{1}{2} \cdot \frac{2}{3} = \pr{C}\pr{A \union B}.
\]
}

\ppart If $C$ is independent of $A$, and $C$ is independent of $B$, and
$C$ is independent of $A \intersect B$, then $C$ is independent of $A
\union B$.

\solution{The statement is true:
\begin{align*}
\pr{C \intersect (A \union B)} & = \pr{(C \intersect A) \union (C \intersect B)}
          & \text{(distributivity of $\intersect$ over $\union$)}\\
  & =  \pr{C \intersect A} + \pr{C \intersect B} - \pr{(C \intersect A \intersect B)} 
          & \text{(inclusion-exclusion)}\\
  & = \pr{C}\pr{A} + \pr{C}\pr{B} - \pr{C}\pr{A \intersect B}
          & \text{(independence)}\\
  & = \pr{C}(\pr{A} + \pr{B} - \pr{A \intersect B}) & \text{(factoring)}\\
  & = \pr{C}(\pr{A \union B}) & \text{(inclusion-exclusion)}.
\end{align*}
}

\eparts

\end{problem}


%% F01 TUT 11

\begin{problem} \textbf{(Birthdays Again)}
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}


\begin{problem}
Let $A_1,\dots, A_n$ be mutually independent events, each with probability
1/2.  Let $D$ be the event that an even number of the events $A_1,\dots,
A_n$ occurs.  Prove that any set of $n$ among the $n+1$ events $A_1,\dots,
A_n, D$ are mutually independent, but $A_1,\dots, A_n, D$ are not mutually
independent.

\solution{
$A_1,\dots, A_n, D$ are mutually dependent, since whether or not each of
$A_1,\dots, A_n$ occurs determines whether or not $D$ does.

By symmetry among the $A_i$'s, to show $n$-way independence, we need only
show that $D,A_2,\dots, A_n$ are mutually independent.  Let $A^(1) \eqdef
A$, and $A^(-1) \eqdef \bar{A}$.  If $A_2^{(x_2)} \intersect \dots
\intersect A_n^{x_n}$ for $x_i = \pm 1$ occurs, then we know that $D$ is
determined by $A_1$ and vice versa, so the conditional probability of $D$
will be the same of that of $A_1$, namely, 1/2.  Since $A_1$ is
independent of $A_2,\dots, A_n$, it follows that $D$ is independent of
$A_2,\dots, A_n$.

Also, $\pr{D}= 1/2$ because it equals the sum of the probabilities of the
$2^{n}/2$ intersections $A_1^{(x_1)} \intersect \dots \intersect
A_n^{x_n}$ with an even number of $x_i$'s equal to one.  But each of these
intersections has probability $2^{-n}$, so their sum is 1/2.}

\end{problem}

\instatements{
\appendix

\section{Appendix}

\subsection{Events}

\begin{eqnarray*}
\pr{\lgunion_{n \in \naturals} A_n} & = & \sum_{n \in \naturals} \pr{A_n}
\quad \mbox{for pairwise disjoint $A_n$ [Sum Rule]}\\
\pr{A-B}  & = &  \pr{A} - \pr{A \intersect B} \quad \mbox{[Difference Rule]} \\
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  & = &  1 - \pr{B} \label{1-b}\quad \text{[Complement Rule]}\\
\pr{A \union B}  & = &  \pr{A} + \pr{B} - \pr{A \intersect B}\quad \text{[Inclusion-Exclusion]}\\
\pr{A \union B} & \leq & \pr{A}+ \pr{B} \quad \mbox{[Boole's inequality]} \\
\pr{A} & \le & \pr{A \union B} \quad \text{[monotonicity]}\\
%
%\item $\pr{\lgintersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\prcond{A}{B} {\pr{B}}  & = &  \pr{A \intersect B}\quad \text{[Product Rule]}\\
\prcond{A}{B} & = & \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \quad \mbox{[Bayes Rule]}\\
\end{eqnarray*}

\begin{lemma*}[Law of Total Probability]
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\[
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\pr{A} = \sum_{i \in \naturals} \pr{A | B_i}\pr{B_i}.
\]
\end{lemma*}

\subsection{Independence}
\begin{definition*}
Events $A$ and $B$ are 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 for all
subsets $J \subset \naturals$ with $\card{J} \le k$, $\set{A_i \suchthat
i\in J}$ are mutually independent.

\subsection{Birthdays}

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

\end{document}
