\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Course notes on probability.}

\begin{document}
\problemset{11}

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

\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 Explain this strange phenomenon in terms that you think a
non-mathematician could understand.

\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}
Philo T. Megabrain, a noted parapsychology researcher, has discovered
an amazing phenomenon!  He puts a psychic on each side of an opaque,
soundproof barrier.  Each psychic rolls a fair die, looks at it, and
tries to guess what number came up on the \textit{other} die by
telepathy.  Since the dice are fair and independent, the psychics
should guess correctly only 1 time in 6.  However, after extensive
testing, Philo has discovered that they actually do {\em slightly}
better.

\bparts

\ppart Philo's somewhat-arbitrary policy is to run the test over and
over each day until both psychics roll a 6 at the same time.  Then he
immediately halts testing for the day, before the psychics make
guesses.  What is the expected number of guesses that each psychic
makes in a single day?

\solution{The probability of rolling two sixes is $1/6 \cdot 1/6 =
1/36$.  Therefore, the expected number of rolls until two sixes are
obtained in 36.  However, the psychics are not permitted to guess when
two sixes are rolled, so they make 35 guesses on average.}

\ppart Explain the flaw in Philo's experiment in qualitative terms.

\solution{If a psychic sees a 6 on her own die, she knows not to guess
that the other die is a 6.}

\ppart If a psychic exploits this flaw optimally, with what probabilty
can she guess the number on the opposite die?

\solution{If she sees a 1, 2, 3, 4, or 5, then her probability of
guessing the other die is the normal $1 / 6$.  However, if she sees a
6, then she knows that the other die is \textit{not} a 6, and so her
probability of guessing the other die is $1/5$.  By the total
probability law, her probability of guessing the other die correctly
in general is:

\begin{equation*}
\frac{5}{6} \cdot \frac{1}{6} + \frac{1}{6} \cdot \frac{1}{5} = \frac{31}{180}
\end{equation*}
}

\eparts

\end{problem}

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

\begin{problem}
Let $A$ be a natural-valued random variable.  The \textit{probability
generating function} for $A$ is:

\begin{equation*}
G_A(x) = \pr{A = 0} + \pr{A = 1} \cdot x + \pr{A = 2} \cdot x^2 + \pr{A = 3} \cdot x^3 + \ldots
\end{equation*}

\bparts

\ppart Write $\Ex(A)$ in terms of $G_A$.

\solution{Differentiating gives:

\begin{equation*}
G'_A(x) = 1 \cdot \pr{A = 1} + 2 \cdot \pr{A = 2} \cdot x + 3 \cdot \pr{A = 3} \cdot x^2 + \ldots
\end{equation*}

Evaluating at $x = 1$ gives:

\begin{equation*}
G'_A(1) = \pr{A = 1} + 2 \cdot \pr{A = 2} + 3 \cdot \pr{A = 3} + \ldots
\end{equation*}

Thus, $G_A'(1) = \expect{A}$.
}

\ppart Suppose that $A$ and $B$ are both natural-valued random
variables.  What random variable has probability generating function
$G_A \cdot G_B$?

\solution{For notational compactness, let $a_i = \pr{A = i}$ and $b_i
= \pr{B = i}$.  Multiplying the power series $G_A$ and $G_B$ and then
grouping terms of the same degree gives:

\begin{align*}
G_a \cdot G_b
  & = a_0 b_0 + (a_0 b_1 + a_1 b_0) x + (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 + \ldots \\
  & = \pr{A + B = 0} + \pr{A + B = 1} \cdot x + \pr{A + B = 2} \cdot x^2 + \ldots
\end{align*}

Thus, $G_A \cdot G_B$ is the generating function for $A + B$, provided
that $A$ and $B$ are independent.}

\ppart \textbf{(challenge) } Suppose that $A$ and $B$ are independent,
natural-valued random variables.  What random variable has probability
generating function $G_A \circ G_B$?  (Here $\circ$ denotes
function composition.)

\solution{
We have:

\begin{align*}
G_A(x) & = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots \\
G_B(x) & = b_0 + b_1 x + b_2 x^2 + b_3 x^3 + \ldots
\end{align*}

Thus, composition gives:

\begin{eqnarray*}
G_A(G_B(x)) & = & a_0 \\
            &   & + a_1 (b_0 + b_1 x + b_2 x^2 + \ldots) \\
            &   & + a_2 (b_0 + b_1 x + b_2 x^2 + \ldots)^2 \\
            &   & + a_3 (b_0 + b_1 x + b_2 x^2 + \ldots)^3 \\
            &   & + \ldots
\end{eqnarray*}

Multiplying out and grouping terms of the same degree gives:

\begin{eqnarray*}
G_A(G_B(x)) & = & a_0 + a_1 b_0 + a_2 b_0^2 + a_3 b_0^3 + \ldots \\
            &   & + (a_1 b_1 + a_2 (b_0 b_1 + b_1 b_0) + \ldots) \cdot x \\
            &   & + (a_1 b_2 + a_2 (b_0 b_2 + b_1 b_1 + b_2 b_0 \ldots) + \ldots) \cdot x^2 \\
            &   & + \ldots
\end{eqnarray*}

Thus, $G_A \circ G_B$ is the generating function for $B_1 + \ldots +
B_A$, assuming $A, B_1, B_2, \ldots$ are all independent.}

\eparts

\end{problem}

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

\begin{problem}

Here is a typical 3-CNF formula:

\[
(x_1 \vee x_3 \vee \neg x_7) \wedge
(\neg x_5 \vee x_6 \vee x_7) \wedge
(x_2 \vee \neg x_4 \vee x_6) \wedge
(\neg x_4 \vee x_5 \vee \neg x_7) \wedge
(x_3 \vee \neg x_5 \vee \neg x_8)
\]

In general, a {\em 3-CNF formula} is the logical ``and'' of $n$
clauses, where each clause is the logical ``or'' of three terms, and
each term is either a variable or its negation.  The terms in a single
clause must involve distinct variables; thus, for example, $(x_1 \vee
\neg x_1 \vee x_2)$ is not a legal clause.

\textsc{Max-3SAT} is a classic computational problem: given a 3-CNF
formula, find an assignment to the variables that makes as many
clauses as possible true.

\bparts

\ppart Suppose that each variable in the example above is true with
probability $1/2$ and false with probability $1/2$ independently.
What is the expected number of clauses that are true?  (Hint: This
problem does {\em not} require intricate calculations.)

\solution{Let $I_k$ be an indicator for the event that the $i$-th
clause is true.  Then $\pr{I_k = 1} = 7 / 8$, since there are 8
equally-probably assignments to the variables in the clause and 7 of
these make the clause true.  Therefore, the expected number of true
clauses is:

\begin{align*}
\expect{I_1 + \ldots I_5}
    & = \expect{I_1} + \ldots \expect{I_5} \\
    & = \pr{I_1 = 1} + \ldots \pr{I_5 = 1} \\
    & = 5 \cdot \frac{7}{8} \\
    & = \frac{35}{8}
\end{align*}
}

\ppart Prove that for every 3-CNF formula with $n$ clauses, there is
an assignment that makes at least $\frac{7n}{8}$ clauses true.

\solution{By the reasoning above, a random assignment makes $\frac{7n}{8}$
of the clauses true.  Therefore, some assignment must make at least 
$\frac{7n}{8}$ of the clauses true, much as some student must score at least
the class average on an exam.}

\eparts

\end{problem}

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

\begin{problem} Each 6.042 final exam will be graded according to a
rigorous procedure:

\begin{itemize}

\item With probability $\frac{4}{7}$ the exam is graded by a {\em TA},
with probability $\frac{2}{7}$ it is graded by a {\em lecturer}, and
with probability $\frac{1}{7}$, it is accidentally dropped behind the
radiator and arbitrarily given a score of 84.

\item {\em TAs} score an exam by scoring each problem individually and
then taking the sum.

\begin{itemize}

\item There are ten true/false questions worth 2 points each.  For
each, full credit is given with probability $\frac{3}{4}$, and no
credit is given with probability $\frac{1}{4}$.

\item There are four questions worth 15 points each.  For each, the
score is determined by rolling two fair dice, summing the results, and
adding 3.

\item The single 20 point question is awarded either 12 or 18 points
with equal probability.

\end{itemize}

\item {\em Lecturers} score an exam by rolling a fair die twice,
multiplying the results, and then adding a ``general impression''
score.

\begin{itemize}

\item With probability $\frac{4}{10}$, the general impression score is 40.

\item With probability $\frac{3}{10}$, the general impression score is 50.

\item With probability $\frac{3}{10}$, the general impression score is 60.

\end{itemize}

\end{itemize}

Assume all random choices during the grading process are independent.

\bparts

\ppart What is the expected score on an exam graded by a TA?

\solution{ Let the random variable $T$ denote the score a TA would
give.  By linearity of expectation, the expected sum of the problem
scores is the sum of the expected problem scores.  Therefore, we have:
\begin{eqnarray*}
\expect{T}	& = &	10 \cdot \expect{\text{T/F score}} +
		4 \cdot \expect{\text{15pt prob score}} +
		\expect{\text{20pt prob score}} \\
	& = &
	10 \cdot \left(\frac{3}{4} \cdot 2 + \frac{1}{4} \cdot 0 \right)
	+ 4 \cdot \left( 2 \cdot \frac{7}{2} + 3 \right)
	+ \left(\frac{1}{2} \cdot 12 + \frac{1}{2} \cdot 18 \right) \\
	& = &	10 \cdot \frac{3}{2} + 4 \cdot 10 + 15 \\
	& = & 	70
\end{eqnarray*}
}

\ppart What is the expected score on an exam graded by a
lecturer?

\solution{
Now we find the expected value of $L$, the score a lecturer would
give.  Employing linearity again, we have:
\begin{eqnarray*}
\expect{L}	& = &	\expect{\text{product of dice}} + \expect{\text{general impression}} \\
	& = &	\left(\frac{7}{2}\right)^2 + \left(
		\frac{4}{10} \cdot 40 + 
		\frac{3}{10} \cdot 50 + 
		\frac{3}{10} \cdot 60 \right) \\
	& = &	\frac{49}{4} + 49 \\
	& = &	61 \frac{1}{4}
\end{eqnarray*}
}

\ppart What is the expected score on a 6.042 final exam?

\solution{Let $X$ equal the true exam score.  The total expectation
law implies:
\begin{eqnarray*}
\expect{X}	& = &	\frac{4}{7} \cdot \expect{T} +
		\frac{2}{7} \cdot \expect{L} +
		\frac{1}{7} \cdot 84 \\
	& = &	\frac{4}{7} \cdot 70 +
		\frac{2}{7} \cdot \left(\frac{49}{4} + 49\right) +
		\frac{1}{7} \cdot 84 \\
	& = &	40 + \frac{7}{2} + 14 + 12 \\
	& = &	69 \frac{1}{2}
\end{eqnarray*}
}

\eparts

\end{problem}

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

\begin{problem}
You shuffle a deck of cards and deal your friend a 5-card hand.

\bparts

\ppart Suppose your friend says, ``I have the ace of spaces.''  What
is the probablity that she has another ace?
\solution{
This is the same as the probability that you will deal an ace in 4
cards in a deck missing the ace of spades. This is equal to:

\[
1-\frac{48}{51}*\frac{47}{50}*\frac{46}{49}*\frac{45}{48}=.2214\ldots
\]

Another way of solving this problem is to count! The number of
hands that have ace of spades is equal to:
$\binom{51}{4}$ and the number of hands that have the ace of
spades and at least another ace is equal to: 

\[
\binom{3}{1}*\binom{48}{3}+\binom{3}{2}*\binom{48}{2}+48
\]

So, the probability that, given she has the ace of spades, that she
has another ace is equal to:

\[
\frac{\binom{3}{1}*\binom{48}{3}+\binom{3}{2}*\binom{48}{2}+48}{\binom{51}{4}}=.2214\ldots
\]
}

\ppart Suppose your friend says, ``I have an ace.''  What is the
probability that she has another ace?

\solution{ Counting is the simplest way to solve this problem. The total number
of hands that contain at least 1 ace is equal to:
$$\binom{4}{1}*\binom{48}{4}+\binom{4}{2}*\binom{48}{3}+\binom{4}{3}*\binom{48}{2}+48$$
and the number of hands that have 2 or more aces is equal to:
$$\binom{4}{2}*\binom{48}{3}+\binom{4}{3}*\binom{48}{2}+48$$
So the probability is equal to:
.12285
}

\ppart Explain why these two answers are different.
\solution{
The number of hands that contain two aces, but no ace of spades, and
the hands that contain a single ace that isn't the ace of spades account
for the difference between the two answers. There are $\binom{48}{4}*3$ more hands
with just a single ace in the second case. The number of hands with 
pairs of aces, however, is $\binom{3}{2}*\binom{48}{3}$ and the
number of hands with three aces without the ace of spades is:
$\binom{48}{2}$. The number of hands with just a single ace is
much much larger now, where as the number of hands with pairs or 3 of
a kinds is not so much larger.
}

\eparts

\end{problem}

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

\begin{problem}
Earlier in the course, we generated a set $S$ consisting of 77
twenty-one digit numbers.  We used the pigeonhole principle to prove
that two distinct subsets of the numbers in $S$ have the same sum.
Actually finding two such sets is quite difficult.  Naively, we could
sum the elements in all $2^{77}$ subsets and find two that match, but
this is a huge computational task.

Recall the birthday principle: If there are $d$ days in a year and
$\sqrt{2d}$ people in a room, then the probability that two share a
birthday is about $1 - 1/e = 0.632\ldots$.

How could the birthday principle help you find two distinct subsets of
$S$ with the same sum using fewer than $2^{77}$ operations?  What
assumptions must you make?  (This is intended to be an open-ended
question.)
\end{problem}

\solution{Assume that the sums are uniformly distributed, mutually
independent random variables taking on values in the range $\set{0, 77
\cdot 10^{21}}$.  Then we have a good chance of finding two subsets
with the same sum if the number of subsets we consider is about:

\begin{equation*}
\sqrt{2 \cdot 77 \cdot 10^21} \approx 4 \cdot 10^11
\end{equation*}

Of course, the sums are not uniformly distributed; in fact, the sum of
a random subset is likely to be close to the expected value.  This
nonuniformity only improves the computational picture, however.  (If
almost everyone were born in July, then then finding two people with
the same birthday would be easier.)

The sums are also not mutually independent.  However, if we sum a few
hundred billion selected at random, then the sets are likely to be
different enough that their sums are ``mostly kinda'' independent.

Overall, it seems that several billion sums should suffice to find two
subsets with the same sum.}

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

\end{document}





