\documentclass[11pt,twoside]{article}

\usepackage{latex-macros/course}

\begin{document} 
\inclassproblems{14, Mon.}

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

\begin{problem}
There are two decks of cards.  One is complete, but the other is
missing the ace of spades.  Suppose you pick one of the two decks with
equal probability and then select a card from that deck uniformly at
random.  What is the probability that you picked the complete deck,
given that you selected the eight of hearts?  Use the four-step method
and a tree diagram.

\solution[\newpage]{Let $C$ be the event that you pick the complete
deck, and let $H$ be the event that you select the eight of hearts.
In these terms, our aim is to compute:

\begin{equation*}
\prcond{C}{H} = \frac{\pr{C \cap H}}{\pr{H}}
\end{equation*}

A tree diagram is worked out below:

\bigskip
\centerline{\resizebox{!}{3in}{\includegraphics{incomplete-deck}}}
\bigskip

Now we can compute the desired conditional probability as follows:

\begin{align*}
\prcond{C}{H} & = \frac{\pr{C \cap H}}{\pr{H}} \\
              & = \frac{\frac{1}{2} \cdot \frac{1}{52}}
                       {\frac{1}{2} \cdot \frac{1}{52} +
                        \frac{1}{2} \cdot \frac{1}{51}} \\
              & = \frac{51}{103} \\
              & = 0.495146\ldots
\end{align*}

Thus, if you selected the eight of hearts, then the deck you picked is
more likely to be incomplete.}
\end{problem}

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

\begin{problem}
\begin{theorem*}[Bayes' Rule] If $A$ and $B$ are events with nonzero
probabilities, then:
\begin{equation*}
\prcond{A}{B} \cdot \pr{B} = \prcond{B}{A} \cdot \pr{A}
\end{equation*}
\end{theorem*}

\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} \\
\prcond{A}{B} \cdot \pr{B} & = \prcond{B}{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:
\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?

\solution[\newpage]{
\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!
}

\eparts

\end{problem}

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

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

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


\begin{problem}
There are three prisoners in a maximum-security prison for
supervillians: the Evil Wizard Voldemort, the Dark Lord Sauron, and
some guy named Darl McBride.  The parole board has declared that it
will release two of the three, chosen uniformly at random, but has not
yet released their names.  Naturally, Sauron figures that he will be
released to his home in Mordor, where the shadows lie, with
probability $\frac{2}{3}$.

A guard offers to tell Sauron the name of one of the other prisoners
who will be released (either Voldemort or Darl).  However, Sauron
declines this offer.  He reasons that if the guard says, for example,
``Darl will be released'', then his own probability of release will
drop to $\frac{1}{2}$.  This is because he will then know that either
he or Voldemort will also be released, and these two events are
equally likely.

Using conditional probability, either prove that the Dark Lord Sauron
has reasoned correctly or prove that he is wrong.  Assume that if the
guard has a choice of naming either Voldemort or Darl (because both
are to be released), then he names one of the two uniformly at random.
\end{problem}

\solution[\newpage]{Sauron has reasoned incorrectly.  His mistake is
not realizing that the event ``Darl will be released'' is different
from the event ``The guard says Darl will be released''.  The tree
diagram below shows that those two events are different sets of
outcomes.  The first split in the tree is based on which two of the
three prisoners are to be released, and the second is based on what
the guard tells Sauron.

\bigskip
\centerline{\resizebox{!}{2.8in}{\includegraphics{prison}}}
\bigskip

Taking probabilities from the tree diagram, we can compute Sauron's
true probabiliy of release as follows:

\begin{eqnarray*}
\lefteqn{
\pr{\text{Sauron released} \mid \text{guard says ``Darl''}}} \hspace{1in} \\
	& = &	\frac{\pr{\text{Sauron released} \cap
			\text{guard says ``Darl''}}}
		{\pr{\text{guard says ``Darl''}}} \\
	& = &	\frac{1/3}{1/3 + 1/6} \\
	& = &	\frac{2}{3}
\end{eqnarray*}

Therefore, if the guard says that Darl McBride will be released, then
Sauron, Lord of Mordor, still has a $\frac{2}{3}$ chance of release.
}

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

\end{document}
