\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{10}{November 21, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart 
In this case, you should always pick Box 1.  Monty (Prof. Leighton)
will be forced to reveal the location of the other ``Nerd Pride''
pocket protector.  Upon switching, you will be guaranteed to win the
ice cream (i.e.  the probability of winning is 1).  If you pick a box
besides 1, Monty can always reveal Box 1 (giving you no additional
information), and you will have a 1/2 chance of winning.

\ppart It is clear that the probability of winning for the ``don't switch'' 
strategy in this modified game is $1/3$, as before, since you have
only a $1/3$ probability of picking Box 1. Since in every game one of
the two strategies always wins it follows that the probablity of the
``switch'' strategy is $1 - 1/3 = 2/3$. Hence this modified game is
the ``same as'' the original game.
\ppart 
If you play the ``don't-switch strategy'', you will win whenever you
pick the correct box initially.  Thus, you will win with probability
1/3.  If you play the ``switch strategy'', you will lose every time
you initially pick the wrong box, since Monty can decide to end the game.
Everytime you pick the right box, Monty will reveal a bad box, and
then you will switch to a bad box.  Thus, you lose again.
Therefore, the probability of winning is 0 with the ``switch strategy''.

\eparts

\problem
\bparts
\ppart
\begin{enumerate}
\item {\em stick both times} You will win only if you pick the correct box initially.
This happens with probability 1/4.
\item {\em switch both times} 
You will win only if you have selected a bad box before the last
switch.  This can occur two different ways.
\begin{enumerate}
\item You first pick the good box and then switch to a bad box.
The probability of picking the good box is 1/4.
After your first switch, you will always pick a bad box.
\item You first pick a bad box (with probability 3/4) and then
switch to another bad box.  At this point, you have the choice
of switching to either the good box or another bad box.  The probability
of picking the bad box is 1/2.  Thus, the probability of this entire
event is 3/8.
\end{enumerate}
Therefore, the probability of winning with this strategy
is $1/4+3/8=5/8$.
\item {\em Stick the first time, switch the second time.}
Again, you will win if you have selected a bad box before the switch.
Since you stuck the first time, this occurs with probability 3/4.
\item {\em Switch the first time, stick the second time.} You will win if 
you switch onto the good box.  In order to do this, you must first
pick a bad box (with probability 3/4) and then switch onto the good
box (with probability 1/2).  Thus, your probability of winning is 3/8.
\end{enumerate}
By comparing probabilities, it is best to ``Stick the first time, and
switch the second''.  This strategy gives you a 3/4 chance of winning.
\ppart
No, the new information does not help you.  After you pick a door,
there are two doors left. If Monty reveals the higher of the two then
you should definitely switch. This ensures a win and happens $1/3$ of
the time. The remaining $2/3$s of the time, when he reveals the lower
of the two remaining doors, the prize is behind one of the two
unrevealed doors with equal probability. Hence you can win only $1/2$
the time in such situations (whether you decide to switch or
not). Thus your best probability of winning is $1\cdot(1/3) +
(1/2)\cdot(2/3) = 2/3 $. The new information does not help you improve
your chances of winning. In general, whatever the strategy of the
host, ``switch'' always wins $2/3$ of the time (and therefore change
wins $1/3$ of the time). This is because in the situation where you
choose a wrong door (which happens $2/3$ of the time) the host has no
choice and ``switch'' wins with probability $1$. In the situation
where you choose the right door the host has a choice but ``switch''
wins with probability $0$. Since you do not know which situation you
are in apriori you can do no better than $2/3$ and you can always do
this well.

\eparts

\problem
Let $B$ be the event the criminal has a beard.  Let $W$ be the
event the witness says the criminal has a beard.
We want to compute $Pr(B|W)$. Using the rules of conditional probability
\[
Pr(B|W)=\frac{Pr(W|B)Pr(B)}{Pr(W|B)Pr(B)+Pr(W|\overline{B})Pr(\overline{B})}
= \frac{(0.8)(.15)}{(0.8)(0.15)+(0.12)(0.85)} =0.54
\]

\problem
\begin{enumerate}

\item $A$ and $B^c$ are independent
\begin{eqnarray*}
P(A \cap B^c) & = & P(A) - P(A \cap B) \\
              & = & P(A) -P(A)P(B) \\
                          & = & P(A)(1 - P(B)) \\
                          & = & P(A)P(B^c)
\end{eqnarray*}

\item $A^c$ and $B^c$ are independent
\begin{eqnarray*}
P(A^c \cap B^c) & = & P((A \cup B)^c) \\
                & = & 1 - P(A \cup B) \\
                                & = & 1 - P(A) - P(B) + P(A \cap B) \\
                                & = & 1 - P(A) - P(B) + P(A)P(B) \\
                                & = & (1 - P(A))(1 - P(B)) \\
                                & = & P(A^c)P(B^c)
\end{eqnarray*}

\item $P(A^c \cap B \cap C) = P(A^c)P(B)P(C)$
 \begin{eqnarray*}
 P(A^c \cap B \cap C)& = &  P(A^c \cap (B \cap C)) \\
                &=& P(A^c \mid B \cap C) \cdot P(B \cap C) \\
                &=& (1-P(A \mid B \cap C)) \cdot P(B \cap C)\\
                &=& (1-P(A)) \cdot P(B) \cdot P(C)\\
                &=& P(A^c) \cdot P(B) \cdot P(C) 
\end{eqnarray*}

Here the second equality follows from the multiplication theorem. The third is
the property of conditional probability and the fourth is
 because $A,B,C$ are independent. Therefore, $A^c, B,C$ are independent.
 Given that $A, B, C$ are symmetric, it is
easy to see that $A, B^c,C$ or $A, B,C^c$ are also independent. 

\item $P(A \cap B^c \cap C^c) = P(A)P(B^c)P(C^c)$
\begin{eqnarray*}
P(A \cap B^c \cap C^c) & = & 1 - P(A^c \cup B \cup C)\\
                       & = & 1 - P(A^c) - P(B) - P(C) + P(A^c)P(B) +
                                                 P(A^c)P(C) \\
                                           &   & + P(B)P(C) - P(A^c)P(B)P(C) \\
                                           & = & P(A) - P(B) - P(C) + (1-P(A))P(B) +
                                                 (1-P(A))P(C) \\
                                           &   & + P(B)P(C) - (1-P(A))P(B)P(C) \\
                                           & = & P(A) - P(A)P(B) - P(A)P(C) + P(A)P(B)P(C) \\
                                           & = & P(A)(1-P(B))(1-P(C)) \\
                                           & = & P(A)P(B^c)P(C^c)
\end{eqnarray*}

\item $P(A^c \cap B^c \cap C^c) = P(A^c)P(B^c)P(C^c)$
\begin{eqnarray*}
P(A^c \cap B^c \cap C^c) & = & 1 - P(A \cup B \cup C) \\
                         & = & 1 - P(A) - P(B) - P(C) + P(A)P(B) + P(A)P(C) \\
                                                 &   & + P(B)P(C) - P(A)P(B)P(C) \\
                                                 & = & (1-P(A))(1-P(B))(1-P(C)) \\
                                                 & = & P(A^c)P(B^c)P(C^c)
\end{eqnarray*}

\end{enumerate}

Finally,
\begin{eqnarray*}
P(A \cap (B \cup C))& = & P((A \cap B) \cup (A \cap C)) \\
        &=& P(A \cap B) + P(A \cap C) - P((A \cap B) \cap (A \cap C))\\
        &=& P(A) \cdot P(B) + P(A) \cdot P(C) - P(A \cap (B \cap C))\\
        &=& P(A) \cdot (P(B) + P(C)) - P(A) \cdot P(B \cap C \mid A) \\
        &=& P(A) \cdot (P(B) + P(C) - P(B \cap C)) \\
        &=& P(A) \cdot P(B \cup C)
\end{eqnarray*}
Therefore, $A$  and $B \cup C$ are also independent.

\problem
He should put $1$ white ball in one pot and all the other balls in the
other.  That gives him a $\frac{1}{2}(1+\frac{49}{99}) = .747$ chance of
surviving.   To prove that this strategy is optimal, suppose he had decided
to put a total of $z$ balls into the first pot.  First note that $z>0$, since if
$z=0$, then he puts all balls into one pot. The probability of surviving
would  be at most $\frac{1}{2}$.  It would be $\frac{1}{2}$ if the king, on
seeing an empty pot just makes him choose from the full pot and
$\frac{1}{4}$ if the king chooses the empty pot (the rules
weren't entirely clear on what happens with an empty pot). This is clearly
dominated by the strategy we just described. Also, without loss of
generality, we can assume $z \leq 50$.(since any one pot has at most $50$
balls).  Suppose that the $z$ balls consist of $x$ white and $y$ black balls ($0
\leq x, y \leq z$). Then for any chosen $z$, the soldier needs to find the $x$ to
maximize  the probability of surviving.  If $F_z(x)$ is the probability of
surviving when we put $x$ white balls into the first pot (containing $z$
balls in all):

\[ 
F_z(x)= \frac{1}{2} \cdot \frac{x}{z}+  \frac{1}{2} \cdot \frac{50-x}{100-z} 
\]

Taking derivatives with respect to $x$, we get

\[ 
F'_z(x) =  \frac{1}{2} \cdot \left( \frac{1}{z}-\frac{1}{100-z}\right)
         = \frac{100-2z}{2z(100-z)} \geq 0 
\]

since we have assumed that $z \leq 50$.

Therefore, to maximize $F_z(x)$, we need to choose $x$ as large as possible.
So, taking $x=z$ would do the trick. Given that he always puts all white
balls in the first pot, the soldier needs to find the $z \leq 50$ to
maximize the probability of surviving: 

\[
S(z) =   \frac{1}{2} \cdot \left( \frac{z}{z}+\frac{50-z}{100-z} \right)
        = 1- \frac{50}{200-2z} 
\]

which clearly decreases with $z$. So the best strategy is to take $z$ as small
as possible. Therefore, $z=1$ would maximize his chance of surviving. 

\problem
False. The people that run the sweepstake do the following: they pick the
winner and then pair up the rest of the people. They then send the same
letter to each triple that consists of the winner and two other people.  So
does everyone who receives a letter have a $\frac{1}{3}$ chance of winning?
Of course not.  Lets formalize this:

\[\mbox{Prob} \{ \mbox{winning $\mid$ receive letter} \}  
        = \frac{\mbox{Prob} \{ \mbox{winning and receive letter} \}}
                {\mbox{Prob} \{\mbox{receive letter}\} } 
        =  \mbox{Prob} \{ \mbox{winning} \} \]
since the probability of receiving a letter is $1$.

\end{problems}

\end{document}





