\problemdata     
{S01-PS9-8}           
{probability-k-events, mutual independence}              
{} 		
{X96, S01-PS9}
{S01 Karger}


\begin{problem}


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


\end{problem}


