\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
%change it back!
%\input{../macros-course}
%\newcommand{\ssl}{
%\medskip
%\textbf{Solution:}
%\medskip
%}
\newcommand{\comp}[1]{\overline{#1}}
\newcommand{\given}{\mid}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}
\newcommand{\Intersect}{\bigcap}
\newcommand{\Union}{\bigcup}


%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}
%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\handout{tut11}{Mini-Quiz 11}{April 27, 2001}
\begin{enumerate}
\item Write your name:
\item You are about to roll a biased die. Find the probability of each outcome if \emph{all} of the conditions below hold:
\begin{itemize}
\item Rolling a 2 occurs with the same probability as rolling a 4
\item Rolling 1, 3, 5, 6 all occur with the same probability.
\item Rolling a 2 is three times as likely as rolling a 1.
\end{itemize} 
Give your results in the table below:
\end{enumerate}
\begin{center}
\begin{tabular}{|c|c|}
\hline
Outcome&Probability \\ \hline
1& \\ \hline
2& \\ \hline
3& \\ \hline
4& \\ \hline
5& \\ \hline
6& \\ \hline
\end{tabular}
\end{center}
\newpage
\thispagestyle{empty}
\mbox{}
\setcounter{page}{0}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{tut11}{Tutorial 11 Problems}{April 27, 2001}


\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Is it true that ``$A$ and $B$ independent" $\Longleftrightarrow$ ``$A$ and $\comp{B}$ independent"?

\solution{\ssl Yes
\proof

($\Longrightarrow$)Assume that $\Pr[A\intersect B]~=~\Pr[A]\cdot\Pr[B]$. Then:
\[
\Pr[A\intersect\comp{B}] = \Pr[A] - \Pr[A\intersect B]
 = \Pr[A](1-\Pr[B]) = \Pr[A]\Pr[\comp{B}]
\]

($\Longleftarrow$)Assume that $\Pr[A\intersect \comp{B}]~=~\Pr[A]\Pr[\comp{B}]~=~\Pr[A]\cdot(1-\Pr[B])$. Then:
\[
\Pr[A\intersect B]~=~\Pr[A] - \Pr[A\intersect \comp{B}]=\Pr[A] - \Pr[A](1-\Pr[B])=\Pr[A]\cdot \Pr[B]
\]


}

  \problem Since his appointment at MIT ends this summer, Dr
  Engebretsen is currently in the process of applying for jobs. He
  reasons that his chances of getting interviewed should increase if
  he praises his future employer in the application; therefore, he
  writes separate, personalized letters to all his prospective employers.
  
  Being eager to complete the application process, Dr. Engebretsen remembered to write the addresses on the envelopes only \emph{after} having sealed them. In order to avoid having to open all the envelopes, he
  adopts the strategy of writing the addresses on the letters
  uniformly at random. What is the probability that at least one
  prospective employer gets the right letter (the one addressed to him)?

  \begin{problemparts}
    \problempart First suppose that Dr Engebretsen sends 3~letters and
    compute the probability in this case.
    \solution{\ssl
Consider the events $A_1, A_2, A_3$ where $A_i$ means that the $i$th envelope contains the right letter. The probability that at least one of these occurs is then:
\[
\Pr[A_1\union A_2\union A_3]
\]
The events are not independent, so we need to use the inclusion/exclusion principle to figure out this probability. We notice that
\[
\Pr[A_1]=\Pr[A_2]=\Pr[A_3]=\frac{(3-1)!}{3!}=\frac{1}{3}
\]
This is because if the first letter is placed correctly ($A_1$), the remaining two can be arranged in $2!$ ways, and similarly for the other two cases.
Moreover,
\[
\Pr[A_1\intersect A_2]~=~\frac{(3-2)!}{3!}=\frac{1}{6}
\]
and likewise for all $\binom{3}{2}$ pairwise intersections.
Finally,
\[
\Pr[A_1\intersect A_2\intersect A_3]~=~\frac{(3-3)!}{3!}=\frac{1}{6}
\]
So, according to the inclusion/exclusion principle, 
\[
\Pr[A_1\union A_2\union A_3]=\binom{3}{1}\frac{1}{3}-\binom{3}{2}\frac{1}{6}+\binom{3}{3}\frac{1}{6}=\frac{2}{3}
\]
It would seem simpler to instead consider the complement event
\[
\Pr[A_1\union A_2\union A_3]
=
1 - \Pr[\comp{A_1}\intersect\comp{A_2}\intersect\comp{A_3}].
\]
However, \emph{the events $\comp{A_1}$, $\comp{A_2}$ and~$\comp{A_3}$
  are not independent!} In fact, they are not even pairwise
independent. To see this, consider $\Pr[A_2 \given A_1]$. (We can
consider $\Pr[A_2 \given A_1]$ instead of $\Pr[\comp{A_2} \given
\comp{A_1}]$ by problem~1 above.) When the first letter has the
correct address, the probability that the second letter has the
correct address is $1/2$.  However $\Pr[A_2] = 1/3 \neq \Pr[A_2 \given
A_1]$.  Using the product rule, we could rewrite the probability we
are interested in as
\[
\Pr[A_1\union A_2\union A_3]
=
1 - \Pr[\comp{A_1}]\Pr[\comp{A_2}\given\comp{A_1}]
\Pr[\comp{A_3}\given\comp{A_2}\intersect\comp{A_1}]
\]
and then compute the conditional probabilities, but this would
most likely not be simpler than inclusion\slash exclusion.}

    
    \problempart Being a theoretician, Dr Engebretsen of course sent
    $n$~letters.  Find an approximation of the probability in this case.
    \solution{\ssl Let $A_i$ be the event that envelope~$i$ has the
      correct address. We are interested in $\Pr[\cup A_i]$.  To apply
      the inclusion-exclusion formula, we need to compute the
      probabilities of individual intersection events---namely, to
      determine the probability $\Pr[A_{i_1}\cap A_{i_2} \cap
      \cdots\cap A_{i_k}]$ that the addresses on envelopes $i_1,
      \ldots, i_k$ are correct.  To do so we apply our standard four
      steps.
      \begin{description}
      \item[The sample space.] The sample space involves a permutation
        of the addresses written on the envelopes. There are $n!$
        permutations, so the sample space has size~$n!$.
      \item[Determine atomic event probabilities.] We assume a uniform
        sample space, so each event has probability $1/(n!)$.
      \item[Determine the event of interest.] These are the
        permutations where envelopes $i_1,\ldots,i_k$ have the correct
        address.
      \item[Find the event probability.] Since the sample space is
        uniform, this is equivalent to determining the \emph{number}
        of atomic events in our event of interest. How many
        permutations have the property that letters $i_1,\ldots, i_k$
        have the correct addresses? Well, the remaining $n-k$ letters
        can be addressed arbitrarily so the total number of atomic
        events of this type is $(n-k)!$. Thus, the \emph{probability}
        of the event in question is $(n-k)! / n!$.
      \end{description}
      We have found that the probability a specific set of
      $k$~addresses is correct is $(n-k)!/n!$. There are
      $\binom{n}{k}$ such sets of $k$ cards. So the term number~$k$ in
      the inclusion\slash exclusion expression is
      \[
      \binom{n}{k}\frac{(n-k)!}{n!} =
      \frac{n!}{(n-k)!k!} \times \frac{(n-k)!}{n!} =
      \frac{1}{k!}\,.
      \]
      Thus, the probability of at least one match is
      \[
      1-1/2!+1/3!-\cdots + (-1)^{n+1}/n!
      \]
      We can understand this expression by thinking about the Taylor
      expansion of
      \[
      e^{-x} = 1-x+x^2/2!-x^3/3!+\cdots
      \]
      In particular,
      \[
      e^{-1} = 1-1+1/2!-1/3!+\cdots
      \]
      Our expression takes the first $n+1$ terms of the Taylor
      expansion; the remainder is less than $1/(n+1)!$, which is
      negligible. So, our probability is approximately $1-1/e$.}
  \end{problemparts}
  




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Suppose that, in a course (not 6.042, naturally), $10\%$ of the
problems on quizzes 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.We assume that 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.

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{\ssl

The answer is no. We will show that the probability that
the two events occur is different from the product of the probabilities.
Define the events $T$, $L$, and $E$ as before.

The probability of $T$ is 

\begin{eqnarray*}
 \Pr(T)&=& \Pr(T\cap E) + \Pr(T\cap \overline{E}) \\
 &=& {80\over 100}{10\over 100}+{20\over 100}{90\over 100} \\
 &=& {26\over 100}\\
 & = & .26
\end{eqnarray*}

The probability of $L$ is 

\begin{eqnarray*}
 \Pr(L)&=& \Pr(L\cap E) + \Pr(L\cap \overline{E}) \\
 &=& {75\over 100}{10\over 100}+{25\over 100}{90\over 100} \\
 &=& {30\over 100}\\
 & = & .3
\end{eqnarray*}


The probability of $L \cap T$ is

\begin{eqnarray*}
 \Pr(L \cap T)&=& \Pr(L\cap T \cap E) + \Pr(L\cap T \cap \overline{E}) \\
& = & \Pr (L \cap T | E) Pr (E) + Pr (L \cap T | \overline E) Pr (\overline E)\\
& = & \Pr (L |E)Pr( T | E) Pr (E) + Pr (L |\overline E)
Pr (T | \overline E) Pr (\overline E)\\
 &=& {75\over 100}{80 \over 100} {10\over 100}+{25\over 100}
{20 \over 100} {90\over 100} \\
 &=& {105 \over 1000}\\
 & = & .105
\end{eqnarray*}

This is higher than 

\[ Pr (L)Pr(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 say there is an error.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Mr. Simpson has been involved in a car crash with Ms. Nicole, who then decided to sue Mr. Simpson for damages, including the loss of her antique Volkswagen Beattle and physical injuries she sustained when her hot coffee was spilled on her lap during the crash. There is very little incriminating evidence against Mr. Simpson, but Ms. Nicole's lawyers maintain that he is very likely to have been responsible for the car crash because it is widely known that Mr. Simpson routinely talks on his cell phone while driving (implying that the car crash must have taken place while he was talking on the phone, which increases the likelihood that \emph{he} was responsible for the crash).  

Defense attorney Dershowitz observed that the fraction of drivers who talk on their cell phone while driving and are involved in a car crash while doing so is $1/2000$.

Since the probability that someone who ``talks and drives" ends up causing an accident is so
low, Dershowitz maintains that the fact that Mr. Simpson talks on his cell phone while driving should be excluded from the evidence.  

We will develop a counter-argument to Dershowitz', by conditioning the probability
on the event that there was a car crash.

We have the following statistical information concerning cell phones and car crashes, for the period of one week:
\begin{center}
\begin{tabular}{|l|c|}
\hline
drivers & 125M\\
drivers with cell phones & 50M\\
drivers who talk and drive & 3M\\
drivers who caused crashes& 6K\\
drivers who caused crashes while talking and driving& 1.5K\\
\hline
\end{tabular}
\end{center}
The number of drivers who talk and drive includes those who caused a crash while talking and driving.  Define the events
\begin{eqnarray*}
H & ::= & \mbox{driver who causes a crash while talking and driving} \\
M & ::= & \mbox{driver who causes a crash} \\
B & ::= & \mbox{driver who routinely talks and drives}
\end{eqnarray*}

\bparts

\ppart Dershowitz' statistical observation can be stated technically as
\[\prob{H \mid B} = 1/2000.\]
Prove it.

\solution{\ssl
\[
\prob{H \mid B}
= \frac{\prob{H \intersect B}}{\prob{B}}
=\frac{\prob{H}}{\prob{B}}=\frac{1500/125M}{3M/125M}
=\frac{1500}{3M}=1/2000.
\]}

\ppart Calculate $\prob{H \mid M}$, i.e., the probability that a driver who caused a car crash was ``talking and driving" during the crash.

\solution{\ssl
\[\prob{H \mid M}
= \frac{\prob{H \intersect M}}{\prob{M}}
=\frac{\prob{H}}{\prob{M}}=\frac{1500/125M}{6000/125M}
= \frac{1500}{6000}=1/4.
\]}

\iffalse
\ppart Prove
\begin{equation}

\label{ABA-B}
\prob{C \mid A}  =  \prob{C \intersect D \mid A} + \prob{C - D \mid A}
\end{equation}
for arbitrary events $A, C, D$.

\solution{\ssl
\begin{eqnarray*}
\prob{C \intersect A} & = & \prob{(C \intersect A) \intersect D}
    + \prob{(C \intersect A) - D},\\
& = & \prob{(C \intersect D) \intersect A}
    + \prob{(C - D) \intersect A}.\\
\end{eqnarray*}
Now dividing both sides of this equation by $\prob{A}$ yields the desired
identity.}
\fi

\ppart Calculate $\prob{H \mid B \intersect M}$, i.e., the probability that
a driver who routinely ``talks and drives" and caused a crash, caused the car crash while talking on his cell phone.  Assume that the
the probability of a driver causing a crash while NOT talking on his cell phone is not influenced by whether or not s/he routinely talks on his cell phone while driving.

\hint $\prob{C \mid A}  =  \prob{C \intersect D \mid A} + \prob{C - D \mid
A}$.

\solution{\ssl
Note that
\[
\prob{H \mid B \intersect M}
= \frac{\prob{H \intersect B \intersect M}}{\prob{B \intersect M}}
= \frac{\prob{H}}{\prob{M \mid B} \prob{B}}.
\]

To evaluate $\prob{M \mid B}$, we apply the identity from the hint:
\[
\prob{M \mid B} = \prob{M \intersect H \mid B} + \prob{M - H \mid B}.
\]
We know that probability of a driver causing a crash while NOT talking on his cell phone is not influenced by whether or not s/he routinely talks on his cell phone while driving,
namely,
\[\prob{M - H \mid B} = \prob{M - H},\]
and $H \intersect M = H$, so
\[
\prob{M \mid B} =  \prob{H \mid B} + \prob{M - H} =
\frac{1}{2000} + \frac{6K - 1.5 K}{125M}.
\]

Now we have
\begin{eqnarray*}
\prob{H \mid B \intersect M} & = & \frac{1500 / 125M}{(1/2000 +
(6K - 1.5 K)/125M)3M/125M}\\
 & = & \frac{1500}{3M/2000 + 4500 \cdot 3/125}\\
 & = & \frac{1}{1 + 9/125}\ =\ \frac{125}{134}\  \approx\  0.93.
\end{eqnarray*}
}

\ppart How could you counter Dershowitz' argument that evidence that a driver routinely talks on his cell phone while driving should be excluded from the evidence?

\solution{\ssl
In general, the probability that someone was talking on the phone during the crash is 25\%. However, if the driver routinely ``talks and drives", the probability that he was on the phone during the crash jumps to  93\%, so the fact of using a cell phone while driving greatly influences the probability of a driver's guilt.
Assuming it is proper for a jury to consider such probabilities---this is
questionable by the way---then Dershowitz' argument that talking on the phone is
unlikely to be relevant does not hold up.}

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider an example of three loaded dice A, B,
C with the properties
\begin{itemize}
\item Die A always comes up 3.
\item Die B is 2 with prob $p$ and 5 otherwise.
\item Die C is 4 with prob $p$ and 1 otherwise.
\end{itemize}
Last time, we proved that if $p = (\sqrt{5} - 1)/2 = 0.618\ldots$\footnote{Note that $p$ is a root of $x^2 + x - 1$}, then the dice have the property that on any roll of dice A and B, the
probability that A beats B is $p$, on a
roll of B and C the probability that B beats C is $p$, and likewise on a
roll of C and A, the probability that C beats A is $p$.  That is, the
``probably beats'' relation on these dice is \emph{intransitive}.


Can we increase this probability?  That is, can we construct dice so that
the probability of A beating B, B beating C, C beating A are each, say, at
least 3/4?  The answer is ``No.''  In fact, the probabilities cannot all
exceed 2/3.  More precisely, consider the experiment of rolling all three
dice.  Define $A$ to be the event that A beats B, $B$ the event that B
beats C, and $C$ the event that C beats A.

Prove that
\[
\min \set{\prob{A}, \prob{B}, \prob{C}} \leq \frac{2}{3}.
\]
\hint Observe that $\prob{A \intersect B \intersect C} = 0$ and apply
Boole's Inequality to the complement.

\solution{\ssl

\begin{proof}
\[\begin{array}{rcll}
\prob{A \intersect B \intersect C}
    & = & 1 - \prob{\bar{A} \union \bar{B} \union \bar{C}} 
          & \mbox{DeMorgan's Law}\\
    & \geq & 1 - (\prob{\bar{A}}+ \prob{\bar{B}} + \prob{\bar{C}}
                & \mbox{by Boole's Inequality}\\
    & = & \prob{A} + \prob{B} + \prob{C} - 2 & 
\end{array}\]
But $\prob{A \intersect B \intersect C} = 0$,
since it is impossible that on any single roll, die A is higher than die B,
\emph{and} B is higher than C, {\em and} C is higher than A.
Hence
\[2  \geq  \prob{A} + \prob{B} + \prob{C} \geq 3 \min \set{\prob{A},\prob{B},\prob{C}}\]
and therefore
\[2/3 \geq \min \set{\prob{A}, \prob{B}, \prob{C}}.\]
\end{proof}

% \textbf{Extra Credit Problem}: Show that the 2/3 bound can be improved to $p
% = (\sqrt{5} - 1)/2 = 0.618\ldots$, and that this is the minimum bound. 

}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




\end{problems}
\end{document} 