\documentclass[12pt]{article}
\usepackage{latex-macros/course}

%\hidesolutions
%\showsolutions

\begin{document}

\inclassproblems{12, Wed.}

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

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

\begin{problem}
A Barglesnort makes its lair in one of three caves:
%
\begin{center}
\includegraphics[height=0.75in]{figures/caves}
\end{center}
%
The Barglesnort inhabits cave 1 with probability $1/2$, cave 2
with probability $1/4$, and cave 3 with probability
$1/4$.  A rabbit subsequently moves into one of the two
unoccupied caves, selected with equal probability.  With probability
$1/3$, the rabbit leaves tracks at the entrance to its cave.
(Barglesnorts are much too clever to leave tracks.)  What is the
probability that the Barglesnort lives in cave 3, given that there are
no tracks in front of cave 2?

\noindent
Use a tree diagram and the four-step method.
\end{problem}

\solution{A tree diagram is given below.  Let $B_3$ be the event that
the Barglesnort inhabits cave 3, and let $T_2$ be the event that there
are tracks in front of cave 2.  Taking data from the tree diagram, we
can compute the desired probability as follows:
%
\begin{align*}
\pr{B_3 \mid \overline{T_2}}
	& = \frac{\pr{B_3 \cap \overline{T_2}}}{\pr{\overline{T_2}}} \\
	& = \frac{\frac{1}{24} + \frac{1}{12} + \frac{1}{12}}
		{1 - \frac{1}{12} - \frac{1}{24}} \\
	& = \frac{5}{21}
\end{align*}
%
In the denominator, we apply the formula $\pr{\overline{T_2}} = 1 -
\pr{T_2}$ for convenience.
%
\begin{center}
\includegraphics[height=4in]{figures/bargle}
\end{center}
}

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



\begin{problem}
There is a rare and deadly disease called \textit{Nerditosis} which
afflicts about 1 person in 1000.  One symptom is a compulsion to refer
to everything--- fields of study, classes, buildings, etc.--- using
numbers.  It's horrible.  As victims enter their final, downward
spiral, they're awarded a degree from MIT.  Two doctors claim that
they can diagnose Nerditosis.

\bparts

\ppart Doctor $X$ received his degree from Harvard Medical School.  He
practices at Massachusetts General Hospital and has access to the
latest scanners, lab tests, and research.  Suppose you ask Doctor $X$
whether you have the disease.
%
\begin{itemize}
\item If you have Nerditosis, he says ``yes'' with probability 0.99.
\item If you don't have it, he says ``no'' with probability 0.97.
\end{itemize}
%
Let $D$ be the event that you have the disease, and let $E$ be the
event that the diagnosis is erroneous.  Use the Total Probability Law
to compute $\pr{E}$, the probability that Doctor $X$ makes a mistake.

The Total Probability Law is 
\begin{equation*}
\pr{A} = \prcond{A}{E} \cdot \pr{E} +
         \prcond{A}{\overline{E}} \cdot \pr{\overline{E}}.
	 \end{equation*}


\solution{By the Total Probability Law:
%
\begin{align*}
\pr{E}
    & = \pr{E \mid D} \cdot \pr{D} +
        \pr{E \mid \overline{D}} \cdot \pr{\overline{D}} \\
    & = 0.01 \cdot 0.001 + 0.03 \cdot 0.999 \\
    & = 0.02998
\end{align*}}

\ppart ``Doctor'' $Y$ received his genuine degree from a
fully-accredited university for \$49.95 via a special internet offer.
He knows that Nerditosis stikes 1 person in 1000, but is a little
shakey on how to interpret this.  So if you ask him whether you have
the disease, he'll helpfully say ``yes'' with probability 1 in 1000
regardless of whether you actually do or not.

Let $D$ be the event that you have the disease, and let $F$ be the
event that the diagnosis is faulty.  Use the Total Probability Law to
compute $\pr{F}$, the probability that Doctor $Y$ made a mistake.

\solution{By the Total Probability Law:
%
\begin{align*}
\pr{F}
    & = \pr{F \mid D} \cdot \pr{D} +
        \pr{F \mid \overline{D}} \cdot \pr{\overline{D}} \\
    & = 0.999 \cdot 0.001 + 0.001 \cdot 0.999 \\
    & = 0.001998
\end{align*}}

\ppart Which doctor is more reliable?

\solution{Doctor $X$ makes more than 15 times as many errors as Doctor
$Y$.}

\eparts
\end{problem}

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

\begin{problem} 
Suppose there is a system with $n$~components, and we know from past
experience that any particular component will fail in a given year with
probability~$p$.  That is, letting $F_i$ be the event that the $i$th
component fails within one year, we have
\[
\pr{F_i} = p
\]
for $1 \leq i \leq n$.  The \emph{system} will fail if \emph{any one} of
its components fails.  What can we say about the probability that the
system will fail within one year?

Let $F$ be the event that the system fails within one year.  Without any
additional assumptions, we can't get an exact answer for $\pr{F}$.
However, we can give useful upper and lower bounds, namely,
\begin{equation}\label{pFnp}
p \le \pr{F} \le np.
\end{equation}
So for example, if $n = 100$ and $p = 10^{-5}$, we conclude that there is
at most one chance in 1000 of system failure within a year and at least
one chance in 100,000.

Let's model this situation with the sample space $\sspace \eqdef
\power(\set{1, \dots,n})$ of subsets of positive integers $\le n$, where
$s \in \sspace$ corresponds to the indices of the components which fail
within one year.  For example, $\set{2, 5}$ is the outcome that the second
and fifth components failed within a year and none of the other components
failed.  So the outcome that the system did not fail corresponds to the
emptyset, $\emptyset$.

\bparts

\ppart Show that the probability that the system fails could be as small
as $p$ by describing appropriate probabilities for the sample points.

\solution{There could be a probability $p$ of system failure if the all
individual failures occur together.  That is, let $\pr{\set{1, \dots,n}}
\eqdef p$, $\pr{\emptyset} \eqdef 1-p$, and let the probability of all
other outcomes be zero.  So $F_i = \set{s \in \sspace \suchthat i \in s}$
and $\pr{F_i} = 0 + 0 + \dots + 0 + \pr{\set{1, \dots,n}} = \pr{\set{1,
\dots ,n}} = p$.  Also, the only outcome with positive probability in $F$
is $\set{1, \dots ,n}$, so $\pr{F} = p$, as required.}

\ppart Show that the probability that the system fails could actually
could be as large as $np$ by describing appropriate probabilities for the
sample points.

\solution{Suppose at most one component ever fails at a time.  That is,
$\pr{\set{i}}=p$ for $1 \le i \le n$, $\pr{\emptyset}=1-np$, and
probability of all other points is zero.  The sum of the probabilities of
all the points is one, so this is a well-defined probability space.  Also,
the only sample point in $F_i$ with positive probability is $\set{i}$, so
$\pr{F_i} = \pr{\set{i}} = p$ as required.  Finally, $\pr{F} = np$ because
$F = \set{A \subseteq \set{1,\dots,n} \suchthat A \neq \emptyset}$, so $F$
in particular contains all the $n$ outcomes of the form $\set{i}$.}

\ppart Prove the inequality~(\ref{pFnp}).

\solution{
$F = \lgunion_{i=1}^n F_i$ so
\begin{align}
p & = \pr{F_1} & \text{(given)}\\
& \le \pr{F} = \pr{\lgunion F_i} & \text{(def. of $F$)} \\
& \le \sum_{i=1}^n \pr{F_i} & \text{(Union bound)}\\
& = np.
\end{align}
}

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

