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

%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\begin{document} 
\inclassproblems{8}

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

\begin{problem}
You have two decks of cards.  One of them is complete, but one of them
is missing the ace of spades.  You do not remember which is which.
You pick a deck at random and pull out a card uniformly at random.  If
that card is the seven of hearts, what is the probability that you are
holding the complete deck?

\solution{Let $C$ be the event that you are holding the complete deck,
and let $H$ be the event that you draw the seven of hearts.  We want
to compute:

\begin{eqnarray*}
\pr{C \mid H}
	& = &	\frac{\pr{C \cap H}}{\pr{H}} \\
	& = &	\frac{\pr{H \mid C} \cdot \pr{C}}
			{\pr{H \mid C} \cdot \pr{C} +
			\pr{H \mid \overline{C}} \cdot \pr{\overline{C}}}
\end{eqnarray*}

The probability of drawing the seven of hearts is $1/52$, given that
you selected the complete deck, and $1/51$, given that you selected
the incomplete one.  Since a deck was selected at random, we have
$\pr{C} = \pr{\overline{C}} = 1/2$.  Plugging these numbers into the
formula above, we find:

\begin{eqnarray*}
\pr{C \mid H}
	& = &	\frac{1/52 \cdot 1/2}
			{1/52 \cdot 1/2 + 1/51 \cdot 1/2} \\
	& = &	\frac{51}{103}
\end{eqnarray*}

When we pull a seven of hearts from a deck chosen at random, the
probability that the deck is complete is about $49.5\%$.  As we would
intuitively expect, this is just under $50\%$.}
\end{problem}

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

\newcommand{\says}[1]{S_{#1}}

\begin{problem}
There is a robbery.  The thief gets away, but there is a witness who
says that the culprit is black.  Subsequent recreations show that
this witness is quite reliable.  In particular:

\begin{itemize}

\item In recreations where the thief is white, the witness says
``white'' 90\% of the time and ``black'' 10\% of the time.

\item In recreations where the thief is black, the witness says
``black'' 90\% of the time and ``white'' 10\% of the time.

\end{itemize}

\bparts

\ppart A reporter concludes that there is a 90\% chance that the real
thief is black.  Explain the reporter's error in terms of conditional
probability, where $B$ is the event that the thief is black and
$\says{B}$ is the event that the witness {\em says} the thief is black.

\solution{The recreations show that:

\begin{eqnarray*}
\pr{\says{B} \mid B} & = & 0.90
\end{eqnarray*}

From this, the reporter erroneously concludes that:

\begin{eqnarray*}
\pr{B \mid \says{B}} & = & 0.90
\end{eqnarray*}

However, these two probabilities are generally not equal.
}

\ppart Here is some additional information.  The thief is someone
selected uniformly at random from the populace of the city, which is
95\% white and 5\% black.  What is the probability that the thief is
black, given that the witness says he was?  (Draw a tree diagram.)

\solution{
Here is a tree diagram for the problem:

\bigskip
\centerline{\includegraphics[height=2.5in]{witness}}
\bigskip

Now we can compute the probability as follows:

\begin{eqnarray*}
\pr{B \mid \says{B}}
	& = &	\frac{\pr{B \cap \says{B}}}{\pr{\says{B}}} \\
	& = &	\frac{9/200}{9/200 + 19/200} \\
	& = &	9/28
\end{eqnarray*}

Thus, the probability that the thief is black is less than 1 in 3.
}

\ppart Let's consider the reverse situation.  If the witness says that
the thief is white, what is the probability that the thief is actually
white?

\solution{
Let $W$ be the event that the thief is white, and $\says{W}$ be the event that the witness says the thief is white.

\begin{eqnarray*}
\pr{W \mid \says{W}}
	& = &	\frac{\pr{W \cap \says{W}}}{\pr{\says{W}}} \\
	& = &	\frac{171/200}{171/200 + 1/100} \\
        & = &   \frac{171}{172}
\end{eqnarray*}

If the witness says that the culprit is white, there's a greater
than 99\% chance that he actually is!
}

\ppart Call your TA over and {\underline {\em pretend}} that he or she
is pretty much a blathering idiot.  Try to explain this strange
phenomenon in non-mathematical terms.

\solution{Here is one attempt.  There are two reasons why the witness
might say that that the culprit is black:

\begin{enumerate}

\item The thief is black and the witness was correct.

\item The thief is white and the witness was wrong.

\end{enumerate}

Because the vast majority of thieves are white, the second possibility
is much more likely, even though the witness is generally reliable.
Therefore, the thief is probably white.

On the other hand, there are also two reasons why the witness might
say that the culprit is white:

\begin{enumerate}

\item The thief is black and the witness was wrong.

\item The thief is white and the witness was correct.

\end{enumerate}

In this case, the first possibility is a combination of two very
unlikely events: the thief is black (1 in 20) and the witness was
wrong (1 in 10).  On the other hand, the second possibility is a
combination of two very likely events: the thief is white (19 in 20)
and the witness was right (9 in 10).  Therefore, the second
possibility is overwhelmingly more probable, and so the thief is
almost certainly white.}

\eparts

\end{problem}

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

\begin{problem}
There are \underline{two} of us, but there is only \underline{one}
cookie.  We could flip a coin to decide who gets the cookie, but the
only coin we have comes up heads with probability $2 / 3$.

\bparts

\ppart Suppose that we flip the coin exactly $n$ times.  What is the
sample space for this experiment?

\solution{The sample space consists of all length-$n$ sequences of H's
and T's, which is the set $\{ H, T \}^n$.}

\ppart What is the probability of each outcome?

\solution{Each outcome with $h$ heads and $n - h$ tails has
probability:

\[
\left(\frac{2}{3}\right)^h \left(\frac{1}{3}\right)^{n-h}
\]
}

\ppart No event in this probability space has probability exactly $1 /
2$.  Why?  (Remember that an event is a set of outcomes, and the
probability of an event is the sum of the outcome probabilities.)

\solution{The probability of each outcome is an integer multiple of
$1/3^n$.  Therefore, no set of outcomes can have probability

\begin{eqnarray*}
\frac{1}{2} & = & \frac{3^n / 2}{3^n}
\end{eqnarray*}

\noindent because the numerator is not an integer.
}

\ppart How can we use the coin to fairly decide who gets the cookie,
despite this?  Argue that your procedure terminates eventually with
probability 1.

\solution{Flip the coin twice.  On result HT, I get the cookie.  On
result TH, you get the cookie.  On result TT or HH, we redo the
experiment.  The game is fair, because on each trial we have an equal
chance of winning:

\begin{eqnarray*}
\frac{1}{3} \cdot \frac{2}{3} & = & \frac{2}{9}
\end{eqnarray*}

The probability that one round does not produce a winner is:

\begin{eqnarray*}
\pr{\text{no winner}}
	& = &	\pr{HH} + \pr{TT} \\
	& = &	\left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 \\
	& = &	\frac{5}{9}
\end{eqnarray*}

The probability that $n$ consecutive rounds fail to produce a winner
is $(5 / 9)^n$.  As number of rounds ($n$) goes to infinity, this
quantity tends to zero.  Therefore, the probability that the procedure
never terminates is 0, and so the probability that the procedure
eventually terminates is 1.}

\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 provocative discussion of the cookie problem, they opt to give
the following probabilistic 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 carefully.  What does your intuition tell you?

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

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