\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}
% END PROBLEM



% FALL 2001 %

%twang
%PSET10 - last used Fall01
%LEARNING OUTCOMES: 8 (Calculate prob.)
%replaced b/c the solution was edited and a probability tree figure
%was added.
\problem
In London, half of the days have some rain. The weather forecaster is
correct 2/3 of the time -- i.e. the probability that it rains, given
that she has predicted that it will rain, and the probability that it
does not rain given that she has predicted that it does not rain, are
both equal to 2/3. When rain is forecast, Mr.Paddington takes his
umbrella. When rain is not forecast, he takes it with probability
1/3.
\bparts

\ppart Find the probability of the weather forecaster forecasting rain.
\solution{

\textbf{Solution:}
To compute this probability, first we define the following events:

\begin{eqnarray*}
F & \eqdef & \text{the weather forecaster forecasts rain},\\
R & \eqdef & \text{there is rain in London} ,\\
U & \eqdef & \text{Mr.Paddington takes his umbrella  }.
\end{eqnarray*}

Using the law of total probability, we have

\[
\prob{R} = \prob{R \mid F} \prob{F} + \prob{R \mid {\overline F}} \prob{{\overline F}}
\]
Plugging in values we get:
\begin{eqnarray*}
\frac{1}{2} &= & \frac{2}{3}\pr{F} +\frac{1}{3}\pr{{\overline F}}\\
&= & \frac{2}{3}\pr{F} + \frac{1}{3}(1-\pr{F}) \\
&= & \frac{1}{3}\pr{F} + \frac{1}{3}
\end{eqnarray*}

Therefore, $\pr{F} = \frac{1}{2}$.
}
\ppart Find the probability that Paddington has no umbrella, given that it rains.

\solnospace{We construct a tree as shown below.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=4in]{figures/Probability_Tree_Figure}
\end{center}
\caption{Probability Tree}
\label{fig:Probability_Tree_Figure}
\end{figure}

We wish to find
\begin{eqnarray*}
\prob{\text{no umbrella}  \mid \text{rain}}
  & = &\frac{\prob{\mbox{no umbrella} \wedge \mbox{rain}}}{\prob{\mbox{rain}}}\\
& = & \frac{1/9}{1/2} = 2/9.
\end{eqnarray*}
}

\ppart Find the probability that it doesn't rain, given that he brings his
umbrella.

\solnospace{
we wish to find
\begin{eqnarray*}
\prob{\text{no rain} \mid \text{umbrella}} & = &
 \frac{\prob{\mbox{no rain} \wedge \mbox{umbrella}}}{\prob{\mbox{umbrella}}}\\
& = & \frac{1/6 + 1/9}{1/9 + 1/6 + 1/3 + 1/18} = 5/12
\end{eqnarray*}
}
\eparts

%twang
%PSET10 - last used Fall01
%LEARNING OUTCOMES:1 (basic math concepts - prob.)
%                  8 (Calculate prob.)
%New problem on probability theory
\problem
\begin{theorem*}[Relative Probability]

Let $\mathcal{P} \eqdef (S, \pr{})$ be a probability space and $C$ be an
event with nonzero probability.  Then
\[
\mathcal{P}_C \eqdef (S, \prsub{C}{})
\]
is also a probability space, where for any event $A$,
\begin{equation}\label{defprc}
\prsub{C}{A} \eqdef \prcond{A}{C}.
\end{equation}
\end{theorem*}
We call $\prsub{C}{}$ the \emph{probability relative to $C$}, and
$\mathcal{P}_C$ the \emph{probability space relative to $C$}.

\bparts

\ppart Prove the Relative Probability Theorem. (Hint: Review the
definition of a probability space in
\hyperref{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l10.pdf}{l10}{probsp}{Notes 10, Definition 4.2}.
\solnospace{
A probability space is defined to be a sample space $S$ and a probability function $\pr{}$ which satisfies two properties:
\begin{enumerate}
\item $\pr{S} =1$, and

\item if $A$ is the disjoint union of a sequence of events
$A_0,A_1,\dots$, then $A$ is an event, $\sum_{i\in\nats} \pr{A_i}$
converges and
\begin{equation}\tag{Sum Rule}
\pr{A} = \pr{\lgunion_{i\in\nats}A_i} = \sum_{i\in\nats} \pr{A_i}.
\end{equation}
\end{enumerate}

First, we see that the sample space for the new probability space has not
changed.  We must then just show that the new probability function $\prsub{C}{}$
still satisfies the two conditions.

\begin{enumerate}
\item
To show this:
\begin{align*}
\prsub{C}{S} &= \prcond{S}{C} & \text{definition~(\ref{defprc}) of $\prsub{C}{}$}\\
             &= \frac{\pr{S \cap C}}{\pr{C}} & \text{definition of $\prcond{S}{C}$}\\
             &= \frac{\pr{C}}{\pr{C}} & \text{since $C \subseteq S$}\\
             &= 1 & \text{since $\pr{C} \neq 0$.}
\end{align*}

\item
The Sum Rule can be verified as follows:

\begin{align*}
\prsub{C}{\lgunion_{i\in\nats}A_i}
    &= \pr{\lgunion_{i\in\nats}A_i \biggm| C} &
          \text{definition~(\ref{defprc}) of $\prsub{C}{}$}\\\\
    &= \frac{\pr{(\lgunion_{i\in\nats}A_i) \cap C}}{\pr{C}} &
           \text{definition of $\prcond{\cdot}{C}$}\\
    &= \frac{\pr{\lgunion_{i\in\nats}(A_i \cap C)}}{\pr{C}}&
             \text{distributive law}\\
    &= \sum_{i \in \nats} \frac{\pr{A_i \cap C}}{\pr{C}} & \text{Sum Rule}\\
    &=  \sum_{i \in \nats} {\prcond{A_i}{C}} &
           \text{definition of $\prcond{\cdot}{C}$}\\\\
    &= \sum_{i \in \nats} {\prsub{C}{A_i}}&
          \text{definition~(\ref{defprc}) of $\prsub{C}{}$}
\end{align*}

\end{enumerate}
}

\ppart Explain why the two-set Inclusion-Exclusion Law for conditional
probabilities,
\[
\prcond{A\union B}{C} = \prcond{A}{C} + \prcond{B}{C} - \prcond{A
\intersect B}{C},
\]
now follows immediately from ordinary two-set Inclusion-Exclusion
(without having to mimic the ordinary proof using conditional
probabilities).

\solnospace{
Now that we have this nifty theorem about relative probability, we no
longer have to re-derive formulas and laws with conditional probabilities and
treat them differently.
The new probability space we defined was different from the original in that
the probability function now represents probabilities that are conditioned on
event $C$. These are exactly the conditional probabilities used in the Inclusion-Exclusion Law for conditional probabilities.  Since in part a, we have shown 
that the original sample space together with the probability function representing these probabilities form a valid probability space, we are able to extend
any laws for probability spaces to conditional probabilities.
}
\eparts





\item
The Sum Rule can be verified as follows:

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 9    *
%**************


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

\problem {\bf (10 points)} In each problem part, either define a probability
space and events $A$, $B$, and $C$ such that all the equations hold
simultaneously, or else prove that no such probability space and
events exist.

\begin{problemparts}

\problempart
\begin{eqnarray*}
\Pr(A \mid B)           & = &   \frac{1}{4} \\
\Pr(A \mid C)           & = &   \frac{1}{4} \\
\Pr(A \mid B \cap C)    & = &   \frac{3}{4}
\end{eqnarray*}

\solution{These events can exist, as indicated in the diagram below.
Empty regions have zero probability.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{Sol9-set1.eps}}}
\bigskip
}

\problempart
\begin{eqnarray*}
\Pr(A \mid B)           & = &   \frac{3}{4} \\
\Pr(A \mid C)           & = &   \frac{3}{4} \\
\Pr(A \mid B \cap C)    & = &   \frac{1}{4}
\end{eqnarray*}

\solution{These events can exist, as indicated in the diagram below.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{Sol9-set2.eps}}}
\bigskip
}

\problempart
\begin{eqnarray*}
\Pr(A \mid B)           & = &   \frac{3}{4} \\
\Pr(A \mid C)           & = &   \frac{3}{4} \\
\Pr(A \mid B \cup C)    & = &   \frac{1}{4}
\end{eqnarray*}

\solution{These events can not exist.  At least one of the events $B$ or
$C$ must be at least half as likely as $B \cup C$.  Without loss of
generality, assume that this is true for event $B$; that is,

\begin{eqnarray*}
\frac{\Pr(B)}{\Pr(B \cup C)}    & \geq &        \frac{1}{2}.
\end{eqnarray*}

The first equation implies that

\begin{eqnarray*}
\frac{\Pr(A \cap B)}{\Pr(B)}    & = &           \frac{3}{4}.
\end{eqnarray*}

Multiplying the equation and the inequality above gives

\begin{eqnarray*}
\frac{\Pr(A \cap B)}{\Pr(B \cup C)}     & \geq &        \frac{3}{8}.
\end{eqnarray*}

Note that the set $A \cap (B \cup C)$ contains the set $A \cap B$.
Therefore, $\Pr(A \cap (B \cup C)) \geq \Pr(A \cap B)$.  Substituting
this fact into the preceding inequality gives

\begin{eqnarray*}
\frac{\Pr(A \cap (B \cup C))}{\Pr(B \cup C)}    & \geq &        \frac{3}{8}.
\end{eqnarray*}

Consequently, $\Pr(A \mid B \cup C) \geq \frac{3}{8} > \frac{1}{4}$,
contradicting the third equation.
}

\end{problemparts}

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

\problem {\bf (10 points)}  After their arrest and sentencing for
unlawful use of firearms, and short hospital stays, the three
gunfighters, $A$, $B$, and $C$ applied for parole.  The parole board
decided to release two of the three, chosen uniformly at random, but
has not released their names.

Gunfighter $A$ figures that he will be released with probability
$\frac{2}{3}$.  A guard offers to tell gunfighter $A$ the name of one
of the other gunfighters who will be released (either $B$ or $C$).
However, gunfighter $A$ declines the offer.  He reasons that if the
guard says, for example, ``$B$ 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 $C$ will also be released, but these
events are equally likely.

Either prove that gunfighter $A$ has reasoned correctly or prove that
he is wrong.  Assume that if the guard has a choice of saying $B$ or
$C$ because both are to be released, then he picks one uniformly at
random.

\solution{Gunfighter $A$ has reasoned incorrectly.  We must compute

\begin{eqnarray*}
\Pr(\text{$A$ released} \mid \text{guard says ``$B$''})
        & = &   \frac{\Pr(\text{$A$ released and guard says ``$B$''})}
                        {\Pr(\text{guard says ``$B$''})}.
\end{eqnarray*}

These probabilities are worked out in the tree diagram below.

\bigskip
\centerline{\resizebox{!}{3.0in}{\includegraphics{Sol9-prisoner.eps}}}
\bigskip

Plugging these probabilities into the preceding equation gives

\begin{eqnarray*}
\Pr(\text{$A$ released} \mid \text{guard says $B$ released})
        & = &   \frac{\frac{1}{3}}{\frac{1}{2}} \\
        & = &   \frac{2}{3}
\end{eqnarray*}

If the guard says that $B$ will be released, then $A$ still has a
$\frac{2}{3}$ chance of release.
}

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

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps10
(You do go to lecture, right?)
You are shown two envelopes, each lying face down on a table.
There is a number from $\{0,\ldots, n\}$ written inside each. You pick an
envelope and get to see the number in that envelope.
You can then either choose to stay with that number, or switch to the number
written in the other envelope.
You {\em win} if the number you end up with
is the larger of the two (that is, if either you originally picked
the larger and stayed, or if you originally picked the
smaller and switched).

A randomized strategy for this game
is a function that, for each number $i$ that may be revealed in the
envelope you look at, assigns a probability $p_i$ of switching. For example,
a strategy where $p_i = \frac{1}{2}$ for all $i$ effectively ignores the number
revealed and chooses randomly. A strategy where
$p_i = 1$ for $i < \frac{n}{2}$ and $p_i = 0$ for $i \geq \frac{n}{2}$
would switch if the number revealed is in the lower half of the range and
stay if it is in the upper half of the range.


\begin{problemparts}
\problempart
Prove that the strategy described in class for winning with probability
better than $1/2$ is optimal if the envelopes are filled with $x$ and $x+1$,
where $x$ is chosen uniformly from $\{0,\ldots, n-1\}$. In other words,
since we have shown that the strategy given in lecture wins with probability
at least $\frac{1}{2}+\frac{1}{2n}$, show that the expected value of wins per
guess with \emph{any} randomized strategy (any set of $\{p_0, p_1, \ldots p_n\}$ is
\emph{at most} $\frac{1}{2}+\frac{1}{2n}$.

\solution{
Let $p_i$ denote the probability that you switch if you see the number
$i$. This is an arbitrary choice, so it covers every strategy (a strategy is
such a set of $p_i$). Then, the  probability that you win if the envelopes 
contain the pair $(i,i+1)$
is the probability that you will see the smaller number and switch or you
will see the bigger number and stay.  Since the probability of picking either
envelope (and thus either number) is $1/2$, the probability that you win is
\[
\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})
\]
Then, since the pair in the envelopes can range from $(0,1)$ to $(n-1,n)$,
the total probability that you win is:

\[
\sum_{i=0}^{n-1} \frac{1}{n} \left(\frac{1}{2}p_i + \frac{1}{2}(1-p_{i+1})\right)
= \frac{1}{2}+\frac{1}{2n}\sum_{i=0}^{n-1} (p_i-p_{i+1})
= \frac{1}{2}+\frac{1}{2n} (p_0 - p_n) \leq \frac{1}{2}+\frac{1}{2n}
\]
}

\problempart
\emph{Optional question:} Can you think of another strategy that is also optimal
as described above? Is this new strategy `really' optimal?

\solution{
This can almost be read directly off of the probability formula. The strategy is
to switch if $0$ is revealed, stay if $n$ is revealed, and act arbitrarily
otherwise (always switch, always stay, switch half the time, etc). This is
reasonable, since those two choices are guaranteed to lead to a win.

No, it's not truly an optimal strategy -- there is no guarantee that the
distribution of the envelopes even includes the endpoints, in the general case.
It relies on the envelopes being filled with the given distribution.
}

\end{problemparts}

\problem %source: spring00 ps8
We know from statistics that when a policeman gets shot he/she survives with
probability $0.8$ if he/she wears a bullet-proof vest and survives with
probability $0.12$ if the policeman doesn't wear a vest.
Given that 15\% of the policemen wear bullet-proof vests, what is the
probability that a random policeman was wearing a bullet-proof vest if he/she
survived a firearm attack?

\omitsolution{
Let $B$ be the event the policeman wears a vest.  Let $W$ be the
event the policeman survives an attack.
We want to compute $Pr(B|W)$.  By Bayes' theorem,
\[
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
\]

An equally valid solution would be to draw out a tree of the
conditional probabilities and to calculate the solution
``graphically''.
}



%END   Joe's problems

%BEGIN Ray's problems
%END   Ray's problems

%BEGIN Ivan's problems (spring '98)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem5 spring98
\problem There are 4 coins in a box, namely $c_1, c_2, c_3, c_4$. The
probability $p_i$ that the coin $c_i$ gives a Head is $\frac{1}{i}$
for $1\leq i\leq4$.  A coin is selected from the box uniformly at
random, and is being tossed until a Head is seen.

\bparts
\ppart
Write down the sample space of the experiment. [2 pts]

\solution{
The sample space is
$\{(c_1,H)\}\cup\{c_2,c_3,c_4\}\times\{H,TH,TTH,TTTH,\dots\}$
}
 
\ppart
What is the probability that a Head is first seen in the $2^{nd}$ toss? [9 pts]

\solution{
For this part and the following part, let $H_i$ be the event that ``a Head is first seen in the $i^{th}$ toss''. Let $C_i$ be the event that ``$c_i$ is drawn from the box''.

\begin{eqnarray*}
P(H_2)  &=&P(H_2|C_1)P(C_1)+P(H_2|C_2)P(C_2)+P(H_2|C_3)P(C_3)+P(H_2|C_4)P(C_4)\\
        &=&0\cdot\frac{1}{4}+\underbrace{\frac{1}{2}\cdot\frac{1}{2}}_{P(H_2|C_2)}\cdot\frac{1}{4}+\underbrace{\frac{2}{3}\cdot\frac{1}{3}}_{P(H_2|C_3)}\cdot\frac{1}{4}+\underbrace{\frac{3}{4}\cdot\frac{1}{4}}_{P(H_2|C_4)}\cdot\frac{1}{4}\\
        &=&\frac{95}{576}\\
\end{eqnarray*}
}
 
\ppart
Given that a Head is first seen in the $2^{nd}$ toss, what is the 
probability that $c_i$ is selected from the box? [9 pts]

\solution{
\begin{eqnarray*}
P(C_i|H_2)&=&\frac{P(C_i\cap H_2)}{P(H_2)}\\
         &=&\frac{P(H_2|C_i)P(C_i)}{P(H_2)}\\
         &=&\frac{\frac{i-1}{i}\cdot\frac{1}{i}\cdot\frac{1}{4}}{\frac{95}{576}}\\
         &=&\frac{144(i-1)}{95i^2}
\end{eqnarray*}

{\bf Checking:} $P(C_1|H_2)+P(C_2|H_2)+P(C_3|H_2)+P(C_4|H_2)=0+\frac{144}{95\cdot4}+\frac{144\cdot2}{95\cdot9}+\frac{144\cdot3}{95\cdot16}=1$. This makes sense.
}
 
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset9 problem7 spring98
\problem [10 pts]

A house is installed with a fire alarm to prevent fire accidents. If there 
is a fire, the probability for the fire alarm being turned on is 96\%. 
Even without a fire, the alarm may be turned on with a probability of 2\%. 
Suppose the probability for a fire accident to happen in the house is 1\%. 
If the fire alarm is now on, what is the conditional probability that there
is really a fire accident?

\solution{
{\bf Solution}

Let $F$ be the event that ``a fire accident happens''. Then let $A$ be the
event that ``the alarm is on''.

From the question, we have:
\begin{itemize}
\item $P(A|F)=0.96$
\item $P(A|\overline{F})=0.02$
\item $P(F)=0.01$
\end{itemize}

We want to find:
\begin{eqnarray*}
P(F|A)&=&\frac{P(F\cap A)}{P(A)}\\
      &=&\frac{P(A|F)P(F)}{P(A|F)P(F)+P(A|\overline{F})P(\overline{F})}\\
      &=&\frac{0.96\times 0.01}{0.96\times0.01+0.02\times0.99}\\
      &=&\frac{16}{49}
\end{eqnarray*}
}

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000 PS 9 %%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem Consider the following procedure for
generating a small, positive integer.  I flip a coin.  If the outcome
is heads, then I roll one die and take the result.  If the outcome is
tails, then I roll two dice and take the sum.  Assume that the coin is
fair and the dice are fair and 6-sided.

\begin{problemparts}
\problempart Define a probability space that describes this experiment.

\solution{The sample space consists of 42 outcomes.  Six of these are
pairs:

\[
(H, 1), (H, 2), \ldots, (H, 6)
\]

Each of these outcomes occurs with probability $\frac{1}{2} \cdot
\frac{1}{6} = \frac{1}{12}$.  The remaining thirty-six outcomes are
triples:

\[
(T, 1, 1), (T, 1, 2), \ldots, (T, 6, 6)
\]

Each of these outcomes occurs with probabiliy $\frac{1}{2} \cdot
\frac{1}{6} \cdot \frac{1}{6} = \frac{1}{72}$.}

\problempart What is the probability that the procedure generates a 5?

\solution{
\begin{eqnarray*}
\Pr(\text{generates 5})
    & = &   \Pr((H, 5)) + \Pr((T, 1, 4)) + \Pr((T, 2, 3)) \\
    &   &   \mbox{} + \Pr((T, 3, 2)) + \Pr((T, 4, 1)) \\
    & = &   \frac{1}{12} + \frac{1}{72} + \frac{1}{72}
        + \frac{1}{72} + \frac{1}{72} \\
    & = &   \frac{5}{36}
\end{eqnarray*}
}

\problempart What is the probability that the coin was heads given
that the procedure generated a 5?

\solution{
\begin{eqnarray*}
\Pr(\text{coin was heads} \mid \text{generated 5})
    & = &   \frac{\Pr(\text{coin was heads} \cap \text{generated 5})}
            {\Pr(\text{generated 5})} \\
    & = &   \frac{\Pr((H, 5))}{\frac{5}{36}} \\
    & = &   \frac{\frac{1}{12}}{\frac{5}{36}} \\
    & = &   \frac{3}{5}
\end{eqnarray*}
}

\end{problemparts}  
%%%%%%%%%%%%%%  Fall 2000   PS 9  %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem Each person carries a certain, rare disease
with probability 1 in 1000.  Two doctors claim to be able to test for
the disease before symptoms appear.

\begin{problemparts}

\problempart Doctor $A$ was educated at Harvard Medical School and
employs the latest high-tech test.  If a patient has the disease, then
the test comes back positive 99\% of the time.  If the patient does
not have the disease, then the test comes back negative 97\% of the
time.  What is the probability that Doctor $A$ correctly diagnoses a
patient?

\solution{
\begin{eqnarray*}
\Pr(\text{$A$ is correct})
    & = &   \Pr(\text{is diseased} \cap \text{test positive}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased} \cap \text{test negative}) \\
    & = &   \Pr(\text{is diseased}) \cdot
        \Pr(\text{test positive} \mid \text{is diseased}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased}) \cdot
        \Pr(\text{test negative} \mid \text{not diseased}) \\
    & = &   0.001 \cdot 0.99 + 0.999 \cdot 0.97 \\
    & \approx & 0.970
\end{eqnarray*}
}

\problempart Doctor $B$ (a quack from MIT) murmurs strange chants and burns incense.
With probability 1 in 1000, Doctor $B$ says that a patient has the
disease, regardless of whether or not the patient actually does.  What
is the probability that Doctor $B$ correctly disgnoses a patient?

\solution{
\begin{eqnarray*}
\Pr(\text{$B$ is correct})
    & = &   \Pr(\text{is diseased} \cap \text{test positive}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased} \cap \text{test negative}) \\
    & = &   \Pr(\text{is diseased}) \cdot
        \Pr(\text{test positive} \mid \text{is diseased}) \\
    &   &   \mbox{} +
        \Pr(\text{not diseased}) \cdot
        \Pr(\text{test negative} \mid \text{not diseased}) \\
    & = &   0.001 \cdot 0.001 + 0.999 \cdot 0.999 \\
    & \approx & 0.998
\end{eqnarray*}
}

\problempart Which doctor makes more errors? And how often, 
compared to the other?

\solution{

\textbf{Solution:}\\
Doctor $A$ makes about 15 times more errors than Doctor
$B$.}

\end{problemparts} 
%%%%%%%%%%%%%%  Fall 2000  PS 10   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\documentclass[11pt, twoside]{article}
\usepackage{epsf}

\input{macros-course}


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

\solution{
\medskip
\textbf{Solution:}
\medskip
Let M be the event the person is male, F female,
C colorblind.  We are given $\prob{C \mid M} = \frac{5}{100}$ and
$\prob{C \mid F}=\frac{25}{10,000}.$ Since the population consists of equal
numbers of males and females, $\prob{M} = \prob{F} = \frac{1}{2}$.  So,
\[\prob{M \mid C} = \frac{\prob{C \mid M}\times \prob{M}}{\prob{C}} = \frac{\prob{C \mid M}\times \prob{M}}{\prob{C \mid M}\times \prob{M} + \prob{C \mid F}\times \prob{F}} = \]
\[\frac{(5/100)\times (1/2)}{(5/100)\times (1/2) + (25/10000) \times
(1/2)} = 20/21. \]}

\problem
Suppose that a resident of Boston chosen at random is a Red Sox fan (The Curse
 notwithstanding) with probability $0.90$. Also suppose that a 
resident chosen at
random is a Celtics fan (probably still living in the Bird-McHale-Parish era)
with probability $0.75$, and that a resident
Red Sox fan chosen at random is a Celtics fan with probability
$0.80$.  Now suppose that a resident is chosen at random from among
those that are {\it not\/} Red Sox fans.  What is the probability
that such a resident is a Celtics fan?

\solution{
\medskip
\textbf{Solution:}
\medskip
Let $C$ represent the event that a resident is a Celtics fan, and $S$ represent the event
that the resident is a Red Sox fan.  Then:
 
\begin{eqnarray*}
\prob{C} & = & \prob{C  \mid  S} \prob{S} + \prob{C  \mid  \overline{S}} \prob{\overline{S}} \\
\prob{C  \mid  \overline{S}} & = & \frac{\prob{C} - \prob{C  \mid  S} * \prob{S}}{\prob{\overline{S}}} \\
& = & \frac{0.75 - 0.80 \cdot 0.90}{1 - 0.9} \\
& = & 0.3
\end{eqnarray*}}   
%%%%%%%%%%%%%%  Fall 2000 PS 10    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem 
% 18.313 Quiz I, problem 3

A population consists of $c_1$ members of type 1, $c_2$ members
of type $2,\cdots ,c_n$ members of type $n$.  A set of $k$ members is
drawn from the population without replacement. 

\bparts
\ppart Find the probability that exactly $i$ members of type 1
were chosen.

\solution{
\medskip
\textbf{Solution:}
\medskip
Let $N_{1i}$ be the event that exactly $i$ members of class 1 were
chosen.  $\prob{N_{1i}} = \frac{\binom{c_1}{i} \times \binom{c_2+\cdots +
c_n}{k-i}}{\binom{c_1+\cdots +c_n}{k}}$.

}

\ppart Find the probability that exactly $i$ members of class 1
and exactly $j$ members of class 2 were chosen.

\solution{
\medskip
\textbf{Solution:}
\medskip
Let $N_{2j}$ be the event that exactly $j$ members of class 2 were
chosen.  Then $ \prob{N_{1i} \cap N_{2j}} = \frac{\binom{c_1}{i} \binom{c_2}{j}
\binom{c_3 +\cdots + c_n}{k-i-j}}{\binom{c_1 + \cdots +c_n}{k}} $}

\eparts


%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem
In London, half of the days have some rain. The weather forecaster is
correct 2/3 of the time -- i.e. the probability that it rains, given
that she has predicted that it will rain, and the probability that it
does not rain given that she has predicted that it does not rain, are
both equal to 2/3. When rain is forecast, Mr. Pickwick takes his
umbrella. When rain is not forecast, he takes it with probability
1/3. 
\bparts
\ppart Find the probability that Pickwick has no umbrella, given that it rains.
\ppart Find the probability that it doesn't rain, given that he brings his umbrella.  
\eparts

\solution{
\medskip
\textbf{Solution:}
\medskip 
\\We construct a tree as in lecture notes \#19. For part (a), we wish to find 
\begin{eqnarray*}
\prob{\text{no umbrella}  \mid \text{rain}}
  & = &\frac{\prob{\mbox{no umbrella} \wedge \mbox{rain}}}{\prob{\mbox{rain}}}\\
& = & \frac{1/9}{1/2} = 2/9.
\end{eqnarray*}

For part (b), we wish to find
\begin{eqnarray*}
\prob{\text{no rain} \mid \text{umbrella}} & = &
 \frac{\prob{\mbox{no rain} \wedge \mbox{umbrella}}}{\prob{\mbox{umbrella}}}\\
& = & \frac{1/6 + 1/9}{1/9 + 1/6 + 1/3 + 1/18} = 5/12
\end{eqnarray*}

} 
%%%%%%%%%%%%%%  Fall 2000  PS 10   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem Compute the probabilities of the following
three events and determine which one is most likely.  Assume that the
dice are fair, 6-sided, and mutually independent.

\begin{problemparts}
\problempart Rolling at least one 6 when six dice are rolled.

\solution{
\medskip
\textbf{Solution:}
\medskip
The probability of rolling a 6 on a particular die is
$\frac{1}{6}$.  The probability of not rolling a 6 on a particular die
is $\frac{5}{6}$, since this is the complementary event.  The
probability of not rolling a 6 on any of six dice is
$(\frac{5}{6})^6$, since the numbers rolled are mutually independent.
The probability of rolling a 6 on some die is therefore $1 -
(\frac{5}{6})^6 = 0.665\ldots$.  }

\problempart Rolling at least two 6's when twelve dice are rolled.

\solution{
\medskip
\textbf{Solution:}
\medskip
The probability of rolling two or more 6's is 1 minus the
probability of rolling zero or one 6's.  The probability of rolling
zero 6's is $(\frac{5}{6})^{12}$, arguing as before.  The probablity
of rolling exactly one 6 is

\[
12 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{11}
\]

since there are 12 ways to choose the die that comes up 6, the
probability of this die coming up 6 is $\frac{1}{6}$, and the
probability of the remaining dice all coming up in the range 1 to 5 is
$(\frac{5}{6})^{11}$.

Overall, the probability of rolling two or more sixes is therefore

\begin{eqnarray*}
1 - \left(\frac{5}{6}\right)^{12} -
    12 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{11}
        & = &   0.618\ldots.
\end{eqnarray*}
}

\problempart Rolling at least three 6's when eighteen dice are rolled.

\solution{
\medskip
\textbf{Solution:}
\medskip
Arguing as before, the probability of rolling at least three 6's is

\begin{eqnarray*}
1   - \left(\frac{5}{6}\right)^{18}
    - 18 \cdot \frac{1}{6} \cdot \left(\frac{5}{6}\right)^{17}
    - \binom{18}{2} \cdot \left(\frac{1}{6}\right)^2 \cdot
        \left(\frac{5}{6}\right)^{16}
    & = &   0.597\ldots.
\end{eqnarray*}
}

\end{problemparts}

\solution{
\medskip
\textbf{Solution:}
\medskip
The first event is most likely.}

\end{problems} 
%%%%%%%%%%%%%% 
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%%%%%%%%%%%% FALL 19999 %%%%%%%%%%%%%%%%%%

%%% PRoblem set #11
\problem %{\bf Independence}
\textbf{The Flippant Juror}

A three-person jury has two responsible members, each of whom
independently has a probability $p> 1/2$ of making the correct decision.
The third juror flips a 50-50 coin for each decision.  So a one-person
jury with a responsible juror has probability $p$ of making the correct
decision.  Suppose the three-person jury decides by majority.  Which jury
has the better probability of making the correct decision, a
one-repsonsible-person jury or the three-person jury?

\solution{

Suppose the members of the 3-person jury are Socrates, Plato, and
Homer Simpson.  Socrates and Plato have both independently a probability
$p$ of making the right choice, and Homer just flips a coin.
Here are the events in which case the 3-person jury could be right:
\begin{itemize}
\item
Socrates and Plato are both right, (in which case what Homer says is irrelevant, as the
majority rules): probability of this event is  $p^2$;

\item
Socrates is right, Plato is wrong, and Homer is right: probability of this event is $\frac{1}{2}
p (1-p)$;

\item
Socrates is wrong, Plato is right, and Homer is right: probability of this event is $\frac{1}{2}
p (1-p)$.
\end{itemize}

These events are disjoint, so the probability that one of them occurs
is the sum $p^2 + p(1-p) = p$.  Thus the 3-person jury and the
1-person jury have the {\it same} probability of making the correct
decision.

}


\iffalse

\problem  %\textbf{Uniform Sample Spaces and Independence}

          %(based on Chung 2.17 and 2.23)

Let $m$ and $n$ be positive integers. Let the sample space be
\begin{align*}
S = \{x\in \naturals: 0 \leq x \leq m n - 1\},
\end{align*}
with all values having equal probability (i.e., this is a uniform
sample space).  Let events $A$ and $B$ be
\begin{align*}
A &= \{x\in S: m | x\},\\
B &= \{x\in S: n | x\}.
\end{align*}
\begin{problemparts}
\ppart Show that
\begin{align*}
\prob{A \cap B} \geq \prob{A} \prob{B}.
\end{align*}

\solution{
Since the sample space is uniform, we have
\begin{align*}
\prob{A} &= \frac{|A|}{|S|} = \frac{(m n)/m}{m n} =
\frac{1}{m},\\
\prob{B} &= \frac{|B|}{|S|} = \frac{(m n)/n}{m n} =
\frac{1}{n},\\
\prob{A \cap B} &= \frac{|A\cap B|}{|S|} = \frac{|A\cap B|}{m
n}.
\end{align*}
We have $|A\cap B| \geq 1$, since $0\in A\cap B$. Therefore,
\begin{align*}
\prob{A \cap B} = \frac{|A\cap B|}{m n} \geq \frac{1}{m n} =
\prob{A} \prob{B},
\end{align*}
which is what we wished to show.
}


\ppart Under what condition on $\gcd(m,n)$ will
events $A$ and $B$ be independent? Prove that your condition is
necessary and sufficient. \emph{Hint:} use Theorem~2.3.5 in Rosen.

\solution{
Events $A$ and $B$ are independent if and only if
\begin{align*}
\prob{A\cap B} = \prob{A} \prob{B}.
\end{align*}
Substituting the values of the probabilities that we computed in
part~(a), we see that $A$ and $B$ are independent if and only if
\begin{align*}
|A\cap B| = 1.
\end{align*}
Let's show that this will occur if and only if $m$ and $n$ are
relatively prime.

Suppose $m$ and $n$ are relatively prime. Then $\gcd(m, n) = 1$.
By theorem~2.3.5 in Rosen, we see that
\begin{align*}
\lcm(m, n) = \frac{m n}{\gcd(m, n)} = m n.
\end{align*}
Clearly, every number in $A\cap B$ is a common multiple of $m$ and
$n$. Also, every element of $A\cap B$ is between $0$ and $m n -
1 = \lcm(m, n) - 1$. It follows that $A\cap B \subseteq \{0\}$
(otherwise we would have a positive common multiple of $m$ and
$n$ that is smaller than the least common multiple). Clearly,
$0\in A\cap B$. Thus $A\cap B = \{0\}$, and so $|A\cap B| = 1$.

Now let's show the other direction. Suppose $|A\cap B| = 1$, but
$m$ and $n$ are not relatively prime, i.e., $\gcd(m, n) > 1$.
Then
\begin{align*}
\lcm(m, n) = \frac{m n}{\gcd(m, n)} < m n,
\end{align*}
and so $\lcm(m, n) \in S$. By definition of least common
multiple, we get $\lcm(m, n)\in A$ and $\lcm(m, n)\in B$. Thus
$\lcm(m, n)\in A\cap B$. Since $0\in A\cap B$, and $\lcm(m, n) >
0$, we see that $|A\cap B| \geq 2$. Contradiction.
}
\end{problemparts}
\fi




\iffalse
\problem \textbf{Birthdays Again}

Suppose there are 120 people in a room. Assume that their
birthdays are independent and uniformly distributed. As stated in
lecture notes, with probability $> 99\%$ there will be two that have
the same birthday.

Now suppose you find out the birthdays of all the people in the room
except one---call her ``Jane''---and find all 119 dates to be different.

\begin{problemparts}

\ppart What's wrong with the following argument:
\begin{quotation}\noindent
With probability greater than 99\%, some pair of people in the room have
the same birthday.  Since the 119 people we asked all had different
birthdays, it follows that with probability at greater than 99\% Jane has
the same birthday as some other person in the room.
\end{quotation}

\solution{

Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
119 people we asked all have different birthdays.

It is true that $\prob{A} > 0.99$ (that is indeed the probability
spoken about in the lecture notes). However, that is the \emph{a
priori} probability, i.e., assuming all the birthdays are
uniform and independent, with no other constraints. The argument
above makes the erroneous assumption that event $A$ has
probability of at least $99\%$ even once we know that event $B$
holds. But once we know that event $B$ holds, the birthdays are
no longer independent. Thus $\prob{A \mid B}$ is not necessarily
equal to $\prob{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).
}


\ppart What is the actual probability that Jane has the same birthday
as some other person in the room?

\solution{
Let $S$ be the set of birthdays of the 119 people in the room
other than Jane. By assumption, $|S| = 119$. Let $b$ be the date
of Jane's birthday. Since $b$ is uniformly distributed over a
set of size 365, and $b$ is independent of all the birthdays in
$S$, we have
\begin{align*}
\prob{b\in S\mid B} = \frac{|S|}{365} = \frac{119}{365} \approx
32.6\%,
\end{align*}
where $B$ is the event that the 119 people we asked all have
different birthdays.
}
\end{problemparts}
\fi






\problem  %Mutually Independent Events: modified from 96

Suppose $n$ balls are thrown randomly into $n$ boxes, so each ball lands
in each box with uniform probability.  Also, suppose the outcome of each
toss is independent of all the other tosses.

\bparts

\ppart Let $X_i$ be an indicator random variable whose value is $1$ if box
$i$ is empty and $0$ otherwise.  Write a simple closed form expression for
the probability distribution of $X_i$.   Are $X_1, X_2, \ldots, X_n$
independent random variables?

\solution{

The probability that box $i$ is empty is the
probabilility that all $n$ balls land in other boxes, which is
$(\frac{n-1}{n})^n=(1 - \frac{1}{n})^n$.  Thus $\prob{X_i=1}= (1 -
\frac{1}{n})^n$ and $\prob{X_i=0}=1 - (1 - \frac{1}{n})^n$.

The $X_i$'s are not independent as $\prob{X_1=X_2=\cdots =
X_n=0}=0$, whereas $\prod_{i=1}^n \prob{X_i = 0}\neq 0$.  }

\ppart Show that $\prob{\text{at least $k$ balls fall in the first box}}
\leq {\binom{n}{k}} \left(\frac{1}{n}\right)^k$ \\

\solution{
For any subset $S$ of $k$ balls, let $E_S$ be the event that 
each of these balls falls in box~1.
There are $\binom{n}{k}$ such events, corresponding to each subset of 
$k$ balls, and these events intersect.
We are intestested in the probability of the union of these events,
which is at most the sum of their individual probabilities:
$\prob{ \bigcup_S E_S} \leq \sum_S \prob{E_S}$.
For any fixed set $S$, $\prob{E_S}=\left(\frac{1}{n}\right)^k$, 
since we don't care where other balls land.
Thus, the probability that at least $k$ balls fall in box 1 is at most
${\binom{n}{k}} \cdot \left( \frac{1}{n}\right)^{k}$.
}

\ppart Let $R$ be the maximum of the numbers of balls that land in each of
the boxes.  Use Stirling's formula and the result from the previous
problem part to give an upper bound for $\prob{R\geq k}$.  (Hint: Use the
previous part to show that $\prob{\text{$k$ or more balls fall in some
box}}\leq n/k!$.)

\solution{
From previous part we know that for any $1\leq i\leq n$,
\begin{equation*}
\prob{\text{at least $k$ balls fall in the $i$th box}}\leq
\binom{n}{k} \cdot \left( \frac{1}{n}\right)^{k}.      
\end{equation*}

Expanding, we get 
\begin{equation*}
\binom{n}{k} \cdot \left(\frac{1}{n}\right)^k =
\frac{n(n-1)\cdots(n-k+1)}{k!n^k}
= \frac{n}{n} \cdot \frac{n-1}{n} \cdots \frac{n-k+1}{n}
\cdot \frac{1}{k!} \leq \frac{1}{k!}.
\end{equation*}
Therefore, 
\begin{equation*}
\prob{\text{at least $k$ balls fall in some box}}\leq 
\sum_{i=1}^n \prob{\text{at least $k$ balls fall into the $i$th
box}}\leq \frac{n}{k!}.
\end{equation*}

$R \geq k$ exactly when some box has at least $k$ balls, 
so using Stirling's formula, 
\begin{equation*}
\prob{{R\geq k}} \leq n \frac{1}{\sqrt{2\pi k}}
\left(\frac{e}{k}\right)^k.
\end{equation*}
}


\ppart Prove that the probability that every box has fewer than $\ln
n$ balls approaches one as $n$ increases.

\iffalse
 How does your answer in part~(c) behave asymptotically with
$n$ when $k=n^\alpha$ for some constant~$\alpha>0$?  Is $\prob{R\geq
k}$ large or small as a function of $n$?  What about when $k=\log\log
n$?
\fi

\solution{

%NEEDS REVISION:
The event that every box has fewer than $\ln n$ balls is equivalent to
the event that the maximum number of balls in any box is less than
$\ln n$.
Therefore, the required probability is 

\begin{align*}
\prob{R<\ln n} & = 1 - \prob{R\geq \ln n}\\
               & \geq 1 - \frac{n}{\sqrt{2\pi \ln n}}\cdot 
                         \left( \frac{e}{\ln n}\right)^{\ln n}\\
%               & = 1 - \frac{e^{\ln n}}{\sqrt{2\pi \ln n}}\cdot 
%                         \left( \frac{e}{\ln n}\right)^{\ln n}\\
               & = 1 - \frac{e^{\ln
               n}}{e^{(1/2)(\ln 2 \pi + \ln \ln n)}}\cdot\frac{e^{\ln n}}{e^{(\ln
               \ln n) \ln n }}\\
               & = 1 - e^{(2 - \ln \ln n)\ln n - (1/2)(\ln\ln n + \ln 2\pi)}
\end{align*}
[The inequality in the second line is derived using part (c).]

Because $\ln n$ and $\ln \ln n$ both approach $\infty$ as
$n\rightarrow\infty$, the exponent of $e$ in the final expression above
goes to $-\infty$, and therefore the limit as $n$ approaches $\infty$ of
the entire final expression is 1.  Hence, $\lim_{n \rightarrow \infty}
\prob{R<\ln n} \geq 1$.  But of course $\prob{R<\ln n}\leq 1$ for all $n$,
which immediately implies that
\[
\lim_{n \rightarrow \infty} \prob{R<\ln n} = 1.
\]

%When $k=n^\alpha$,
%\begin{equation*}
%\prob{R\geq k}  \leq 
%n \cdot \frac{1}{\sqrt{2\pi n^\alpha}} \cdot
%\frac{e^{n^\alpha}}{\left(n^\alpha\right)^{n^\alpha}}
%=\frac{1}{\sqrt{2\pi}}\cdot e^{-n^\alpha (\alpha\ln n -1) +
%(1-\alpha/2) \ln n} = e^{-\Theta(n^\alpha \ln n)},
%\end{equation*}
%which is exponentially small in~$n$.

%When $k = \log \log n$, 
%\begin{align*}
%\prob{R\geq k} & \leq
%n\cdot \frac{1}{\sqrt{2\pi \log\log n}} \cdot
%\frac{e^{\log\log n}}{\left(\log\log n\right)^{\log\log n}}
%\\
%&=
%\frac{1}{\sqrt{2\pi}} \cdot e^{ \ln n - \frac{1}{2}\ln \log \log n} \cdot
%\frac{e^{ \log \log n}}{e^{(\ln\log\log n) (\log \log n)}}
%\\
%&= 
%e^{\Theta( \ln n \,-\, \frac{1}{2}\ln \log \log n \,+\, \log \log n
%\, - \,\ln\log\log n \log \log n )}
%\\
%&= 
%e^{\Theta( \ln n )} \;\; ,
%\end{align*}
%which is much greater than 1, trivializing our upper bound.

\iffalse

which asymptotically is dominated by $e^{\ln n -\frac{1}{2}\ln\log\log n}
= n/\sqrt{\log\log n}$ (since $\ln n$ grows much faster than any power of
$\log \log n$),

\fi

}

\eparts

\iffalse
\ppart
We'd like to know when this upper bound goes from being close to 1
to being close to 0  as we increase $k$.
Show that this happens around $\displaystyle k\approx \frac{\log n}{\log\log n}$.
\\
(You only need to find when $n/k^k$ goes from being close to $0$ to
close to~$1$.)

\solution{
We would like to know what value of $k=k(n)$ 
(that is, $k$ as a function of $n$) makes
$n\cdot \frac{1}{\sqrt{2\pi k}} \left( \frac{e}{k}\right)^k$ 
equal to a constant.   % (between 0 and 1).
Asymptotically, we would like 
$ e^{\ln n} \frac{e^k}{k^k} $ to be some constant.
It is clear that for $k=\omega(\log n)$, the denominator is growing 
faster than the numerator and this expression is asmyptotically~0.
When $k=o(\log n)$, the numerator's growth is governed by 
$e^{\ln n} = n$, so we really want to find out
when $n/k^k$ is a constant.

Solving $n/k^k = 1$ (or any constant $c$ instead of 1)
by taking logs of both sides, we get $k\log k = \log n$.
Iterating this once, we get\\
$k= \log n/\log k = \log n/\log (\log n/\log k) = 
\log n/(\log \log n -\log \log k) \approx \log n/\log \log n$
since $k=o(\log n)$.

It is easy to check that $k\approx \frac{\log n}{\log\log n}$ satisfies
$k^k = n$: 
\begin{eqnarray*}
\left( \frac{\log n}{\log \log n} \right)^{\frac{\log n}{\log \log n}}
& =&
2^{\left( \log \left( \frac{\log n}{\log \log n} \right) \right) \frac{\log n}{\log \log n}}\\
&=&
2^{\left( \log\log n -\log\log\log n \right) \frac{\log n}{\log \log n}}\\
&=&
2^{\log n -\log n \left( \frac{\log\log\log n}{\log \log n}\right)}\\
&=&
n\cdot n^{o(1)}.
\end{eqnarray*}
}

\ppart  Let $E$ be a random variable denoting the number of empty boxes.
What is the probability distribution of $E$? 
The following lemma may be useful in your calculations.
\begin{lemma*}
Suppose we have $m$ independent random variables $B_1$, \ldots,
$B_m$ with Bernoulli distribution: for each $i$,
\begin{align*}
\prob{B_i = 1} &= p,\\
\prob{B_i = 0} &= 1-p.
\end{align*}
Then $\sum_{i=1}^m B_i$ is a random variable with distribution
$f_{m,p}$.
\end{lemma*}

\solution{ Let $X_i$ be the indicator random variable whose value is $1$ if box
$i$ is empty and is $0$ otherwise.  This is a Bernoulli random variable.
Now the probability that box $i$
is empty is the probability that all $n$ balls land in all other
boxes, which is $(\frac{n-1}{n})^n=(1 - \frac{1}{n})^n$.  So $\prob{X_i=1}= (1 -
\frac{1}{n})^n$ and $\prob{X_i=0}=1 - (1 - \frac{1}{n})^n$.  

Finally,  $E=\sum_{i=1}^n {X_i}$, and by the lemma
$E$ is a random variable with distribution
$f_{n,(1-\frac{1}{n})^n}$. 

}

\ppart  Show that
\[
\\prob{\text{at least $k$ balls fall in the first box}}
      \leq \binom{n}{k} \left(\frac{1}{n}\right)^k.
\]

\solution{
For any subset $S$ of $k$ balls, let $E_S$ be the event that 
each of these balls falls in box~1.
There are $\binom{n}{k}$ such events, corresponding to each subset of 
$k$ balls, and these events intersect.
We are interested in the probability of the union of these events,
which is at most the sum of their individual probabilities:
$\prob{ \cup_S E_S} \leq \sum_S \prob{E_S}$.
For any fixed set $S$, $\prob{E_S}=\left(\frac{1}{n}\right)^k$, 
since we don't care where other balls land.
Thus, the probability that at least $k$ balls fall in box 1 is at most
${\binom{n}{k}} \cdot \left( \frac{1}{n}\right)^{k}$.
}

\ppart  Let random variable $R$ be the maximum number of balls that land
in any box.  Use Stirling's formula and the result from the last part
to give an upper bound for $\prob{{R\geq k}}$.
(Hint: First use the last part to show that the 
$\prob{\text{at least $k  balls fall in some box}} \leq n/k!$.)

\solution{
From previous part we know that for any $1\leq i\leq   n$, 
\[
\prob{\text{at least $k$ balls fall in the i-th box}}\leq
\binom{n}{k} \cdot \left( \frac{1}{n}\right)^{k}.
\]
Expanding, we get 
$\binom{n}{k} \frac{1}{n^k} = \frac{n(n-1)\cdots(n-k+1)}{k!n^k}
= \frac{n}{n} \cdot \frac{n-1}{n} \cdots \frac{n-k+1}{n}
\cdot \frac{1}{k!}
\leq \frac{1}{k!}$


So, the $\prob{\text{at least $k$ balls fall in some box}} \leq
n\prob{\text{at least $k$ balls fall into the $i$th-box}} \leq n/k!$.

$R \geq k$ exactly when some box has at least $k$ balls, 
so using Stirling's formula, 
$\prob{{R\geq k}} \leq    n \frac{1}{\sqrt{2\pi k}} \left( \frac{e}{k}\right)^k$.
}


\ppart  How does your answer to the last part behave asymptotically
with $n$ when $k=n^\alpha$ for some constant~$\alpha$?
Is $\prob{{\mbox{$\geq k$ balls land in some box}}}$ large or small as
a function of $n$?\\
What about when $k=\log\log n$?
\solution{
When $k=n^\alpha$ (for some constant $\alpha$), 
\[
\prob{R\geq k}  \leq 
n \cdot \frac{1}{\sqrt{2\pi n^\alpha}} \cdot
\frac{e^{n^\alpha}}{\left(n^\alpha\right)^{n^\alpha}}
=\frac{1}{\sqrt{2\pi}}\cdot e^{-n^\alpha (\alpha\ln n -1) + (1-\alpha/2) \ln n} = e^{-\Theta(n^\alpha \ln n)}
\]
which is exponentially small in~$n$.

When $k = \log \log n$, 
\begin{eqnarray*}
\prob{R\geq k} & \leq &
n\cdot \frac{1}{\sqrt{2\pi \log\log n}} \cdot
\frac{e^{\log\log n}}{\left(\log\log n\right)^{\log\log n}}
\\
&=& 
\frac{1}{\sqrt{2\pi}} \cdot e^{ \ln n - \frac{1}{2}\ln \log \log n} \cdot
\frac{e^{ \log \log n}}{e^{(\ln\log\log n) (\log \log n)}}
\\
&=& 
e^{\Theta( \ln n \,-\, \frac{1}{2}\ln \log \log n \,+\, \log \log n
\, - \,\ln\log\log n \log \log n )}
\\
&=& 
e^{\Theta( \ln n )} \;\; ,
\end{eqnarray*}
%which asymptotically is dominated by $e^{\ln n -\frac{1}{2}\ln\log\log n}
%= n/\sqrt{\log\log n}$
%(since $\ln n$ grows much faster than any power of $\log \log n$), 
which is much greater than 1, trivializing our upper bound. }

%\ppart
%We'd like to know when this upper bound goes from being close to 1
%to being close to 0  as we increase $k$.
%Show that this happens around $\displaystyle k\approx \frac{\log n}{\log\log n}$.
%\\
%(You only need to find when $n/k^k$ goes from being close to $0$ to
%close to~$1$.)
%\solution{
%We would like to know what value of $k=k(n)$ 
%(that is, $k$ as a function of $n$) makes
%$n\cdot \frac{1}{\sqrt{2\pi k}} \left( \frac{e}{k}\right)^k$ 
%equal to a constant.   % (between 0 and 1).
%Asymptotically, we would like 
%$ e^{\ln n} \frac{e^k}{k^k} $ to be some constant.
%It is clear that for $k=\omega(\log n)$, the denominator is growing 
%faster than the numerator and this expression is asymptotically~0.
%When $k=o(\log n)$, the numerator's growth is governed by 
%$e^{\ln n} = n$, so we really want to find out
%when $n/k^k$ is a constant.
%
%Solving $n/k^k = 1$ (or any constant $c$ instead of 1)
%by taking logs of both sides, we get $k\log k = \log n$.
%Iterating this once, we get\\
%$k= \log n/\log k = \log n/\log (\log n/\log k) = 
%\log n/(\log \log n -\log \log k) \approx \log n/\log \log n$
%since $k=o(\log n)$.

%It is easy to check that $k\approx \frac{\log n}{\log\log n}$ satisfies
%$k^k = n$: 
%\begin{eqnarray*}
%\left( \frac{\log n}{\log \log n} \right)^{\frac{\log n}{\log \log n}}
%& =&
%2^{\left( \log \left( \frac{\log n}{\log \log n} \right) \right) \frac{\log n}{\log \log n}}\\
%&=&
%2^{\left( \log\log n -\log\log\log n \right) \frac{\log n}{\log \log n}}\\
%&=&
%2^{\log n -\log n \left( \frac{\log\log\log n}{\log \log n}\right)}\\
%&=&
%n\cdot n^{o(1)}.
%\end{eqnarray*}
%}
\eparts
\fi


%END   Tina's problems





%BEGIN Christos Fall 01

%----------------------------------------------------
% source  : Problem Repository
% topics  : Conditional Probability, Birthday Paradox
% outcome : 2,8

\problem \textbf{(Birthdays Again)}
Suppose there are 100 people in a room. Assume that their birthdays
are independent and uniformly distributed. As stated in lecture notes, 
with probability $> 99\%$ there will be two that have the same
birthday. 

Now suppose you find out the birthdays of all the people in the room 
except one---call her ``Jane''---and find all 99 dates to be different.

\begin{problemparts}

\ppart 
What's wrong with the following argument:
\begin{quotation}\noindent
With probability greater than 99\%, some pair of people in the room
have the same birthday.  Since the 99 people we asked all had
different birthdays, it follows that with probability greater
than~99\% Jane has the same birthday as some other person in the
room. 
\end{quotation}

\solnospace{
Here's the problem with the argument: Let $A$ be the event that some two
people in the room have the same birthday.  Let $B$ be the event that the
99 people we asked all have different birthdays.

It is true that $\prob{A} > 0.99$ (that is indeed the probability
spoken about in the lecture notes). However, that is the \emph{a
priori} probability, i.e., assuming all the birthdays are
uniform and independent, with no other constraints. The argument
above makes the erroneous assumption that event $A$ has
probability of at least $99\%$ even once we know that event $B$
holds. But once we know that event $B$ holds, the birthdays are
no longer independent. Thus $\prob{A \mid B}$ is not necessarily
equal to $\prob{A}$ (in our case, they are actually quite
different, as will be computed in part~(b)).
}

\ppart 
What is the actual probability that Jane has the same birthday
as some other person in the room?

\solnospace{
Let $S$ be the set of birthdays of the 99 people in the room
other than Jane. By assumption, $|S| = 99$. Let $b$ be the date
of Jane's birthday. Since $b$ is uniformly distributed over a
set of size 365, and $b$ is independent of all the birthdays in
$S$, we have
\begin{align*}
\prob{A\mid B} = 
\prob{b\in S} = 
\frac{|S|}{365} = 
\frac{99}{365} \approx
27.1\%,
\end{align*}
where $B$ is the event that the 99 people we asked all have
different birthdays.
}
\end{problemparts}



%END Christos Fall 01


\end{problems}

\end{document}



