\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9.1in}

\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\vari[1]{\mbox{Var}(\, #1 \,)}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}

\remove{
  \newcommand{\problm}{\problem \rm}
  \renewcommand{\ppart}{\problempart \rm}
  \newcommand{\pf}{\begin{proof}\sf}
  \newcommand{\soln}{\sf}
  \newcommand{\thm}{\begin{theorem}\ \ }
}
\newcommand{\mystrut}{\rule{0pt}{14pt}}


\begin{document}

\psol{10}{December 13, 1994}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let random variable $X$ be the total number of heads.
In order to answer this question, we first need to compute
$\Ex{X}$ and~$\vari{X}$.
%	$\Ex{\mbox{\# heads}}$ and $\vari{\mbox{\# heads}}$:
\[
\Ex{X}
= 100 \Ex{\mbox{\# heads in 1 flip}} = 100 \cdot {1\over 2} = 50
\]
by linearity of expectation.
As shown in recitation, $\vari{R_1+R_2} = \vari{R_1} + \vari{R_2}$
if random variables $R_1$ and $R_2$ are independent.  (You should be able
to verify this yourself from the definitions.) 
For one coin, the variance of the number of heads is
$\frac{1}{2}(1-\frac{1}{2})^2 + \frac{1}{2}(0-\frac{1}{2})^2 = \frac{1}{4}$.
Thus we have
\[
\vari{X} = 100 \cdot \frac{1}{4} = 25.
\]

\remove{
  In order to compute the variance, we must look at $\vari{$R_1+R_2$}$
  when $R_1$ and $R_2$ are independent:
  \begin{eqnarray*}
  \vari{$R_1+R_2$} & = & \Ex{$(R_1+R_2 - \Ex{R_1+R_2})^2$}\\
   & = & \Ex{$(R_1+R_2)^2 -2(R_1+R_2)\Ex{$R_1+R_2$} + \Ex{$R_1+R_2$}^2$}\\
   & = & \Ex{$(R_1^2 -2R_1\Ex{$R_1$}+\Ex{$R_1$}^2)
	      (R_2^2 -2R_2\Ex{$R_2$}+\Ex{$R_2$}^2)
	      +2R_1R_2 -2R_1\Ex{$R_1$}-2R_2\Ex{$R_2$}+2\Ex{$R_1$}\Ex{$R_2$}$}\\
	...................
  \end{eqnarray}
}

\begin{problemparts}
\problempart  According to Markov's Inequality, 
\[
	\Prob{X \geq 70} \leq \frac{\Ex{X}}{70} = \frac{5}{7}.
\]
\problempart  Using Chebyshev's Inequality with $\sigma_X = \sqrt{25}$, 
\[	
	\Prob{X \geq 70} \leq \Prob{|X-\Ex{X}|\geq 4\sigma_X} \leq 1/4^2 = 1/16.
\]
Moreover, since the coin is fair, the distribution is symmetric,
and we can conclude that $\Prob{X-\Ex{X}\geq 4\sigma} \leq 1/32$.
\problempart
Since the coin is fair, $\Prob{X\geq(1-\alpha)n} = \Prob{X\leq\alpha n}$, 
which we analyzed in lecture:
\begin{eqnarray*}
	\Prob{X \leq \alpha n} & \leq & 
     \left(\frac{1-\alpha}{1-2\alpha}\right) {n\choose \alpha n} \frac{1}{2^n} 
\\
& \leq & \left(\frac{1-\alpha}{1-2\alpha}\right) 
{\sqrt{2\pi n} \left( n\over e\right)^n  e^{1/(12n)} \over
\sqrt{2\pi \alpha n} \left( \alpha n\over e\right)^{\alpha n} \cdot
\sqrt{2\pi (1-\alpha) n} \left( (1-\alpha) n\over e\right)^{(1-\alpha) n}} 
\cdot\frac{1}{2^n}
\\
&=& 
\left(\frac{1-\alpha}{1-2\alpha}\right) 
	\frac{2^{nH(\alpha)}}{\sqrt{2\pi n\alpha(1-\alpha)}}\cdot e^{1/(12n)} 
	\cdot \frac{1}{2^n} 
\end{eqnarray*}
%as derived in lecture.
%Since the coin is fair, this is the same as $\Prob{X \geq (1-\alpha)n}$.
%Now evaluating with $n=100$ and $\alpha=0.3$
%we have $H(0.3) = 0.3 \lg (1/0.3) + 0.7 \lg (1/0.7)=0.8812909$ and 
where $H(\alpha) = \alpha\lg\frac{1}{\alpha} + (1-\alpha)\lg\frac{1}{1-\alpha}$.  
Evaluating at $n = 100$ and $\alpha = 0.3$, we get 
\begin{eqnarray*}
	\Prob{X \geq (0.7)100} & \leq & 
\left(\frac{1-0.3}{1-0.6}\right) 
	\frac{2^{-100(1-H(0.3))}}{\sqrt{200\pi(0.3)(0.7)}} 
	\cdot e^{1/1200}
\\
&=& \frac{7}{4} 
	\cdot \frac{2^{-100 (1-0.8813)}}{\sqrt{200\pi(0.3)(0.7)}}
	\cdot e^{1/1200} 
\approx 4.071 \times 10^{-5} \approx \frac{1}{24,564}
\end{eqnarray*}
\end{problemparts}	
\remove{
  Notice that the more we know about the distribution, the better upper
  bound we can give:  knowing only the expectation, we get $5/7$ from
  Markov's inequality; knowing the variance as well, we get~$1/16$
  from Chebyshev's inequality; 
  knowing the entire distribution---that in fact it is a binomial 
  distribution---we get the best upper bound of all, $1/24564$.
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      10-2.
\problem 
Each side of the equation computes the expected number of heads:
the left side by linearity of expectation, 
since the expectation of the number of heads in a single coin flip is $p$, 
and the right side by definition, 
since $\Prob{\mbox{number of heads} = i} = {n\choose i} p^i(1-p)^{n-i}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      10-3.
\problem 
\mbox{}
\begin{problemparts}

\problempart
Note that for any random variables, $R$ and $T$, 
if $R \geq T$ on all sample points, then $\Ex{R} \geq \Ex{T}$.  
(This follows easily by considering $\Ex{R-T}$.)

For all $x,y \geq 0$, 
we have $\min(x,y) \leq \frac{x+y}{2} \leq \max(x,y) \leq x+y$, 
and since $x,y \in \{1, \ldots, n\}$, 
$\Ex{\min(x,y)} \leq \Ex{\frac{x+y}{2}} \leq \Ex{\max(x,y)} \leq \Ex{x+y}$, 

\problempart
\begin{eqnarray*}
\Ex{\max(x,y)} &=& \sum_{i=1}^n i\, \Prob{\max(x,y) = i} \\
	&=& \sum_{i=1}^n i\,\bigl(\Prob{\max(x,y)\leq i} - \Prob{\max(x,y)<i}\bigr) \\
	&=& \sum_{i=1}^n i\left(\frac{i^2}{n^2} - \frac{(i-1)^2}{n^2}\right) \\
	&=& \sum_{i=1}^n i\cdot\frac{2i-1}{n^2} \\
	&=& \frac{1}{n^2}\left(2\sum_{i=1}^n i^2 - \sum_{i=1}^n i\right) \\
	&=& \frac{1}{n^2}\left(2\cdot\frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}\right) \\
	&=& \frac{n(n+1)}{n^2}\left(\frac{2n+1}{3} - \frac{1}{2}\right) \\
	&=& \frac{(n+1)(4n-1)}{6n}
\end{eqnarray*}

We can check this for small $n$ (say 1 or 2) 
by looking directly at the sample space.

\problempart
Note that $\min(x,y) + \max(x,y) = x+y$ for all $x,y$, and thus, 
\begin{eqnarray*}
\Ex{\min(x,y)} % = \Ex{x+y-\max(x,y)} \\
	&=& \Ex{x} + \Ex{y} - \Ex{\max(x,y)} \\
	&=& \frac{n+1}{2} + \frac{n+1}{2} - \frac{(n+1)(4n-1)}{6n} \\
	&=& (n+1)\cdot\frac{6n-(4n-1)}{6n} \\
	&=& \frac{(n+1)(2n+1)}{6n}
\end{eqnarray*}

\remove{
We can check our answers by computing this directly, as in the previous part.
\begin{eqnarray*}
\Ex{\min(x,y)} &=& \sum_{i=1}^n i\left(\Prob{\min(x,y)\geq i} - \Prob{\min(x,y)>i}\right) \\
	&=& \sum_{i=1}^n i\left(\frac{(n-i+1)^2}{n^2} - \frac{(n-i)^2}{n^2}\right) \\
	&=& \sum_{i=1}^n i\cdot\frac{2(n-i)+1}{n^2} \\
	&=& \frac{1}{n^2}\left((2n+1)\sum_{i=1}^n i - 2\sum_{i=1}^n i^2\right) \\
	&=& \frac{1}{n^2}\left((2n+1)\cdot\frac{n(n+1)}{2} - 2\cdot\frac{n(n+1)(2n+1)}{6}\right) \\
	&=& \frac{n(n+1)(2n+1)}{n^2}\left(\frac{1}{2}-\frac{1}{3}\right) \\
	&=& \frac{(n+1)(2n+1)}{6n}
\end{eqnarray*}
}
We can check our answers by computing this directly:
\begin{eqnarray*}
\Ex{\min(x,y)} &=& \sum_{i=0}^\infty \Prob{\min(x,y)>i} \\
	&=& \sum_{i=1}^n \Prob{\min(x,y) \geq i} \\
% Alternatively, skip preceding step, and use $i = i-1$ in following.
	&=& \sum_{i=1}^n \frac{(n-i+1)^2}{n^2} \\
	&=& \frac{1}{n^2}\sum_{j=1}^n j^2 \qquad \mbox{where $j = n-i+1$}\\
	&=& \frac{1}{n^2}\cdot\frac{n(n+1)(2n+1)}{6} \\
	&=& \frac{(n+1)(2n+1)}{6n}
\end{eqnarray*}

\problempart
$\Ex{x-y} = \Ex{x} - \Ex{y} = \frac{n+1}{2} - \frac{n+1}{2} = 0$.  

\problempart
Note that $|x-y| = \max(x,y) - \min(x,y)$, so we have
\begin{eqnarray*}
\Ex{|x-y|} &=& \Ex{\max(x,y)} - \Ex{\min(x,y)} \\
	&=& \frac{(n+1)(4n-1)}{6n} - \frac{(n+1)(2n+1)}{6n} \\
	&=& \frac{(n+1)(2n-2)}{6n} \\
	&=& \frac{(n+1)(n-1)}{3n}
\end{eqnarray*}

Again, we can check this is $0$ and $\frac{1}{2}$ for $n=1,2$ respectively. 

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      10-4.
\problem 
In lecture, we derived that the expected number of boys before the 
first girl is 1, 
assuming that boys and girls are equally likely to be born, 
and that the gender of each child is independent of the gender of the 
other children.  
By symmetry, the expected number of girls before the first boy is also 1.  
If the couple wants to have one of each gender, 
they must have their first child, 
and then wait for the first child of the opposite gender, 
giving them a total of the first child, 
the other children born (of the same gender) before the first child 
of the opposite gender, 
and the last child, who is of the opposite gender.  
Thus the expected total number of children is 3.  

We can also compute this directly.  
Let $R$ be the total number of children.  
\begin{eqnarray*}
\Ex{R} &&= \sum_{i=0}^\infty \Prob{R>i} 
	= \sum_{i=0}^\infty \Prob{\mbox{first $i$ children have same gender}} \\
	&&= 1+\sum_{i=1}^\infty (1/2)^{(i-1)} 
%	= 1+\sum_{i=0}^\infty (1/2)^i 
	= 1+\frac{1}{1-1/2} 
	= 3
\end{eqnarray*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%      10-5.
\problem 
\mbox{}
\begin{problemparts}

\problempart
The sample space is the triple of outcomes of each of the dice, 
which can take one of six values.  
Every sample point is equally likely, so the space is uniform, 
and each point has probability $6^{-3} = 1/216$.
\begin{enumerate}

\item
There are $6 \cdot 5 \cdot 4$ ways for all the dice to take 
different values, so this happens with probability 
$\frac{6 \cdot 5 \cdot 4}{6^3} = \frac{20}{36} = \frac{5}{9}$.

\item
There are $3 \choose 2$ ways to pick the two dice with the same value, 
$6$ ways to choose their value, 
and $5$ ways to choose the (different) value of the last die.  
Thus the probability of this is 
$\frac{{3 \choose 2} 6 \cdot 5}{6^3} = \frac{3 \cdot 5}{36} = \frac{5}{12}$.

\item
Since all the dice have the same value, and there are six possible values, 
the probability is $\frac{6}{6^3} = \frac{1}{36}$.

\end{enumerate}
We verify that this is a probability: 
$\frac{5}{9} + \frac{5}{12} + \frac{1}{36} = \frac{20+15+1}{36} = 1$.

\problempart
Let $W_{\rm all}$ be the random variable corresponding to the 
net winnings of wagering \$1 on each of the six values.  
\remove{
If all dice have different values, 
then there is a net gain of \$1 on each of three numbers rolled, 
and net loss of \$1 on the three numbers not rolled, 
for a total \$0 net winnings on all six numbers.  
If two dice come up with the same value, 
and the last one with a different value, 
then there is a \$2 net gain from the number rolled twice, 
a \$1 net gain on the number rolled once, 
and a \$1 net loss on the four other numbers, 
for a net loss of \$1 on all six numbers. 
If all three dice come up with the same value, 
then there is a net gain of \$3 on that number, 
and a net loss of \$1 on each of the five others, 
for a net loss of \$2 on all six numbers.  
}
\begin{enumerate}

\item
If all dice have different values then
\begin{itemize}
\item Return on each of three numbers rolled: $\$1$
\item Return on each of three numbers not rolled: $-\$1$
\end{itemize}

\item
If two dice come up with the same value then
\begin{itemize}
\item Return on number rolled twice: $\$2$
\item Return on number rolled once: $\$1$
\item Return on each of the four number not rolled: $-\$1$
\end{itemize}

\item
If all three dice come up with the same value then 
\begin{itemize}
\item Return on the numbers rolled (on all three dice): $\$3$
\item Return on each of five numbers not rolled: $-\$1$
\end{itemize}

\end{enumerate}
Thus, 
$\Ex{W_{\rm all}} = \frac{5}{9}(3 \cdot 1 + 3 \cdot -1) 
		+ \frac{5}{12}(2 + 1 + 4 \cdot -1) 
		+ \frac{1}{36}(3 + 5 \cdot -1)
	= -17/36 \approx -0.472$.

\problempart
For $k \in \{ 1, 2, 3, 4, 5, 6\}$, 
let $W_k$ be the random variable corresponding to the 
net winnings of wagering \$1 on $k$.  
Also, $W_{\rm all} = \sum_{k=1}^6 W_k$, 
and so by the linearity of expectation, 
$\Ex{W_{\rm all}} = \sum_{k=1}^6 \Ex{W_k}$. 
By symmetry, $\Ex{W_j} = \Ex{W_k}$ for all $j$ and $k$, 
so $\Ex{W_k} = \frac{1}{6}\Ex{W_{\rm all}} = -17/216 \approx -0.0787$. 

\problempart
The game will be fair if $\Ex{W_k} = 0$, or equivalently, 
if $\Ex{W_{\rm all}} = 0$.  
Thus, we want $i_1$, $i_2$, and $i_3$ such that
$\frac{5}{9}(3 \cdot i_1 + 3 \cdot -1) 
		+ \frac{5}{12}(i_2 + i_1 + 4 \cdot -1) 
		+ \frac{1}{36}(i_3 + 5 \cdot -1)
	= 0$.
There is a lot of freedom to choose these values, 
since there are three parameters and only one equation.  
One solution is to set all the terms to 0, 
yielding $i_1 = 1$, $i_2 = 3$, and $i_3 = 5$.  
This makes $W_{\rm all} = 0$ always; 
different choices will give different variances for $W_{\rm all}$.


\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	10-6.
\problem 
\mbox{}
\begin{problemparts}

\problempart
$\sigma_{cR} = \sqrt{\vari{cR}} 
	= \sqrt{\Ex{(cR)^2} - (\Ex{cR})^2}
	= \sqrt{\Ex{c^2 R^2} - (c\Ex{R})^2}
	= \sqrt{c^2(\Ex{R^2} - (\Ex{R})^2)}
	= c\sqrt{\vari{R}}
	= c\sigma_R = cs$.

\problempart
$\vari R$ may be arbitrarily large.\\
If $\Prob{R=0} = 1-1/n$ and $\Prob{R=n}=1/n$, then $\Ex{R}=1$
and $\vari{R}=(1-\frac{1}{n})\cdot(0-1)^2 + \frac{1}{n}(n-1)^2=n-1$.\\
So by choosing~$n$ we can make the variance as large as we like.

In fact, it is possible to make $\vari{R}$ infinite.  
Let $f_R:\nats \to [0,1]$ be the probability function of $R$ 
i.e., $f_R(i) = \Prob{R=i}$, such that 
\[f_R(i) = \cases{
\frac{6}{\pi^2} \cdot \frac{1}{i^3}			& \cif{i > 0} \\
1- \frac{6}{\pi^2}\sum_{j=1}^\infty \frac{1}{j^3}	& \cif{i = 0} \\
}
\]
Then $\Ex{R} = \sum_{i} i\,f_R(i) 
	= \sum_{i=1}^\infty i \cdot \frac{6}{\pi^2 i^3}
	= \frac{6}{\pi^2}\sum_{i=1}^\infty \frac{1}{i^2}
	= 1$, 
but $\vari{R} = \sum_{i} i^2f_R(i) 
	= \sum_{i=1}^\infty i^2 \cdot \frac{6}{\pi^2 i^3}
	= \frac{6}{\pi^2}\sum_{i=1}^\infty \frac{1}{i}
	= \infty$. 

\problempart
$\Ex{1/R}\leq 1$ since $R\geq 1$.

\problempart
$\Prob{R=10}=\frac{3}{4}$ and $\Prob{R=4}=\frac{1}{8}=\Prob{R=16}$.\\
For this distribution, 
$\Ex{R} = 4\cdot\frac{1}{8} + 10\cdot\frac{3}{4} + 16\cdot\frac{1}{8} = 10$, \\
$\sigma_R^2 = \vari{R} = \Ex{(R-10)^2} 
	= (4-10)^2\frac{1}{8} + (10-10)^2\frac{3}{4} + (16-10)^2\frac{1}{8} 
	= 9$,\\ 
and $\Prob{|R-\Ex{R}| \geq 6} = \Prob{R=4}+\Prob{R=16} 
	= \frac{1}{8} + \frac{1}{8} = \frac{1}{4}$.

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	10-7
\problem 
\remove{
\begin{eqnarray*}
\Ex{Z} &= &\Prob{V=1}\left(\sum_{r\in\mbox{\scriptsize Range}(R)} 
		r\cdot \Prob{R=r}\right) 
	+ \Prob{V=2}\left(\cdots \mystrut\right) + \cdots
\\
&=&	 \left(\Prob{V=1}\cdot \Ex{R_1}\mystrut\right)
	+\left(\Prob{V=2}\cdot \Ex{R_1+R_2}\mystrut\right) +\cdots
%	+\left(\Prob{V=n}\cdot \Ex{R_1+R_2+\cdots+R_n}\mystrut\right)
\\
&=&	 \left(\Prob{V=1}\cdot \Ex{R}\mystrut\right)
	+\left(\Prob{V=2}\cdot 2 \Ex{R}\mystrut\right) +\cdots
	+\left(\Prob{V=n}\cdot n \Ex{R}\mystrut\right)
\\
&=&	 \Ex{R}\left(\Prob{V=1}
	+\Prob{V=2}\cdot 2 +\cdots
	+\Prob{V=n}\cdot n\mystrut\right)
\\
&=&	 \Ex{R}\cdot\Ex{V}.
\end{eqnarray*}
}
For $k \in \{1,\ldots, n\}$, 
let $T_k = \sum_{i=1}^k R_i$, 
and $I_k$ be the indicator random variable of the event $V=k$.  
Notice that $Z = \sum_{k=1}^n I_k T_k$, 
since $I_V T_V = R_1 + \ldots + R_V$, 
and $I_k T_k = 0$ for all $k \neq V$.  
Also, since $R_1, \ldots, R_n$, and $V$ are mutually independent, 
$I_i$ and $T_i$ are also independent for each $i$, 
so $\Ex{I_i T_i} = \Ex{I_i} \Ex{T_i}$.  
Thus, 
\begin{eqnarray*}
\Ex{Z} &=& \sum_{k=1}^n \Ex{I_k T_k} \\
	&=& \sum_{k=1}^n \Ex{I_k} \Ex{T_k} \\
	&=& \sum_{k=1}^n \Prob{V=k} \Ex{\sum_{i=1}^k R_i} \\
	&=& \sum_{k=1}^n \Prob{V=k} \sum_{i=1}^k \Ex{R_i} \\
	&=& \sum_{k=1}^n \sum_{i=1}^k \Prob{V=k} \Ex{R} \\
	&=& \Ex{R} \sum_{k=1}^n k\,\Prob{V=k} \\
	&=& \Ex{R} \Ex{V} 
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	10-8
\problem \mbox{}

\bparts
\ppart 
$\Prob{\mbox{choosing largest of $n$ numbers}} = 1/n$.  \\
$\Prob{\mbox{challenger in round $i$ is highest so far}}=1/(i+1)$. \\
(The challenger in round $i$ is player $i+1$.)
\ppart 
%$\Ex{c_i} = (1-\frac{1}{i+1})\cdot 0 + \frac{1}{i+1}\cdot 1 = \frac{1}{i+1}$.
$\Ex{c_i} = \Prob{c_i = 1} 
	= \Prob{\mbox{challenger in round $i$ is highest so far}} 
	= \frac{1}{i+1}$.
\ppart 
$\Ex{C} = \sum_i \Ex{c_i} = \sum_{i=2}^{n}\left( \frac{1}{i}\right)
	 \sim \ln n$. \\
$C$ is the total number of times that the challenger wins, 
so $\Ex{C}$ is the number of times we expect the current champion 
to displaced by the challenger.  

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%	10-9
\problem \mbox{}

\bparts
\ppart Let indicator random variable $\mbox{Empty}_i$ be 1 if box $i$
is empty and 0 otherwise.  
$\Ex{\mbox{Empty}_i} = \Prob{\mbox{box $i$ is empty}} 
	= \left(1-\frac{1}{n}\right)^n$.\\
By linearity of expectation, the expected number of empty boxes is\\
$\sum_i \Ex{\mbox{Empty}_i} = n\left(1-\frac{1}{n}\right)^n$.

\ppart 
For any subset $S$ of $k$ balls, let $E(S)$ be the event that 
each of these balls falls in box~1.
There are $n\choose 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{ \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.
%		 \left( \frac{n-1}{n}\right)^{n-k}$, which 
%	less than $\left(\frac{1}{n}\right)^k$ if $n\geq 2$.
Thus, the probability that at least $k$ balls fall in box 1 is at most
${n\choose k} \left( \frac{1}{n}\right)^{k}$.

Expanding $n\choose k$, we get
$
{n \choose 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!}
$.

Summing over the different boxes, we have \\
$\Prob{\geq k \mbox{ balls fall into {\em some\/} box}} \leq n/k!$.

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

\ppart
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(\lg n)$, the denominator is growing 
faster than the numerator and this expression is asmyptotically~0.
When $k=o(\lg 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\lg k = \lg n$.
Iterating this once, we get\\
$k= \lg n/\lg k = \lg n/\lg (\lg n/\lg k) = 
\lg n/(\lg \lg n -\lg \lg k) \approx \lg n/\lg \lg n$
since $k=o(\lg n)$.

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

\eparts


\end{problems}

\end{document}
