\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\begin{document}

\recitation{19}{November 19, 2004}

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

\begin{problem} \textit{Bayes' Rule} says that if $A$ and $B$ are events with
nonzero probabilities, then:
%
\[
\pr{A \mid B} \cdot \pr{B} = \pr{B \mid A} \cdot \pr{A}
\]

\bparts

\ppart Prove Bayes' Rule.

\solution[\vspace{1.5in}]{We reason as follows:
%
\begin{align*}
\pr{A \cap B} & = \pr{A \cap B} \\
\frac{\pr{A \cap B}}{\pr{B}} \cdot \pr{B} & = \frac{\pr{A \cap B}}{\pr{A}} \cdot \pr{A} \\
\pr{A \mid B} \cdot \pr{B} & = \pr{B \mid A} \cdot \pr{A}
\end{align*}
%
In the first step, we rewrite both sides using the facts that $\pr{A}$
and $\pr{B}$ are nonzero.  The second step uses the definition of
conditional probability.}

\ppart A weatherman walks to work each day.  Some days it rains:
%
\[
\pr{\text{rains}} = 0.30
\]
%
Sometimes the weatherman brings his umbrella.  Usually this is because
he predicts rain, but he also sometimes carries it to ward off bright
sunshine.
%
\[
\pr{\text{carries umbrella}} = 0.40
\]
%
As a weatherman, he usually doesn't get caught out in a storm without
protection:
%
\[
\pr{\text{carries umbrella} \mid \text{rains}} = 0.80
\]
%
Suppose you see the weatherman walking to work, carrying an umbrella.
What is the probability of rain?  Use Bayes' Rule.

\solution[\newpage]{
\begin{align*}
\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{align*}
%
We've 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!}

\eparts

\end{problem}

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

\newpage

\noindent \textbf{Fact from lecture.}  If there are $N$ days in a year
and $m$ people in a room, then the probability that no two people in
the room have the same birthday is about:
%
\[
e^{-m^2/(2N)}
\]

\begin{problem}
Suppose that we create a a national database of DNA profiles.  Let's
make some simplistic assumptions:
%
\begin{itemize}
\item Each person can be classified into one of \underline{20 billion}
different ``DNA types''.  (For example, you might be type
\#13,646,572,661 and the person next to you might be type
\#2,785,466,098.)  Let $T(x)$ denote the type of person $x$.
\item Each DNA type is equally probable.
\item The DNA types of Americans are mutually independent.
\end{itemize}

\bparts

\ppart A congressman argues that there are only about 250 million
Americans, so even if a profile for every American were stored in the
database, the probability of even one coincidental match would be very
small.  How many profiles must the database actually contain in order
for the probability of at least one coincidental match be about $1/2$?

\solution[\vspace{1.25in}]{By the birthday principle, the probability of
a match is around half when the number of entries is:
%
\[
\sqrt{2 \ln 2 \cdot 20,000,000,000} = 166,511
\]
}

\ppart Person $x$ is arrested for a crime that was committed by person
$y$.  At trial, jurors must determine whether $x = y$.  The crime lab
says $x$ and $y$ have the same DNA type.  The prosecutor argues that
the probability that $x$ and $y$ are different people is only 1 in 20
billion.  Write the prosecutor's assertion in mathematical notation
and explain her error.

\solution{The prosecutor is asserting that:
%
\[
\pr{\text{$x$ and $y$ are different people} \mid T(x) = T(y)} = 2 \cdot 10^{-10}
\]
%
This assertion is at best false and arguably not even a well-formed
mathematical statement.  Either $x$ and $y$ are the same person or
different people, regardless of the DNA types of all the people in the
world.  Thus, either $x$ and $y$ are the same person in every outcome
or they are different people.  Consequently, the probability above is
either 0 or 1, but we don't know which.

The prosecutor's argument \textit{sounds} confusingly similar to a
correct assertion: if $x$ and $y$ are different people, then:
%
\[
\pr{T(x) = T(y)} = 2 \cdot 10^{-10}
\]

The prosecutor can validly argue that \textit{either} an amazing
1-in-20 billion coincidence involving DNA has occurred \textit{or
else} $x$ and $y$ are the same person.  On this basis, a jury might
conclude that $x$ is almost surely guilty, but there is nothing in our
probability model to justify that conclusion directly.}

\eparts

\end{problem}

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

\newpage

\begin{problem}
There were $n$ Immortal Warriors born into our world, but in the end
{\em there can be only one}.  The Immortals' original plan was to
stalk the world for centuries, dueling one another with ancient swords
in dramatic landscapes until only one survivor remained.  However,
after a thought-provoking discussion of probabilistic independence,
they opt to give the following protocol a try:

\begin{enumerate}

\item The Immortals forge a coin that comes up heads with probability
$p$.

\item Each Immortal flips the coin once.

\item If {\em exactly one} Immortal flips heads, then he or she is
declared The One.  Otherwise, the protocol is declared a failure, and
they all go back to hacking each other up with swords.

\end{enumerate}

\bparts

\ppart One of the Immortals (the Kurgan from the Russian steppe)
argues that as $n$ grows large, the probability that this protocol
succeeds must tend to zero.  Another (McLeod from the Scottish
highlands) argues that this need not be the case, provided $p$ is
chosen \textit{very carefully}.  What does your intuition tell you?

\solution[\vspace{0.5in}]{Your intuition tells you that a short nap
would be nice right now.  As would a couple cookies to dunk in a cold
glass of milk.}

\ppart What is the probability that the experiment succeeds as a
function of $p$ and $n$?

\solution[\vspace{1.5in}]{The sample space consists of all possible
results of $n$ coin flips, which we can represent by the set $\{ H, T
\}^n$.  Let $E$ be the event that the experiment successfully selects
The One.  Then $E$ consists of the $n$ outcomes which contain a single
head.  In general, the probability of an outcome with $h$ heads and $n
- h$ tails is:

\[
p^h (1-p)^{n-h}
\]

Summing the probabilities of the $n$ outcomes in $E$ gives the
probability that the procedure succeeds:


\begin{eqnarray*}
\pr{E} & = & n p (1-p)^{n-1}
\end{eqnarray*}
}

\ppart How should $p$, the bias of the coin, be chosen in order to
maximize the probability that the experiment succeeds?  (You're going
to have to compute a derivative!)

\solution[\vspace{1.75in}]{We compute the derivative of the success
probability:

\begin{eqnarray*}
\frac{d}{dp}\ n p (1-p)^{n-1}
	& = & n (1-p)^{n-1} - n p (n-1) (1-p)^{n-2} \\
\end{eqnarray*}

Now we set the right side equal to zero to find the best probability
$p$:

\begin{eqnarray*}
n (1-p)^{n-1} & = & n p (n-1) (1-p)^{n-2} \\
(1-p) & = & p (n-1) \\
p & = & 1 / n
\end{eqnarray*}

This answer makes sense, since we want the coin to come up heads
exactly 1 time in $n$.}

\ppart What is the probability of success if $p$ is chosen in this
way?  What quantity does this approach when $n$, the number of
Immortal Warriors, grows large?

\solution{Setting $p = 1/n$ in the formula for the probability that
the experiment succeeds gives:

\begin{eqnarray*}
\pr{E} & = & \left(1-\frac{1}{n}\right)^{n-1}
\end{eqnarray*}

In the limit, this tends to $1/e$.  McLeod is right.
}

\eparts

\end{problem}

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

\end{document}

