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

\addtolength{\topmargin}{-.35in}
\setlength{\textheight}{9in}

\newcommand{\problm}{\problem \rm}
\renewcommand{\ppart}{\problempart \rm}
\newcommand{\mystrut}{\rule{0pt}{14pt}}

\newcommand{\E}{\mbox{\bf E}}
\renewcommand{\Var}{\mbox{\bf Var}}
\renewcommand{\Pr}{\mbox{\bf Pr}}

\begin{document}

\psol{13}{May 17, 1997}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts

\ppart
Observe that there are $6^3 = 216$ possibilies for the values on $3$ dice.
\begin{enumerate}
\item The number of ways to get $3$ different values is $6 \cdot 5
\cdot 4 = 120$.  So the probability is $\frac{120}{216} = \frac{5}{9}$.
\item The number of ways to get two identical values is ${3 \choose 2}
(6 \cdot 1) \cdot 5 = 90$.  So the probability is $\frac{90}{216} =
\frac{5}{12}$.   
\item The number of ways to get one value is $6$.  So the probability
is $\frac{6}{216} = \frac{1}{36}$.
\end{enumerate}

\ppart
If all three dice have different values, the net winning is \$3 - \$3
= \$0.  If
two dice have the same value (and the third has a different one), the
net winning is \$2 + \$1 - \$4 = -\$1.  
If all dice have the same value, the net winning
is \$3 - \$5 = -\$2.  So the expected return is $\frac{5}{9}\cdot 0 +
\frac{5}{12} \cdot (-1) + \frac{1}{36} (-2) = - \$ \frac{17}{36}$.

\ppart
Let $X_i$ be the random variable whose value is the net winning if we
wager \$1 on the value $i$.  Note that $X_1 + X_2 + X_3 + X_4 + X_5 +
X_6$ is the random variable whose value is the net winning if we wager
\$1 on each of the $6$ values.  Now $\E[X_1] = \E[X_2] = \cdots =
\E[X_6]$, so by the linearity of expectation,
the expected winning is $\frac{1}{6} \cdot (-\frac{17}{36}) = -\$
\frac{17}{216}$. 

\ppart
The game will be fair if $\E[X_i] = 0$.  This is the same as requiring $\E[X_1 + \cdots + X_6]$ = 0, i.~e., that the game described in the second part of the question is fair.  
If all three dice have different values, the net winning is $3i_1 - 3$.  If
two dice have the same value (and the third has a different one), the
net winning is $2i_2 + i_3 - 4$.
If all dice have the same value, the net winning
is $i_3 - 5$.  So the expected return is $\frac{5}{9} \cdot (3i_1 - 3) +
\frac{5}{12} \cdot (i_1 + i_2 - 4) + \frac{1}{36} (i_3 - 5) =
\frac{25}{12}i_1 + \frac{5}{12}i_2 + \frac{1}{36}i_3 - \frac{125}{36}$.
For the game to be fair the expectation has to be zero.  So this
translates as $75i_1 + 15i_2 + i_3 = 125$.  
A possible choice would be $(i_1, i_2, i_3) = (1,3,5)$.  (There are
other solutions.)
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts
\ppart

At any step, the probability that there is a failure in either
component is $p + p - p^2 = 2p - p^2$.  So $\E[X] = 1/(2p - p^2)$.

\ppart

At any step, the probability that there is a failure in both
components is $p^2$.  So $\E[Y] = 1/p^2$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts
\ppart
Let $X_i$ be the random variable whose value is $1$ if student $i$ is
ranked higher on list from grad school B than for grad school A and
$0$ otherwise.  Now if student $i$ has rank $r$ for grad school B,
then the probability that his/her rank for grad school A is lower is
$(r-1)/n$.  In other words, we know that $\Pr[$ student $i$ has
higher rank on the list for grad school B$|$ student $i$ has
rank $r$ on grad school B$] = (r-1)/n$.  Now $\Pr[\mbox{student $i$
has rank $r$ on grad school B}] = 1/n$.  So by the theorem of total
probability, $\Pr[\mbox{student $i$ has higher rank on list for grad
school B}] = \sum_{r=1}^n \frac{r-1}{n} \cdot \frac{1}{n} =
\frac{n-1}{2n}$.  

By the linearity of expectation, the expected number of students that
have a higher rank on the list for grad school B is $\E[X_1] + \cdots
+ \E[X_n] = \frac{n-1}{2}$.

Another way to do this is to observe that the expected number of
students with higher rank is the same as the number with lower rank.
The expected number of students with the same rank, by linearity of
expectation, is $1$.  (The probability that student $i$ is ranked the
same in both schools is $1/n$.)  This gives us the same answer as before.

\ppart

Let $X_i$ be the random variable whose value is $1$ if student $i$ is
ranked at least $k$ higher on list from grad school B than for grad
school A and $0$ otherwise.  Now if student $i$ has rank $r$ (where $r
> k$) for grad school B,
then the probability that his/her rank for grad school A is at least
$k$ lower is
$(r-k)/n$.  In other words, we know that $\Pr[$student $i$ has
at least $k$ higher rank for grad school B $|$ student $i$ has
rank $r$ on grad school B$] = (r-k)/n$.  Now $\Pr[$student $i$
has rank $r$ on grad school B$] = 1/n$.  So by the theorem of total
probability, $\Pr[$student $i$ has higher rank on list for grad
school B$] = \sum_{r=k}^n \frac{r-k}{n} \cdot \frac{1}{n} =
\frac{(n-k)(n-k+1)}{2n^2}$.

By the linearity of expectation, the expected number of students that
have a higher rank on the list for grad school B is $\E[X_1] + \cdots
+ \E[X_n] = \frac{(n-k)(n-k+1)}{2n}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts
\ppart
Let $X_i$ be the indicator random variable whose value is $1$ if box
$i$ is empty and is $0$ otherwise.  Now the probability that box $i$
is empty is the probabilility that all $n$ balls land in all other
boxes, which is $(1 - \frac{1}{n})^n$.  So $\E[X_i] = (1 -
\frac{1}{n})^n$.  By the linearity of expectation, the expected
number of empty boxes is $\E[X_1] + \cdots + \E[X_n] = n(1-\frac{1}{n})^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:
$\Pr[ \cup_S \E[S]] \leq \sum_S \Pr[\E[S]]$.
For any fixed set $S$, $\Pr[\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 \\
$\Pr[\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, 
\[\Pr[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$), 
\[
\Pr[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*}
\Pr[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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

Let $X$ be the random variable whose value is the roll in the first
stage.  Let $Y_1, Y_2, \ldots, Y_X$ be the random variable whose values
are the rolls in the second stage.  Define $Y = Y_1 + \cdots + Y_X$.
Let $Z_1, Z_2, \ldots, Z_Y$ be the random variable whose values are
the rolls in the third stage.  Define $Z = Z_1 + \cdots + Z_Y$.  We
want to find $\E[Z]$.  Now all the rolls are mutually independent, so
we can use Wald's theorem to get $\E[Y] = \E[X]\E[Y_i] =
(\frac{7}{2})^2$.  Since $Y$ is determined by rolls that are
independent of the rolls in the third stage,
$Y$ and $Z_i$ are independent.  So we apply Wald`s theorem again to
get $\E[Z] = \E[Y]\E[Z_i] = (\frac{7}{2})^3.$

The answer is $(\frac{7}{2})^3$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts

\ppart
Observe that $\Pr[\max(X,Y) = i] = \Pr[X = i \mbox{ and } Y < i] +
\Pr[X < i \mbox{ and } Y = i] + \Pr[X = Y = i] = \frac{1}{n} \cdot
\frac{i-1}{n} + \frac{i-1}{n} \cdot \frac{1}{n} + \frac{1}{n} \cdot
\frac{1}{n} = \frac{2i-1}{n^2}$.  

This means that $\E[\max(X,Y)] = \sum_{i=1}^n \frac{i(2i-1)}{n^2} =
\frac{1}{n^2} \sum_{i=1}^n (2i^2 - i) = \frac{1}{n^2}(
\frac{2n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}) = \frac{(n+1)(4n-1)}{6n}$.

\ppart
Observe that $\E[\max(X,Y)] + \E[\min(X,Y)] = \E[\max(X,Y) +
\min(X,Y)] = \E[X + Y] = \E[X] + \E[Y]$.  Now $\E[X] = \E[Y] =
\frac{n+1}{2}$.  so $\E[\min(X,Y)] = n+1 - \frac{(n+1)(4n-1)}{6n} =
\frac{(n+1)(2n+1)}{6n}$. 

\ppart
Note that $\Var[X - Y] = \Var[X] + \Var[Y]$ and that $\Var[X] =
\Var[Y] = \E[X^2] - (\E[X])^2 = \sum_{i=1}^n \frac{i^2}{n} -
(\frac{n+1}{2})^2 = \frac{(n+1)(2n+1)}{6} - \frac{(n+1)^2}{4} =
\frac{n^2 - 1}{12}$.  So $\Var[X - Y] = \frac{n^2 - 1}{6}$.

\ppart
Now $\Var[|X - Y|] = \E[|X - Y|^2] - (\E[|X - Y|])^2$.  But $\E[|X -
Y|^2] = \E[(X - Y)^2] = \Var[X - Y] + (\E[X - Y])^2 = \Var[X - Y] =
\frac{n^2 - 1}{6}$ (since $\E[X - Y] = \E[X] - \E[Y] = 0$).  So all we
need is to compute $\E[|X - Y|]$.  

But $|X - Y| = \max(X,Y) - \min(X,Y)$, so by linearity of expectation, $\E[|X - Y| = \E[\max(x,y)] - \E[\min(x,y)] = \frac{(n^2-1)}{3n}$.

This means that $\Var[|X - Y|] = \frac{n^2 - 1}{6} - (\frac{n^2 -
1}{3n})^2 = \frac{(n^2 - 1)(n^2 + 2)}{18 n^2}$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts

\ppart
There are many examples to see that $X$ and $Y$ are not independent.
An easy one is to note that $\Pr[X = 2]\Pr[Y = 1] \ne 0$ 
but $\Pr[XY = 2] = \Pr[X^3 = 2] = 0$.  

To see that $\E[XY] = \E[X] \E[Y]$, note that $\E[X] = 0$ and $\E[XY]
= \E[X^3] = 0$ since $X$ and $X^3$ are both symmetrical.

\ppart
We have that $\Var[X + Y] = \E[(X+Y)^2] - (\E[X+Y])^2 = \E[X^2 + 2XY +
Y^2] - (\E[X]+ \E[Y])^2 = \E[X^2] - (\E[X])^2 + \E[Y^2] - (\E[Y])^2 +
2\E[XY] - 2\E[X]\E[Y] = \Var[X] + \Var[Y]$. 

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \mbox{}

\bparts

\ppart
The expected number of heads of $50$.  So the probability that the
number of heads is at least $70$ is at most $50/70 = 0.71$.

\ppart
Let $X_i$ be the random variable whose value is $1$ if the $i$th coin
flip is heads.  Then $\Var[X_i] =  1/2 - (1/2)^2 = 1/4$.  So $\Var[X_1
+ \cdots + X_100] = 100/4 = 25$.
 The variance of the number of heads is $100/4 = 25$, so the standard
deviation is $5$.  So $70$ is four times the standard deviation from
the mean.  Since the distribution is symmetric, the
probability is at most $\frac{1}{2} \cdot \frac{1}{4^2} = \frac{1}{32}$

\ppart
We apply Chernoff`s bound with $c = 70/50 = 1.4$.  This gives us that
$\alpha = \ln(1.4) + 1/1.4 - 1 = 0.05076$ and that the probability is at most $e^{-0.05076 \cdot 1.4 \cdot 50} = 0.0286$.


\eparts


\end{problems}

\end{document}




