\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{/a/class/6.042/spring94/handouts/macros-course}

\addtolength{\topmargin}{-.3in}
\setlength{\textheight}{9.1in}
\setlength{\textwidth}{7in}
\setlength{\leftmargin}{0in}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\pr}{\mbox{Prob}}
\newcommand{\wun}{\frac{1}{1}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\third}{\frac{1}{3}}
\newcommand{\fourth}{\frac{1}{4}}
\newcommand{\twoth}{\frac{2}{3}}
\newcommand{\threef}{\frac{3}{4}}
\renewcommand{\bar}{\overline}

\begin{document}

\handout{sols8}{Problem Set 8 Solutions}{April 15, 1994}

\pset{8}
\bigskip

\begin{problems}
\pnumset{7}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem 

\begin{problemparts}
\problempart
Let ``$W$'' denote the event that the Red Sox win.
The sample space along with the associated probabilities 
are given in the figure.
We see that 
\[
\pr [\mbox{Red Sox win}] = \half\third\half + \half\twoth\threef\twoth +
\half\twoth\fourth\threef + \half\wun\threef\half + \half\wun\fourth\twoth
	= \frac{7}{12}.
\]

\begin{figure}[htb]
\setlength{\unitlength}{.3in}
\begin{picture}(12,7)(-7,-3.5)

\end{picture}
\end{figure}

%	\hspace*{2in}

\problempart
\[
\pr [W \mid \bar{Y_2}] = {\pr [W \land \bar{Y_2}] \over \pr [\bar{Y_2}]}
= { \half\third\half + \half\twoth\fourth\threef + \half\wun\fourth\twoth
	\over
	\half\third + \half\twoth\fourth + \half\wun\fourth}
= \frac{11}{18}.
\]
\problempart
This is defined to be $1/m$---in this case, $1/2$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem

\begin{problemparts}
\problempart
Let $s_1, \ldots, s_p$ be the names of the people in the room.
Our sample space ranges over all birthdays and all orders in which 
we choose the people.
Let us represent the sample space as 
all pairs $(\bar{b}, \pi)$ where $\bar{b}$ 
is a $p$-tuple, $\bar{b}= (b_1, \ldots, b_p)$ with $b_i\in \{1, \ldots, n\}$
(denoting the birthday of person $s_i$)
and $\pi$ is a permutation of $\{1, \ldots, p\}$
(so $s_{\pi (i)}$ is the $i$th person we choose).
The $p$-tuples are all equally likely---each has probability $1/n^p$---%
and no matter how the birthdays occur, we
choose an ordering $\pi$ of the people uniformly---each
$\pi$ has probability $1/n!$---%
%	Each $p$-tuple $\bar{b}$ has probability $1/n^p$ of occurring and 
%	each permutation $\pi$ has probability $1/n!$ of occurring,
so the probability of any pair $(\bar{b}, \pi)$ is $1/(n!\; n^p)$.

Consider the pairs containing some fixed permutation~$\pi_0$.
How many $p$-tuples $\bar{b}$, when paired with $\pi_0$, result in an sample
point where the first $t$ names are written without anyone responding?
The birthdays of persons $s_{\pi_0(1)}, \ldots, s_{\pi_0(t)}$ must 
all be different from each other and different from everyone else's.
This can happen in 
$n(n-1)\cdots (n-t+1) (n-t)^{p-t}= {n!\over (n-t)!}(n-t)^{p-t}$ ways.
No matter which permutation $\pi$ we fix, there will always be this many
$p$-tuples that can be paired with $\pi$ to result in a 
``successful'' sample point.
Thus the probability is 
\[ 
{\left( n! \cdot {n! \over (n-t)!} (n-t)^{p-t} \right) {1 \over n! \; n^p}}
= 
{ n! \; (n-t)^{p-t} \over (n-t)! \; n^p}.
\]
You may conclude that the permutation $\pi$ did not affect the probability,
and so it did not matter that we chose people randomly:
If we don't know anything about anyone's birthday---each person's birthday 
is assumed to be uniformly distributed throughout the year---then fixing an 
ordering of the people does not bias the probability one way or the other.

\problempart
Using Stirling's approximation, this probability is
\[
{
\sqrt{2\pi n} \left({n\over e}\right)^n (n-t)^{p-t}
\over
\sqrt{2\pi (n-t)} \left({n-t\over e}\right)^{n-t} n^p
}
= 
{
{\textstyle \sqrt{n\over n-t}} \cdot e^{-t} \cdot {n^{n-p} \over (n-t)^{n-p}}
}
= 
{\textstyle \sqrt{n\over n-t}} \; e^{-t} \; (1-t/n)^{p-n}.
\]
If $t=o(n)$, then $n-t$ goes to $n$ as $n$ gets large, and so
$\sqrt{n\over n-t}$ goes to~1, and the above expression 
is thus $\sim e^{-t} (1-t/n)^{p-n}$ (``$\sim$'' with respect to~$n$).
\problempart
We simply have
\[
e^{-t} 
\left( e^{-\frac{t}{n} - \Theta\left( \frac{t^2}{n^2}\right)}\right)^{p-n}
=
e^{-t+\frac{t}{n}(n-p) + \Theta\left( \frac{t^2(n-p)}{n^2}\right)}
=
e^{-\frac{tp}{n} + \Theta\left( \frac{t^2(n-p)}{n^2}\right)}
=
e^{-\frac{tp}{n}}
\left( e^{\Theta\left( t^2\frac{1}{n}-t^2\frac{p}{n^2}\right)}\right).
\]

If $t=o(\sqrt{n})$, then $t^2\frac{1}{n}$ goes to 0 as $n$ gets large;
similarly if $t=o(n/\sqrt{p})$, then $t^2\frac{p}{n^2}$ also goes to 0 as $n$ 
gets large.
Thus, under these two assumptions on $t$, the probability goes to
$e^{-tp/n}$ as $n$ gets large.
Notice that in order to say that the probability is $\sim e^{-pt/n}$
(with respect to $n$), we need that both terms inside the $\Theta$ go to~0; 
it is not sufficient that both terms merely be small compared to~$tp/n$.
Also notice that in our analysis we used 
$1-x = e^{\ln (1-x)}$ and 
$\ln (1-x) = (-x) - {(-x)^2\over 2} + {(-x)^3\over 3} - {(-x)^4\over 4}+\cdots$
for $|x|<1$ 
and the fact that ${(-x)^3\over 3}-{(-x)^4\over 4}+\cdots=O(x^2)$ for $|x|<1$.

\problempart
From part {\bf (a)}, we have the probability equal to
\[
{ n(n-1)\cdots (n-t+1) \over n^t} \cdot
{ (n-t)^{p-t} \over n^{p-t}}
= 
{365\over 365}  \cdot
{364\over 365}  \cdot
{363\over 365}  \cdot
{362\over 365}  \cdot
{361\over 365}  \cdot
\left({360\over 365} \right)^{95}
= 0.2624.
\]
From part {\bf (c)}, the asymptotic estimate is 
$e^{-{tp\over n}} = e^{-{5\cdot 100\over 365}} = 0.2541$, 
which is within~4\% of the correct answer.
\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\wproblem 

\begin{problemparts}
\problempart 
$\pr [\mbox{Exactly $k$ heads}] = {n\choose k} p^k (1-p)^{n-k}.$
\problempart 
\[
{\pr [\mbox{Exactly $k$ heads}] 
 \over
 \pr [\mbox{Exactly $k-1$ heads}]}
= 
{n-k+1 \over k}\cdot {p\over 1-p},
\]
which is 1 for $k=p(n+1)$.  For $k<p(n+1)$ it is greater than 1, and
for  $k>p(n+1)$ it is less than~1.
Thus $k=p(n+1)$ is the most likely number of heads.
\problempart
$\pr [\mbox{No heads}] = \left( 1-1/n \right)^n$ which goes to $e^{-1}$
as $n$ gets large.

$\pr [\mbox{One head}] 
= {n\choose 1} \left( {1\over n}\right) ^1 \left( 1-{1\over n} \right)^{n-1}$,
so the ratio is $\left( 1-{1\over n} \right)$.
\end{problemparts}


\end{problems}


\end{document}


