\documentclass[11pt,twoside]{article}   
\usepackage{light}


%\hidesolutions
\showsolutions

\renewcommand{\bar}[1]{\overline{#1}}

\newcommand{\lgunion}{\bigcup}
\newcommand{\lgintersect}{\bigcap}

\newlength{\strutheight}

%\newcommand{\paren}[1]{\left(#1\right)}

\newcommand{\range}[1]{\mathop{\textup{range}}\nolimits\left(#1\right)}
\newcommand{\card}[1]{\size{#1}}

\newcommand{\prob}[1]{\mathop{\textup{Pr}} \nolimits \left( #1 \right)}
\newcommand{\prcond}[2]{%
  \ifinner \settoheight{\strutheight}{$#1 #2$}
  \else    \settoheight{\strutheight}{$\displaystyle#1 #2$} \fi%
  \mathop{\textup{Pr}}\nolimits\left(
    #1\,\left|\protect\rule{0cm}{\strutheight}\right.\,#2  \right)}

\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}

\newcommand{\Ex}{\mathop{\textup{E}}\nolimits}
\newcommand{\expect}[1]{\Ex\left[#1\right]}
\newcommand{\expectsq}[1]{{\Ex}^2\left[#1\right]}
\newcommand{\expcond}[2]{\expect{#1\mid#2}}

\begin{document}
\problemset{11}{November 24, 2004}{\textit{Friday, December 3 at \textbf{5 PM}}}

%\insolutions{\stamp}


%\problemdata
%{induction}
%{random variable}
%{distribution}
%{Eric Ho, S02}

\begin{problem}
Your TA has invented a random number generator using a bunch of red
balls, a bunch of green balls, and a bin.  This is how it works.

Initially, there is a red ball and a green ball in the bin.  Your TA
randomly removes one ball from the bin, and then puts back into the bin
two balls of the same color as the one removed.  He/she repeats this
process until there are exactly $n$ balls in the bin.  Define the random
variable
\[
R_n = \text{ number of red balls in the bin when the bin has $n$ balls.}
\]

Your TA observes that $R_n$ is a random variable taking integer values
from 1 to $n-1$ with a \emph{uniform} distribution.  Prove this.
\emph{Hint:} Induction.

\solution{
By induction on $n \ge 2$, with induction hypothesis
\[
P(n) = [R_n \text{ has a uniform distribution over $\set{1,\dots,n-1}$}].
\]

\textbf{Base case} ($n=2$): $R_2$ only takes the value 1, so is uniform on the
integers from 1 to $2-1$, as required.

\textbf{Inductive step}: Assume $P(n)$, that is, the distribution of red
balls among $n$ balls is uniform.  We need to show that the distribution
of red balls among $n+1$ balls is uniform, that is, that $\pr{R_{n+1} = j}
= 1/n$ for $1 \leq j \leq n$.

Since one ball is added at each step, we know that
\begin{itemize}
\item $R_{n+1} = R_n$ and a green ball was added as the $n+1$st ball, or
\item $R_{n+1} = R_n+1$ and a red ball was added as the $n+1$st ball.
\end{itemize}

So we can apply the Total Probability Law to calculate $\pr{R_{n+1} = j}$:
\begin{align}
\pr{R_{n+1} = j} = & \prcond{R_{n+1} = j}{R_n = j} \cdot \pr{R_{n} =
 j}\label{TP} + \\
 & \prcond{R_{n+1} = j }{R_{n} = j-1} \cdot \pr{R_{n} = j-1}.\notag
\end{align}
Now if there are exactly $j$ red balls among $n$ balls in the bin, then
the probability of picking a green ball is $(n-j)/n$.  That is,
\begin{equation}\label{g}
\prcond{R_{n+1} = j}{R_n = j} = \frac{n-j}{n}
\end{equation}
Likewise, if there were $j-1$ red balls among $n$ balls, the probability
of picking a red ball is $(j-1)/n$, so
\begin{equation}\label{r}
\prcond{R_{n+1} = j}{R_n = j-1} = \frac{j-1}{n}
\end{equation}
Also, by induction hypothesis, we have
\begin{equation}\label{u}
\pr{R_{n} = j} = \pr{R_{n} = j-1} = \frac{1}{n-1}
\end{equation}
Plugging the values from~\eqref{g},~\eqref{r},~\eqref{u}, into~\eqref{TP},
we conclude that
\[
\pr{R_{n=1} = j} =
\frac{n-j}{n}\cdot\frac{1}{n-1} + \frac{j-1}{n} \cdot \frac{1}{n-1} 
= \frac{1}{n}
\]
as required.}
\end{problem}


%\problemdata      
%        {?} % latex-friendly label for the prob.
%        {Probability-Expectation} % The topic(s) of the problem content.
%        {?} % Source (if known)
 %       {F01, TU11-5} % Usage (list ones you are aware of).
 %       {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
A biased coin will be flipped $n$ times.  The probability of Heads on each
flip is $h$, and the flips are independent.  Write simple formulas for:

\bparts
\ppart The probability of $k$ Heads.

\solution{Let $H$ be the random variable equal to the number of Heads in
$n$ trials.  Then $H$ has binomial distribution with parameters $n,h$, so
\[
\pr{H=k} = \binom{n}{k}h^k(1-h)^{n-k}
\]
for $0\leq k \leq n$.}

\ppart The probability of at least one Head.

\solution{\[
\prob{H>0}  = 1-\prob{\text{No Head}} = 1-(1-h)^n.
\]
}

\ppart The expected number of flips before the first Head.

\solution{Let $T$ be a random variable representing the number of trials
before the first Head.  Calculating $\expect{T}$ is similar to finding
mean time to failure, except that we stop after $n$ trials.

\begin{eqnarray*}
\expect{T} &=& \sum_{i=0}^{\infty} \prob{T>i} \\
           &=& \sum_{i=0}^{n-1} \prob{T>i} \\
           &=& \sum_{i=0}^{n-1} (1-h)^i\\
           &=& \frac{1-(1-h)^n}{h}.
\end{eqnarray*}
}

\eparts

\end{problem}


%\problemdata     
%{S01-PS9-8}           
%{probability-k-events, mutual independence}              
%{} 		
%{X96, S01-PS9}
%{S01 Karger} revised 11/04 by ARM

\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 throw
is independent of all the other throws.

\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{
Box $i$ is empty iff all $n$ balls land in other boxes.  The probability
that a ball will land in another box in $(n-1)/n = 1- (1/n)$, and since
the balls are thrown independently, we have
\begin{equation}\label{pxi}
\prob{X_i=1} = \paren{1 - \frac{1}{n}}^n.
\end{equation}
The $X_i$'s are not independent.  For example, 
\[
\prob{X_1=X_2=\cdots = X_n=1}=0 < \prod_{i=1}^n \prob{X_i = 1}.
\]
}

\ppart Find a constant, $c$, such that the expected number of empty boxes
is asymptotically equal ($\sim$) to $cn$.

\solution{The number of empty boxes is the sum of the $X_i$'s.  So the
expected number of empty boxes is the sum of the expectations of the
$X_i$'.  By~\eqref{pxi}, we now have
\[
\ex{\text{number of empty boxes}} = n\ex{X_1} = n\paren{1 - \frac{1}{n}}^n \sim
n\cdot\frac{1}{e}
\]
That is,
\[
c = \frac{1}{e}
\]
}

\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{Let $S$ be a set of $k$ of the $n$ balls, and let $E_S$ be the
event that each of these $k$ balls falls in the first box.  Since the
probability that a ball lands in this box is $1/n$, and the throws are
independent, we have
\begin{equation}\label{ES}
\prob{E_S}=\paren{\frac{1}{n}}^k.
\end{equation}
The event that \emph{at least} $k$ balls land in the first box is the
union of all the events $E_S$.  There are $\binom{n}{k}$ subsets, $S$, of
$k$ balls, so by the Union Bound,
\[
\prob{\text{at least $k$ balls fall in the first box}}
\leq {\binom{n}{k}} \cdot \prob{E_S}.
\]
Using the value for $\prob{E_S}$ from~\eqref{ES} in the preceding
inequality yields the required bound.
}

\ppart Let $R$ be the maximum of the numbers of balls that land in each of
the boxes.  Conclude from the previous parts that
\[
\pr{R \geq k} \leq \frac{n}{k!}.
\]

\solution{ Note that $R \geq k$ exactly when some box has at least $k$
balls.  Since the bound on the probability of at least $k$ balls in the
first box applies just as well to any box, we can apply the Union Bound to
having at least $k$ balls in at least one of the $n$ boxes:
\[
\prob{R \geq k} \leq n\prob{\text{at least $k$ balls fall in the first
box}}.
\]
So from the previous problem part, we have
\begin{align*}
\prob{R \geq k} & \leq n\binom{n}{k} \paren{\frac{1}{n}}^{k}\\
                & = n\paren{\frac{n(n-1)\cdots(n-k+1)}{k!\, n^k}}\\
                & = \frac{n}{k!}
                        \paren{\frac{n}{n} \cdot \frac{n-1}{n} \cdots \frac{n-k+1}{n}}
                    \\
                & \leq \frac{n}{k!}
\end{align*}
}

\ppart Conclude that 
\[
\lim_{n \to \infty} \pr{R \geq n^{\epsilon}} = 0
\]
for all $\epsilon >0$.

\solution{Using Stirling's formula, and the upper bound from the previous
part, we have
\[
\pr{R \geq k} \leq
\frac{n}{k!} \sim \frac{n}{\sqrt{2\pi k}(k/e)^k} \leq
\frac{n}{(k/e)^k} = \frac{ne^k}{k^k} = 
\frac{e^{k + \ln n}}{e^{k \ln k}}.
\]
Now let $k= n^{\epsilon}$.  Then the exponent of $e$ in the numerator
above is $n^{\epsilon} + \ln n$, and the exponent of $e$ in the
denominator is $n^{\epsilon} \ln n^{\epsilon}$.  Since
\[
n^{\epsilon} + \ln n = o(n^{\epsilon} \ln n^{\epsilon}),
\]
we conclude
\[
\pr{R \geq n^{\epsilon}} \leq \frac{e^{n^{\epsilon} + \ln
n}}{e^{n^{\epsilon} \ln n^{\epsilon}}} \to 0
\]
as $n$ approaches $\infty$.
}

\iffalse

\medskip

Two special cases of the Theorem are worth singling out because they come
up all the time.
\begin{corollary*}
Suppose an event has probability $1/m$.  Then the probability that the
even will occur at least once in $m$ independent trials is approximately
$1- 1/e \approx 63\%$.  There is a 50\% chance the event will occur in $n
= \log 2 m \approx 0.69m$ trials.
\end{corollary*}


\ppart
Prove the Corollary.

\solution{
From the Taylor's expansion of $e^x$, we have
\begin{equation} \label{1+xesim}
1 + x \approx e^x,
\end{equation}
for $0 \leq x \leq 1$.

In this case, $\pr{A_i}=1/m$ for $1\leq i \leq n$ and
\[
\expect{\text{\# occurrences}} = n \frac{1}{m} = \frac{n}{m}.
\]
So by the Theorem,
\[
\pr{\text{no occurrence}} \leq e^{-(n/m)},
\]
and therefore
\begin{equation}\label{1-enm}
\pr{\text{at least one occurrence}} \geq 1 - e^{-(n/m)}.
\end{equation}
In fact, it follows from by~(\ref{1+xesim}), that the $\geq$
in~(\ref{1-enm}) is an approximate equality.

So if the number, $n$ of trials is $m$, we have
\[
\pr{\text{at least one occurrence}} \approx 1- e^{-(m/m)} = 1-\frac{1}{e}.
\]

If we want
\[
1 - e^{-(n/m)} \approx \pr{\text{at least one occurrence}} \approx
\frac{1}{2},
\]
then we need
\[
e^{-(n/m)} \approx \frac{1}{2},
\]
so taking log's we conclude
\[
n \approx m\log 2.
\]
}

\fi

\eparts

\end{problem}


%F95 pset 11

\begin{problem}
We are given a set of  $n$ positive integers.  We then determine the
maximum of these numbers by the following procedure:

Randomly arrange the numbers in a sequence.

Let the ``current maximum'' initially be the first number in the sequence
and the ``current element'' be the second element of the sequence.
If the current element is greater than the current maximum, update the
current maximum to be the current element, and let the current element be
the next element of the sequence.  Repeat this process until there is no
next element.

Prove that the expected number of updates is $\sim \ln n$.

\emph{Hint:} Let $M_i$ be the indicator variable for the event that the
$i$th element of the sequence is bigger than all the previous elements in
the sequence.

\solution{Note that the number of times we update the current maximum is
precisely $M= M_1 + \ldots + M_n$.  Since expectation is a linear
operator, we can compute $\expect{M}$ by finding $E(M_i)$ for all $i$ and
summing them up.  Note also that since $M_i$ is an ``indicator'' variable,
we only have to find $\pr{M_i=1}$.  In a random permutation, this happens
with probability $1/i$.  Why?  Because all permutations of the first $i$
numbers in the sequence are equally likely, and the largest among them
occurs as the last element of the permutation in $1/i$ of the cases.  Thus
\begin{eqnarray*}
\expect{M} & = & \sum_i \pr{M_i=1} \\
     & = & \sum_{i=1}^n 1/i \\
     & = & H_n \sim \ln n,
\end{eqnarray*}
where $H_n$ is the $n$th Harmonic number.
}
\end{problem}


%Feller, exercises on expectation
%(slightly revised from Fall95, pset 11)

\begin{problem}  A true story from World War II:

The army needs to identify soldiers with a disease called ``klep''.  There
is a way to test blood to determine whether it came from someone with
klep.  The straightforward approach is to test each soldier individually.
This requires $n$ tests, where $n$ is the number of soldiers.  A better
approach is the following: group the soldiers into groups of $k$.  Blend
the blood samples of each group and apply the test once to each blended
sample.  If the group-blend doesn't have klep, we are done with that group
after one test.  If the group-blend fails the test, then someone in the
group has klep, and we individually test all the soldiers in the group.

Assume each soldier has klep with probability, $p$, independently of all
the other soldiers.

\bparts

\ppart What is the expected number of tests as a function of $n$, $p$, and
$k$?

\solution{Assume for simplicity that $n$ is divisible by $k$.  so there are
$n/k$ groups of size $k$ each.  Let $X_i$ be a random variable that denotes
the number of tests performed in group $i$.  $X_i$ takes value $1$ with
probability $(1-p)^k$ and value $k+1$ with probability $1-(1-p)^k$.  Hence
the expected number of tests is
\begin{equation}\label{extts}
\ex{\sum_{i=1}^{n/k} X_i} = \sum_{i=1}^{n/k} E(X_i) =
(\frac{n}{k})((1-p)^k + (k+1)(1 - (1-p)^k)) = n(1 - (1-p)^k + \frac{1}{k}).
\end{equation}}

\ppart How should $k$ be chosen to minimize the expected number of
test performed, and what is the resulting expectation?

\solution{The $k$ must be chosen so that the derivative w.r.t. $k$ of the
answer from part~(a) is $0$, namely,
\[
(1-p)^k\ln(1-p) + \frac{1}{k^2} = 0.
\]
Assuming that $p$ is much smaller than $1/k$, we can approximate $(1-p)^k$
by $1$ and $\ln(1-p)$ by $-p$, giving us
\[
k \approx \sqrt{\frac{1}{p}}.
\]
In particular, $p \approx 1/k^2$ comes out much smaller than $1/k$, so our
approximations are justified (this sounds circular, but it isn't).  The
resulting expectation is approximately $n\sqrt{p}$.}

\ppart What fraction of the work does the grouping method expect to save
over the straightforward approach in a million-strong army where $1\%$
have klep?

\solution{Using the approximation from the previous part, the expected
fraction of work saved is $1-\sqrt{p}$, so for $p=0.01$, we estimate a
90\% savings.  Using the exact formula~\eqref{extts}, we find that the
fraction of work saved is $(1-p)^k-1/k$.  So for $p = 0.01$ and
$k=\sqrt{1/p}= 10$, the savings is $(1-0.01)^{10} - \sqrt{0.01} = 0.804$,
that is, more than 80\%.}

\eparts
\end{problem}


\begin{problem}
A \emph{tournament} is a digraph in which there is exactly one edge (in
one direction or the other) between every two distinct vertices.  The
vertices are called ``players,'' and if there is a edge from player $A$ to
player $B$, then player $A$ is said to have \emph{won} against player $B$.
A \emph{ranking} in the tournament is a path visiting every player exactly
once.  (That is, the first player on the path won against the second, the
second won against the third,\dots, the next-to-last won against the last.
However, it need not be the case that the first player won against the
third player, or more generally, that a player won against \emph{any}
player other than the next one in the ranking.)

\bparts

\ppart Describe a tournament of 9 players that has $3^3=27$ rankings.

\solution{Let the tournament consist of a simple cycle of 123 with edges
to 456789, a cycle 456 with edges to 789, and a cycle 789.

In this tournament, a ranking may begin with any of the three players in
the first cycle, followed by the other two players in order around the
cycle.  A ranking may continue with any of the three players in the second
cycle, followed by the other two players in order around that cycle.
Finally it may end with any of the three players in the last cycle,
followed by the other two players in order around that cycle.  So there
are exactly $3^3 = 27$ possible rankings.}

\ppart Prove that there is a tournament with 9 players that has over
$1000$ distinct rankings.  \emph{Hint:} If each players is equally likely
to win against any other player, what is the expected number of rankings?

(This problem is an instance of the {\em probabilistic method.}  It uses
probability to prove the existence of an object without constructing it.)

\solution{Call a set of two players a \emph{match}.  Construct a
tournament by independently flipping a fair coin to determine which of the
players won in each of the matches.  So for any pair of distinct players,
the probability that the first player won the match with the second player
is $1/2$.  This means that the probability that any given sequence of the
9 players is a ranking is $2^{-8}$, since the winners of the 8 successive
matches in the sequence were chosen independently.

For any sequence, $\sigma$, of the 9 players, let $X_\sigma$ be the
indicator variable for the event that $\sigma$ is a ranking.  So
\[
\ex{X_\sigma} = \pr{\sigma\text{ is a ranking}} = 2^{-8}.
\]
If $R$ is the number of rankings in the tournament, we have
\[
R = \sum_\sigma X_\sigma.
\]
Since there are $9!$ possible $\sigma$'s, conclude that
\[
\ex{R} = \sum_\sigma \ex{X_\sigma} = 9!\cdot2^{-8} = 1417.5
\]
Now there must be a tournament with a number of rankings at least as large
as the expected number, 1417.5.  Since $1417.5 > 1000$, this tournament
has the required number of rankings.}

\eparts

\end{problem}


%S02 cp14m

\begin{problem}\label{noAi}

In this problem you will check a proof of:
\begin{theorem*}
Let $E_1, E_2, \dots, E_n$ be a sequence of mutually independent events,
and let $K$ be the random variable equal to the number of these events
that occur.  The probability that none of the events occur is at most
$e^{-\expect{K}}$.
\end{theorem*}
To prove the Theorem, let $K_i$ be the indicator variable for the event
$E_i$.  Justify each line in the following derivation:

\begin{proof}
\begin{align*}
\pr{K = 0}
  & = \pr{\bar{\bigcup_{i=1}^n E_i}}\\
  & = \pr{\bigcap_{i=1}^n \bar{E_i}}\\
  & = \prod_{i=1}^n (1 - \pr{E_i})\\
  & \leq  \prod_{i=1}^n e^{-\pr{E_i}}\\
  & =  e^{\displaystyle -\sum_{i=1}^n \pr{E_i}}\\
  & =  e^{\displaystyle -\sum_{i=1}^n \expect{K_i}}\\
  & =  e^{-\expect{K}}.
\end{align*}
\end{proof}

\solution{
Note that
\begin{equation}\label{Tsum}
K = \sum_i K_i.
\end{equation}
Also, remember that
\begin{equation} \label{1+xeleq}
1 + x \leq e^x.
\end{equation}

\begin{proof}
\begin{align*}
\pr{K = 0}
  & = \pr{\bar{\lgunion_{i=1}^n E_i}}
               & \text{(def. of $K$)}\\
  & =  \pr{\lgintersect_{i=1}^n \bar{E_i}}
          & \text{(De Morgan's law)}\\
  & =  \prod_{i=1}^n \pr{\bar{E_i}} & \text{(mutual independence of $E_i$'s)}\\
  & =  \prod_{i=1}^n 1 - \pr{E_i} & \text{(complement rule)}\\
  & \leq  \prod_{i=1}^n e^{-\pr{E_i}} & \text{(by~(\ref{1+xeleq}))}\\
  & =  e^{-\sum_{i=1}^n \pr{E_i}} & \text{(exponent algebra)}\\
  & =  e^{-\sum_{i=1}^n \expect{K_i}} & \text{(expectation of indicator variable)}\\
  & =  e^{-\expect{K}}. & \text{((\ref{Tsum}) \& linearity of expectation)}
\end{align*}
\end{proof}
}
\end{problem}


\end{document}
