\documentclass[12pt,twoside]{article}
\input{macros-course}

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{2}{February 11, 2003}{Start of class on Tuesday, February 25}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

\begin{problems}

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

\problem Suppose that {\em Let's Make a Deal} is played according to
different rules.  Now there are \underline{four} doors, with a prize
hidden behind one of them.  The contestant is allowed to pick a door.
Carol must then reveal a different door that has no prize behind it.
The contestant is allowed to stay with his or her original door or to
pick one of the other two that are still closed.  If the contestant
chooses the door concealing the prize in this second stage, then he or
she wins.

\begin{problemparts}

\problempart Contestant Stu, a sanitation engineer from Trenton, New Jersey,
stays with his original door.  What is the probability that he wins
the prize?

\solution{Stu guesses the right door initially with probability
$\frac{1}{4}$ and guesses the wrong door with probability
$\frac{3}{4}$.  If he was right initially, then he surely wins the
prize.  If he was wrong initially, then he surely does not win the
prize.  Therefore, his probability of winning is $\frac{1}{4} \cdot 1
+ \frac{3}{4} \cdot 0 = \frac{1}{4}$.
}

\problempart Contestant Zelda, an alien abduction researcher from Helena,
Montana, randomly picks one of the other two doors with equal
probability.  What is the probability that she wins the prize?

\solution{Zelda also guesses the right door initially with probability
$\frac{1}{4}$ and guesses the wrong door with probability
$\frac{3}{4}$.  If she was right initially, then she can not win.  If
she was wrong initially, then she wins with probability $\frac{1}{2}$.
Therefore, her probability of winning is $\frac{1}{4} \cdot 0 +
\frac{3}{4} \cdot \frac{1}{2} = \frac{3}{8}$.
}

\end{problemparts}

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

\problem Inspector Lestrade is waiting for Holmes and Watson, who are
driving (separately) to meet him.  It is a winter day, which means
that the roads have a 70\% chance of being icy.  Lestrade's secretary
informs him that Watson has had a car accident.  Lestrade figures that
each driver has an 80\% chance of an accident if the roads are icy,
and a 10\% chance of an accident if they are not.  Given that the
roads are icy, the event that Watson has an accident is independent of
the event that Holmes has an accident.  Given that the roads are not
icy, these events are again independent.

\begin{problemparts}

\problempart ``Probably the roads are icy'', Lestrade says.  What is
the actual probability that the roads are icy, given that Watson had
an accident?

\solution{In this question, we shall find that knowing that Watson has
had an accident, the probability that the roads are icy is about
94.9\%. We could solve this problem in two ways: using a tree diagram,
or using conditional probability formulas.  We shall use the
conditional probability method, for variety.

Let $I$ be the event ``the road is icy'', and $W$ be the event
``Watson has an accident''.  In this question, we want to know the
probability that the road is icy, knowing that Watson had an
accident. By applying the definition of conditional probability twice,
we get

\beqn
\pr{I \mid W}
	& = &	\frac{\pr{I \cap W}}{\pr{W}} \\
	& = &	\frac{\pr{W \mid I} \cdot \pr{I}}{\pr{W}}
\eeqn

In this expression, we know that $\pr{W \mid I} = 0.8$ and $\pr{I} =
0.7$.  We still need to compute $\pr{W}$. We do so using the total
probability law from Problem~7:

\beqn
\pr{W}	& = &	\pr{W \mid I} \cdot \pr{I} +\
		\pr{W \mid \overline{I}} \cdot \pr{\overline{I}} \\
	& = &	0.8 \cdot 0.7 + 0.1 \cdot 0.3 \\
	& = &	0.59
\eeqn

Substituting this into our previous expression, we conclude:

\beqn
\pr{I \mid W}
	& = &	\frac{\pr{W \mid I} \cdot \pr{I}}{\pr{W}} \\
	& = &	\frac{0.8 \cdot 0.7}{0.59} \\
	& = &	0.949\ldots
\eeqn

Therefore, there is about a 94.9\% chance that the roads are icy,
knowing that Watson had an accident.
}

\problempart ``Therefore, Holmes will probably crash as well, and so I
can go to lunch'', he reasons.  What is the probability that Holmes
has an accident, given that Watson did?

\solution{Let $H$ be the event ``Holmes has an accident'', and define
events $W$ and $I$ as before.

\beqn
\pr{H \mid W}
	& = &	\frac{\pr{H \cap W}}{\pr{W}} \\
	& = &	\frac{	\pr{H \cap W \mid I} \pr{I} +
			\pr{H \cap W \mid \overline{I}} \pr{\overline{I}}}
		{\pr{W}} \\
	& = &	\frac{	\pr{H \mid I} \pr{W \mid I} \pr{I} +
			\pr{H \mid \overline{I}}
				\pr{W \mid \overline{I}} \pr{\overline{I}}}
		{\pr{W}} \\
	& = &	\frac{0.8 \cdot 0.8 \cdot 0.7 + 0.1 \cdot 0.1 \cdot 0.3}
			{0.59} \\
	& = &	0.764\ldots
\eeqn

The first step uses the definition of conditional expectation, and the
second usees the total probability law from Problem~7.  The third step
uses the independence assumptions.  All that remains is to plug in
values from the problem statement and the previous problem part.  We
conclude that if Watson has had an accident, then the probability of
Holmes having an accident is about 76.4\%.
}

\problempart ``If you look out your window, Inspector, you'll find
that the roads are not icy at all'', says his secretary.  What is the
probability that Holmes has an accident, given that Watson did, but
the roads are not icy?

\solution{When the roads are not icy, the events of Holmes and Watson
having accidents are independent. Therefore the probability of Holmes
having an accident is simply the probability that he has an accident
knowing that it not icy, which is 10\%.

We can prove this formally as follows:

\beqn
\pr{H \mid \overline{I} \cap W}
	& = &	\frac{\pr{H \cap \overline{I} \cap W}}
			{\pr{\overline{I} \cap W}} \\
	& = &	\frac{\pr{H \cap W \mid \overline{I}} \cdot \pr{\overline{I}}}
			{\pr{W \mid \overline{I}} \cdot \pr{\overline{I}}} \\
	& = &	\frac{\pr{H \cap W \mid \overline{I}}}
			{\pr{W \mid \overline{I}}} \\
	& = &	\frac{\pr{H \mid \overline{I}} \cdot \pr{W \mid \overline{I}}}
			{\pr{W \mid \overline{I}}} \\
	& = &	\pr{H \mid \overline{I}}
\eeqn

As expected, the probability of Holmes crashing, knowing that it is
not icy and that Watson has crashed, is 10\%.
}

\end{problemparts}

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

\problem There are three prisoners in a maximum-security penitentiary
for fictional villains: the Evil Wizard Voldemort, the Dark Lord
Sauron, and Little Bunny Foo-Foo.  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 Foo-Foo).  However, Sauron
declines the offer.  He reasons that if the guard says, for example,
``Little Bunny Foo-Foo 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 Foo-Foo (because both
are to be released), then he names one of the two uniformly at random.

\solution{Sauron has reasoned incorrectly.  His mistake is not
realizing that the event ``Foo-Foo will be released'' is different
from the event ``The guard says Foo-Foo 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{pset2-prob3.eps}}}
\bigskip

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

\beqn
\lefteqn{
\pr{\text{Sauron released} \mid \text{guard says ``Foo-Foo''}}} \hspace{1in} \\
	& = &	\frac{\pr{\text{Sauron released} \cap
			\text{guard says ``Foo-Foo''}}}
		{\pr{\text{guard says ``Foo-Foo''}}} \\
	& = &	\frac{1/3}{1/3 + 1/6} \\
	& = &	\frac{2}{3}
\eeqn

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

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

\problem Suppose that, on average, 5 men out of 100 and 25 women out
of 10,000 are colorblind.  A colorblind person is chosen uniformly at
random from a population with equal numbers of males and females.
What is the probability of that person being male?

\solution{We shall solve this problem using the tree diagram below:

\bigskip
\centerline{\resizebox{!}{3in}{\includegraphics{pset2-colorblind.eps}}}
\bigskip

Let $M$ be the event ``a person is a man'', and let $C$ be the event
``a person is colorblind''.  Working from the tree diagram, we can
compute the probability that a colorblind person is male as follows:

\beqn
\pr{M \mid C}
	& = & 	\frac{\pr{M \cap C}}{\pr{C}} \\
	& = &	\frac{1/40}{1/40 + 1/800} \\
	& = &	\frac{20}{21}
\eeqn
}

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

\problem You flip a penny, a dime, a nickel, and a quarter.  Assume
that the coins are perfectly fair and the outcome of one is unaffected
by the outcomes of the others.

\begin{problemparts}

\problempart What is the probability that you flip at least two heads,
given that some coin comes up heads?

\solution{iThe sample space for this experiment consists of sixteen
equally-lkely outcomes:

\beqn
\{H, T\}^4 & = & \{ HHHH, HHHT, HHTH, HHTT, HTHH, \ldots \}
\eeqn

The four symbols in each sequence specify what comes up on the penny,
dime, nickel, and quarter.  We can compute the desired probability as
follows:

\beqn
\lefteqn{\pr{\text{at least two heads} \mid \text{at least one head}}}
		\hspace{1in} \\
	& = &	\frac{\pr{\text{at least two heads}
			\cap \text{at least one head}}}
			{\pr{\text{at least one head}}} \\
	& = &	\frac{\pr{\text{at least two heads}}}
			{\pr{\text{at least one head}}}
\eeqn

There is at least one head in all but one of the sixteen outcomes
($TTTT$), and there are at least two heads in all but five of the
outcomes ($TTTT$, $TTTH$, $TTHT$, $THTT$, and $HTTT$).  Therefore, we
have:

\beqn
\lefteqn{\pr{\text{at least two heads} \mid \text{at least one head}}}
		\hspace{1in} \\
	& = &	\frac{\pr{\text{at least two heads}}}
			{\pr{\text{at least one head}}} \\
	& = &	\frac{11/16}{15/16} \\
	& = &	\frac{11}{15}
\eeqn

The probability of getting at least two heads, knowing that there is
at least one head is $\frac{11}{15} \approx 73.3\%$.}

\problempart What is the probability that you flip at least two heads,
given that the dime comes up heads?

\solution{
As before, we begin with the definition of conditional probability:

\beqn
\lefteqn{\pr{\text{at least two heads} \mid \text{dime is heads}}}
		\hspace{1in} \\
	& = &	\frac{\pr{\text{at least two heads}
			\cap \text{dime is heads}}}
			{\pr{\text{dime is heads}}}
\eeqn

In 8 out of 16 outcomes, the dime comes up heads.  In 7 of those
outcomes, there are at least two heads overall; the only exception is
$TTHT$.  Therefore, we have:

\beqn
\pr{\text{dime is heads}}
	& = & \frac{8}{16} \\
\pr{\text{at least two heads} \cap \text{dime is heads}}
	& = &	\frac{7}{16}
\eeqn

By plugging these numbers into the formula above, we conclude that:

\beqn
\lefteqn{\pr{\text{at least two heads} \mid \text{dime is heads}}}
		\hspace{1in} \\
	& = &	\frac{\pr{\text{at least two heads}
			\cap \text{dime is heads}}}
			{\pr{\text{dime is heads}}} \\
	& = &	\frac{7/16}{8/16} \\
	& = & \frac{7}{8}
\eeqn

So the odds of at least two coins being heads, knowing that the dime
is heads, are $\frac{7}{8} = 87.5\%$.
}

\end{problemparts}

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

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

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

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:

\beqn
\pr{C \mid H}
	& = &	\frac{1/52 \cdot 1/2}
			{1/52 \cdot 1/2 + 1/51 \cdot 1/2} \\
	& = &	\frac{51}{103}
\eeqn

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\%$.}

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


\problem The {\em Total Probability Law} is often helpful in
evaluating the probability of an event:

\begin{eqnarray*}
\Pr\{A\} & = & \Pr\{A \mid B \} \cdot \Pr\{ B \} +
               \Pr\{A \mid \overline{B} \} \cdot \Pr\{ \overline{B} \}
\end{eqnarray*}

Intuitively, this formula lets you break evaluation of the probability
of event $A$ into two cases: when event $B$ occurs and when it does
not.

\begin{problemparts}

\problempart Prove that this formula holds for arbitrary events $A$
and $B$ over a finite sample space.

\solution{Note that each outcome in the event $A$ is also either in
the event $B$ or in the event $\overline{B}$.  Therefore, we can
reason as follows:

\beqn
\pr{A}	& = &	\pr{A \cap B} + \pr{A \cap \overline{B}} \\
	& = &	\pr{A \mid B} \cdot \pr{B} +
		\pr{A \mid \overline{B}} \cdot \pr{\overline{B}}
\eeqn

The second step uses the definition of conditional probability.  Note
that the second step is valid only if $0 < \pr{B} < 1$, a condition we
inadvertantly omitted from the problem statement.

Our mistake raises an interesting point, however.  In many ways, one
is better off simply adopting the convention that $\pr{A \mid B} \cdot
\pr{B} = 0$ when $\pr{B} = 0$.  Then the equation

\beqn
\pr{A \cap B} & = & \pr{A \mid B} \cdot \pr{B}
\eeqn

holds unconditionally.  A similar ``undefined quantity times zero
equals zero'' convention is used routinely in the field of {\em
information theory}.  There, by convention, $x \log x$ is treated as 0
when $x = 0$.}

\problempart Suppose that you flip a fair coin.  If you get heads,
then you roll a six-sided die and take the result.  If you get tails,
then you roll two six-sided dice and take the sum as your result.
Overall, what is the probability that the result is 6?

\solution{This exercise is a simple application of the total probability
law. If $6$ is the event ``The result is 6'' and H is the event ``The coin
came up heads'' then we want to compute

\beqn
\pr{6} & = &	\pr{6 \mid H} \cdot \pr{H} +
		\pr{6 \mid \overline{H}} \cdot \pr{\overline{H}}
\eeqn

Most of these probabilities are given in the problem statement:
$\Pr\{H\}=\Pr\{\overline{H}\}=\frac{1}{2}$ and $\Pr\{6 \mid
H\}=\frac{1}{6}$.  The probability of getting a result of 6 when two
dice are rolled is slightly more involved as we must consider the
different ways that two dice can add up to 6. We shall simply
enumerate them: 1+5, 2+4, 3+3, 4+2, 5+1.  So there are 5 ways for the
sum of two dice to add up to 6, out of a total of $6 \times 6 = 36$
equally-probable outcomes. Therefore $\Pr\{6 \mid
\overline{H}\}=\frac{5}{36}$. We can now compute the answer:

\beqn
\pr{6}	& = &	\pr{6 \mid H} \cdot \pr{H} +
		\pr{6 \mid \overline{H}} \cdot \pr{\overline{H}} \\
	& = &	\frac{1}{6} \cdot \frac{1}{2} +
		\frac{5}{36} \cdot \frac{1}{2} \\
	& = &	\frac{11}{72}
\eeqn
}

\problempart Suppose that you carry out the experiment above and the
result is 6.  What is the probability that you flipped heads?

\solution{
We can reason as follows:

\beqn
\pr{H \mid 6}
	& = &	\frac{\pr{H \cap 6}}{\pr{6}} \\
	& = &	\frac{\pr{6 \mid H} \cdot \pr{H}}{\pr{6}} \\
	& = &	\frac{1/6 \cdot 1/2}{11/72} \\
	& = &	\frac{6}{11}
\eeqn

Knowing that the result is 6, the probability that heads was flipped
is about $54.5\%$. Since 6 is slightly more likely in the head case
than in the tail case, this result is as we would expect.}

\end{problemparts}

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

\problem In Ultimate Frisbee, first possession is determined by an
unusual procedure.  An opposing player flips two frisbees in the air
and then you call either ``same'' or ``different''.  The frisbees can
either fall the same way (both face up or both face down) or different
ways (one up and one down).  If your call is correct, you win the
toss.  Assume that the frisbees are identical, but far from fair.
Which call should you make and why?

\solution{ Let $p$ be the probability that a frisbee falls face up,
and $S$ be the event ``The frisbees fall the same way''. We can draw a
tree diagram that shows the different outcomes.

\bigskip
\centerline{\resizebox{!}{3.5in}{\includegraphics{pset2-prob8.eps}}}
\bigskip

This shows:

\beqn
\Pr\{S\}
	& = &	p^2 + (1-p)^2 \\
	& = &	2 p^2 - 2 p + 1 \\
	& = &	2 \left(p - \frac{1}{2}\right)^2 + \frac{1}{2}
\eeqn

From the last expression, we can conclude that $\Pr\{S\} >
\frac{1}{2}$ whenever $p \neq \frac{1}{2}$. So it would be a good idea
to call ``same'', if you want first possession.
}

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

\problem There is a $100 \times 100$ grid of points, a larger version
of the grid shown below:

\[
\begin{array}{ccccc}
\circ & \circ & \circ & \circ & \circ \\
\circ & \circ & \circ & \circ & \circ \\
\circ & \circ & \circ & \circ & \circ \\
\circ & \circ & \circ & \circ & \circ \\
\circ & \circ & \circ & \circ & \circ
\end{array}
\]

Suppose that you pick $n$ points from this grid independently and
uniformly at random.  (You might pick the same point more than once.)
Two points are said to be {\em conflicting} if they lie in either the
same row or the same column.  What is the smallest value of $n$ such
that the probability that there are two conflicting points is greater
than $\frac{1}{2}$?

\solution{This is similar to the birthday paradox problem. We could
solve it using similar reasoning, however we can actually reuse our
earlier result.  The key idea is that picking a point uniformly at
random in this grid is equivalent to picking a row and a column
independently and uniformly at random.

We can restate the problem from this new perspective.  Pick $n$ rows
and $n$ columns, independently and uniformly at random.  If some row
is picked more than once or some column is picked more than once, then
we have a conflict.  Otherwise, there is no conflict.  What is the
smallest value of $n$ such that the probability of a conflict is
greater than $\frac{1}{2}$?

We now have two independent birthday problems, one on the columns and
one on the rows.  Let $C$ be the event that no column is picked more
than once, let $R$ be the event that no row is picked more than once.
The probablity that there is no conflict is:

\beqn
\pr{\text{no conflict}}
	& = &	\pr{C \cap R} \\
	& = &	\pr{C} \cdot \pr{R} \\
	& = &	\left(\pr{C}\right)^2 \\
	& = &	\left(\prod_{i=1}^{n-1} \left(1-\frac{i}{100}\right)\right)^2
\eeqn

The second equation uses the fact that rows and columns are selected
independently, and so $C$ is independent of $R$.  The third equation
uses the fact that a conflict between rows is just as likely as a
conflict between columns.  In the final step, we plug in our solution
to the birthday problem.

For $n = 8$, this sum evaluates to about $56.3\%$.  For $n = 9$, it
evaluates to about $47.6\%$. Therefore, the probability that two
points in the original game conflict excedes 50\% as of $n=9$.

(Some students assumed that a point in the grid could be picked at
most once.  However, since the problem states that points are picked
{\em independently}, it must be possible to pick the same point
multiple times.)
}

\end{problems}
\end{document}

