\documentclass[11pt,twoside]{article}
\usepackage{amsmath} %,graphicx}
\input{/a/class/6.042/fall99/inputs/macros-course}

%\allowdisplaybreaks

\begin{document}

\renewcommand{\solution}[1]{}

\pset{11}{November 18, 1999}{\textbf{Tuesday, 11/23/99 at start of lecture}}

\reading F97 Lecture Notes 20 (Independence), and 21 (Random Variables).

\textbf{Remember to include a collaboration statement on the front page
of your solutions.}

\begin{problems}

\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


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

\problem  % {\bf Random Variables based on Dice experiments}

Let $R$ and $Z$ denote random variables for two independent dice
experiments. Let $M_1 = \min(R,Z)$, and $ M_2 = R+Z$.  what is the
distribution function for $M_1$?  Are $M_1$ and $M_2$ independent random
variables?  Prove it.

\solution{
For any $x\in [1, 6]$,
\begin{align*}
\prob{M_1=x} &=
\prob{\min(R,Z)=x}\\
&= \prob{R = x~ \mbox{and}~ Z > x} + \prob{R > x~ \mbox{and}~ Z
= x} + \prob{R=Z=x}\\
&= {1/6}\cdot {\frac{6-x} {6}} + \frac{6-x}{6}\cdot {1/6} +
{1/6}\cdot {1/6}\\
&= {\frac{13-2x}{36}}.
\end{align*}

$M_1$ and $M_2$ are not independent since we have, for any $x\in [1,6]$,
\begin{align*}
\prob{M_1 = x | M_2 < x} &= 0\\
&\not= \prob{M_1 = x}
\end{align*}
}

\iffalse

\problem  % \textbf{Random variables and the Binomial Distribution}

Suppose $n\in \naturals$ and $p\in [0,1]$. Let $X$ and $Y$ be independent
random variables, both with binomial distribution $f_{n,p}$. Define
random variable $Z = X+Y$.
%\begin{problemparts}
%\ppart 

%QUERY: why the ugly algebraic proof, when there is such an obvious
%combinatorial/probabilistic-process oroof?

Using the definition of the binomial distribution and
Vandermonde's identity (theorem~4.3.5 in Rosen), prove that $Z$
has distribution $f_{2n,p}$. (You may find it easier to prove this
fact separately for the three cases $\prob{Z=z}$ when
$z\not\in[0,2n]$, $0\leq z\leq n$, and $n < z \leq 2n$)

\solution{
Clearly, $\prob{Z=z} = 0 = f_{2n,p}(z)$ for any $z\not\in [0,
2n]$.

Suppose $0\leq z \leq n$. Then
\begin{align*}
\prob{Z = z} &=
\prob{X + Y = z}
\\&= \sum_{(x,y)\in [0,n]^2: x+y=z} \prob{X=x \wedge Y=y}
\\&= \sum_{(x,y)\in [0,n]^2: x+y=z} \prob{X=x} \prob{Y=y}
%      \\&= \sum_{x=0}^z \prob{X=x} \prob{Y=z-x}
\\&= \sum_{x=0}^z f_{n,p}(x) f_{n,p}(z-x)
%      \\&= \sum_{x=0}^z \binom{n}{x} p^x (1-p)^{n-x} \cdot
%      \binom{n}{z-x} p^{z-x} (1-p)^{n-(z-x)}
\\&= p^z (1-p)^{2n-z} \sum_{x=0}^z \binom{n}{x} \binom{n}{z-x}
\\&= p^z (1-p)^{2n-z} \binom{2n}{z}
\\&= f_{2n,p}(z).
\end{align*}

Now suppose $2n \geq z > n$. Let $r = 2n-z$. Then $0\leq r< n$,
and so
\begin{align*}
\prob{Z = z} &=
\sum_{(x,y)\in [0,n]^2: x+y=z} \prob{X=x} \prob{Y=y}
\\&= \sum_{x=z-n}^n f_{n,p}(x) f_{n,p}(z-x)
\\&= p^z (1-p)^{2n-z} \sum_{x=z-n}^n \binom{n}{x} \binom{n}{z-x}
\\&= p^z (1-p)^{2n-z} \sum_{x=z-n}^n \binom{n}{n-x} \binom{n}{n
- (z-x)}
%      \\&= p^z (1-p)^{2n-z} \sum_{x=z-n}^n \binom{n}{n-x} \binom{n}{r +
%        (x - n)}
\\&= p^z (1-p)^{2n-z} \sum_{x=n-r}^n \binom{n}{n-x} \binom{n}{r +
(x - n)}
\\&= p^z (1-p)^{2n-z} \sum_{k=0}^r \binom{n}{k} \binom{n}{r -
k}
\\&= p^z (1-p)^{2n-z} \binom{2n}{r}
\\&= p^z (1-p)^{2n-z} \binom{2n}{2n-z}
\\&= p^z (1-p)^{2n-z} \binom{2n}{z}
\\&= f_{2n,p}(z).
\end{align*}

We thus see that $\prob{Z=z} = f_{2n,p}(z)$ for all $z$, and so
$Z$ has distribution $f_{2n,p}$.
}


%\ppart Assume the following result:
%\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*}
%Now use this result to give a simpler proof that $Z$ has
%distribution $f_{2n,p}$.

%\solution{
%Let $B_1$, \ldots, $B_{2n}$ be independent Bernoulli
%random variables, with the same distribution as in the lemma.
%Let
%\begin{align*}
%X' &= \sum_{i=1}^n B_i,\\
%Y' &= \sum_{i=n+1}^{2n} B_i,\\
%Z' &= \sum_{i=1}^{2n} B_i = X + Y.
%\end{align*}
%Now, by the lemma, both $X'$ and $Y'$ have distribution
%$f_{n,p}$. Also, $X'$ and $Y'$ are independent, since all
%$B_i$'s are mutually independent.

%We can also use the lemma to see that $Z'$ has distribution
%$f_{2n,p}$. Since $Z = X' + Y'$, we see that the sum of two
%independent random variables with distribution $f_{n,p}$ has
%distribution $f_{2n,p}$.
%}
%  \end{problemparts}
\fi


\problem  % \textbf{Binomial distribution}

A highly parallel supercomputer has 65,536 processors.  The cooling system
can't always keep up, and any processor can fail during the computation,
with probability $10\%$.  Using sophisticated failure-recovery algorithms,
the software can handle the failure of up to 7,000 processors.  Use
Theorem~3.1 in Lecture Notes~21 to derive an approximate lower bound on
the probability that the computation will complete successfully, assuming
all processor failures are independent.

\solution{

Let $n = 65536$, $p = 0.9$, and $\alpha = \frac{n -
7000}{n}$.  The probability that at most $n - 7000$ processors
will be OK is $F_{n,p}(\alpha \cdot n)$. By theorem~3.1 in lecture
notes~21, we have
\begin{align*}
F_{n,p}(\alpha n) &\leq
\frac{1-\alpha}{1 - \frac{\alpha}{p}} f_{n,p}(\alpha n)
\\&\approx \frac{1-\alpha}{1 - \alpha/p} \cdot \frac{2^{(\alpha
\log_2(\frac{p}{\alpha}) + (1-\alpha)
\log_2(\frac{1-p}{1-\alpha})) \cdot n}}{\sqrt{2\pi \alpha
(1-\alpha) n}}
\\&\approx 4.56 \cdot 10^{-9}.
\end{align*}
(Note that we can use that result, since $\alpha < p$.)  We see
that the probability that $n - 7000$ or more processors will be OK
(implying that the computation will complete successfully) is at
least $1 - 4.56\cdot 10^{-9}$.

}

\problem  \textbf{The World Series}

New York and Atlanta have both made it to the World Series again in 2000.
Assume that New York wins each game with probability 2/3 independently of
the outcomes of other games\footnote{---they wish \texttt{:-)}}.  Let $R$ be the
random variable denoting the number of the 4th game won by New York, e.g.,
if NY wins the 1st, 2nd, 4th, and 6th games, then $R=6$; let $R \eqdef 0$ if
NY doesn't win four games.

Let's generalize slightly and assume the teams keep playing,
possibly forever, until NY has indeed won 4 games.  This makes $R$ a
random variable taking on all natural number values.

\bparts

\ppart For $n>0$, give a simple closed form expression for $\prob{R = n}$.

\solution{

For $0<n<3$, we have $\prob{R=n} = 0$. For $4\leq n$, we have
\[
\prob{R=n} = \binom{n-1}{3} \cdot (2/3)^4  \cdot \frac{1}{3^{n-4}}=
\frac{8(n-1)(n-2)(n-3)}{3^{n+1}}.
\]
}


\ppart What is the most likely value of $R$?

\solution{4}

\ppart What is the probability that NY never wins 4 games, i.e., that $R=0$?

\solution{0}

\ppart What is the probability that New York really wins the 7 game
Series?

\solution{
\[
\prob{4 \leq R\leq 7}= \frac{?}{?}.
\]
}

\eparts


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

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

\iffalse

\problem %{\bf fall96 }

Use the lecture notes to compute upper bounds on the
following probabilities:

\bparts
\ppart 
In a poll with 2000 people, what is the probability that the result is off
by more than $1\%$?

\solution{$\prob{\geq 0.01} = 1 - \prob{< 0.01} \leq 1 -
\left(\frac{1-0.01}{1-0.02}\right) 2^{-2000} \binom{2000}{0.01\times
2000}$}

\ppart
In 1000 independent coin flips, what is the probability of getting 
at least 600 heads?

\solution{ $\prob{\geq 600} = 1-\prob{< 600}(n=1000,\alpha=3/5)\leq 1 - 
2^{-1000}{\binom{1000}{600}}{\frac{1-3/5}{1-6/5}}$}


\ppart
In a noisy communication channel with $10\%$ error rate, what is the
probability that out of 1000 transmitted bits, at least 200 bits are 
wrongly transmitted ({\em i.e.}, {\tt 1} is received as {\tt 0} and 
vice versa)?

\solution{
g$\prob{\geq 200} = 1-\prob{< 200}(n=1000,\alpha=1/5)\leq 1 - 
2^{-1000}{\binom{1000}{200}}{\frac{1-1/5}{1-2/5}}$}
\eparts

\fi


\end{problems}

\newpage
\section*{Topics for Week of November 22nd, 1999}

\begin{itemize}
\item
Independence (of 2 or more events)
\item
Product Rule for Independent events
\item
Uniform Distrbution
\item
Birthday Paradox
\item
Random Variables
\item
Indicator Variables
\item
Bernoulli Distribution
\item
Binomial Distribution
\end{itemize}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
