\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Lecture notes for weeks 13 and 14.}

%\newcommand{\rem}{\operatorname{\,rem\,}}

%\newcommand{\pr}[1]{\mathop{\textup{Pr}}\nolimits\left\(#1\right\)}
%\newlength{\strutheight}
%\newcommand{\prob}[1]{\mathop{\textup{Pr}} \nolimits \left( #1 \right)}
%\newcommand{\prsub}[2]{\mathop{\textup{Pr}_{#1}}\nolimits\left(#2\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{\paren}[1]{\left(#1\right)}
%\newcommand{\comment}[1]{}
%\newcommand{\intersect}{\cap}
%\newcommand{\union}{\cup}
%\newcommand{\card}[1]{\lvert #1 \rvert}
%%\newcommand{\pr}[1]{\Pr(#1)}
%%\newcommand{\prob}[1]{\operatorname{Pr}(#1)}
%%\newcommand{\prcond}[2]{\operatorname{Pr}(#1 \mid #2)}
%%\newcommand{\prsub}[2]{\operatorname{Pr}_{#1}(#2)}
%\newcommand{\cE}{\mathcal{E}}
%\renewcommand{\setminus}{-}
%\renewcommand{\complement}[1]{\overline{#1}}
%\newcommand{\prcond}[2]{\pr{#1\mid#2}}
%
\begin{document}
\problemset{10}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\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{\ex}[1]{\Ex\left[#1\right]}
%\newcommand{\expectsq}[1]{{\Ex}^2\left[#1\right]}
%\newcommand{\expcond}[2]{\expect{#1\mid#2}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse


\begin{problem}
Suppose you flip $n$ fair, independent coins.  Let the random variable
$X$ be the number of heads that come up.

\bparts

\ppart What is the exact value of $\pr{X \leq k}$, the probability of
flipping $k$ or fewer heads?  Your answer need not be in closed form.

\solution{
\[
\frac{\binom{n}{k} + \binom{n}{k-1} + \ldots + \binom{n}{0}}{2^n}
\]
}

\ppart Suppose $k < n / 2$.  Prove that:
%
\[
\pr{X \leq k} \leq \frac{n - k + 1}{n - 2k + 1} \cdot \pr{X = k}
\]
%
(Upper bound your previous answer with an infinite geometric sum and
then evaluate the sum.)

\solution{We can upper bound the numerator in the preceding answer as
follows:
%
\begin{align*}
\lefteqn{\binom{n}{k} + \binom{n}{k-1} + \ldots + \binom{n}{0}} \quad \\
    & = \binom{n}{k}
        + {\textstyle \frac{k}{n-k+1}} \binom{n}{k}
        + {\textstyle \frac{k(k-1)}{(n-k+1)(n-k+2)}} \binom{n}{k}
        + {\textstyle \frac{k(k-1)(k-2)}{(n-k+1)(n-k+2)(n-k+3)}} \binom{n}{k}
        + \ldots \\
    & \leq \binom{n}{k} \cdot \paren{
        1 + \frac{k}{n-k+1} + \frac{k^2}{(n-k+1)^2}
          + \frac{k^3}{(n-k+1)^3} + \ldots} \\
    & = \binom{n}{k} \cdot \frac{1}{1 - \frac{k}{n-k+1}} \\
    & = \binom{n}{k} \cdot \frac{n-k+1}{n-2k+1}
\end{align*}
%
(Note that the geometric sum converges only if $k < n/2$.)  Therefore:
%
\[
\pr{X \leq k} \leq \frac{n - k + 1}{n - 2k + 1} \cdot \pr{X = k}
\]
}

\ppart If you flip a coin 100 times, the probability of flipping
exactly 30 heads is approximately 23 out of a million.  
First
use the union bound to give an upper
bound on the probability of flipping \textit{30 or fewer} heads.
Then use the bound above to get a better upper bound
on the same quantity.

\solution{
The union bound gives $31 \cdot 23 \cdot 10^{-6} 
 = 713 \cdot 10^{-6}$.

Applying the bound above gives:
%
\[
\paren{23 \cdot 10^{-6}} \cdot \frac{100 - 30 + 1}{100 - 2 \cdot 30 + 1}
    \approx 40 \cdot 10^{-6}
\]
%
The actual value is about $39.25 \cdot 10^{-6}$.
}

\eparts

\end{problem}

\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse

\begin{problem} Each 6.042 final exam will be graded according to a
rigorous procedure:

\begin{itemize}

\item With probability $\frac{4}{7}$ the exam is graded by a {\em TA},
with probability $\frac{2}{7}$ it is graded by a {\em lecturer}, and
with probability $\frac{1}{7}$, it is accidentally dropped behind the
radiator and arbitrarily given a score of 84.

\item {\em TAs} score an exam by scoring each problem individually and
then taking the sum.

\begin{itemize}

\item There are ten true/false questions worth 2 points each.  For
each, full credit is given with probability $\frac{3}{4}$, and no
credit is given with probability $\frac{1}{4}$.

\item There are four questions worth 15 points each.  For each, the
score is determined by rolling two fair dice, summing the results, and
adding 3.

\item The single 20 point question is awarded either 12 or 18 points
with equal probability.

\end{itemize}

\item {\em Lecturers} score an exam by rolling a fair die twice,
multiplying the results, and then adding a ``general impression''
score.

\begin{itemize}

\item With probability $\frac{4}{10}$, the general impression score is 40.

\item With probability $\frac{3}{10}$, the general impression score is 50.

\item With probability $\frac{3}{10}$, the general impression score is 60.

\end{itemize}

\end{itemize}

Assume all random choices during the grading process are mutually
independent.

\bparts

\ppart What is the expected score on an exam graded by a TA?

\solution{ Let the random variable $T$ denote the score a TA would
give.  By linearity of expectation, the expected sum of the problem
scores is the sum of the expected problem scores.  Therefore, we have:
\begin{eqnarray*}
\expect{T}	& = &	10 \cdot \expect{\text{T/F score}} +
		4 \cdot \expect{\text{15pt prob score}} +
		\expect{\text{20pt prob score}} \\
	& = &
	10 \cdot \left(\frac{3}{4} \cdot 2 + \frac{1}{4} \cdot 0 \right)
	+ 4 \cdot \left( 2 \cdot \frac{7}{2} + 3 \right)
	+ \left(\frac{1}{2} \cdot 12 + \frac{1}{2} \cdot 18 \right) \\
	& = &	10 \cdot \frac{3}{2} + 4 \cdot 10 + 15 \\
	& = & 	70
\end{eqnarray*}
}

\ppart What is the expected score on an exam graded by a
lecturer?

\solution{
Now we find the expected value of $L$, the score a lecturer would
give.  Employing linearity again, we have:
\begin{eqnarray*}
\expect{L}	& = &	\expect{\text{product of dice}} + \expect{\text{general impression}} \\
	& = &	\left(\frac{7}{2}\right)^2 + \left(
		\frac{4}{10} \cdot 40 + 
		\frac{3}{10} \cdot 50 + 
		\frac{3}{10} \cdot 60 \right) \\
	& = &	\frac{49}{4} + 49 \\
	& = &	61 \frac{1}{4}
\end{eqnarray*}
}

\ppart What is the expected score on a 6.042 final exam?

\solution{Let $X$ equal the true exam score.  The total expectation
law implies:
\begin{eqnarray*}
\expect{X}	& = &	\frac{4}{7} \cdot \expect{T} +
		\frac{2}{7} \cdot \expect{L} +
		\frac{1}{7} \cdot 84 \\
	& = &	\frac{4}{7} \cdot 70 +
		\frac{2}{7} \cdot \left(\frac{49}{4} + 49\right) +
		\frac{1}{7} \cdot 84 \\
	& = &	40 + \frac{7}{2} + 14 + 12 \\
	& = &	69 \frac{1}{2}
\end{eqnarray*}
}

\eparts

\end{problem}

\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
MIT students sometimes delay laundry for a few days.  Assume all
random values described below are mutually independent.

\bparts

\ppart A \term{busy} student must complete 3 problem sets before doing
laundry.  Each problem set requires 1 day with probability $2/3$ and 2
days with probability $1/3$.  Let $B$ be the number of days a busy
student delays laundry.  What is $\expect{B}$?

Example: If the first problem set requires 1 day and the second and
third problem sets each require 2 days, then the student delays for $B
= 5$ days.

\solution{ The expected time to complete a problem
set is:
%
\[
1 \cdot \frac{2}{3} + 2 \cdot \frac{1}{3} = \frac{4}{3}
\]
%
Therefore, the expected time to complete all three problem sets is:
%
\begin{align*}
\expect{B}
    & = \expect{\text{pset1}} + \expect{\text{pset2}} + \expect{\text{pset3}} \\
    & = \frac{4}{3} + \frac{4}{3} + \frac{4}{3} \\
    & = 4
\end{align*}
}

\ppart A \term{relaxed} student rolls a fair, 6-sided die in the
morning.  If he rolls a 1, then he does his laundry immediately (with
zero days of delay).  Otherwise, he delays for one day and repeats the
experiment the following morning.  Let $R$ be the number of days a
relaxed student delays laundry.  What is $\expect{R}$?

Example: If the student rolls a 2 the first morning, a 5 the second
morning, and a 1 the third morning, then he delays for $R = 2$ days.

\solution{If we regard doing laundry as a failure, then the mean time
to failure is $1 / (1/6) = 6$.  However, this counts the day laundry
is done, so the number of days delay is $6 - 1 = 5$.  Alternatively,
we could derive the answer as follows:
%
\begin{align*}
\expect{R}
    & = \sum_{k=0}^{\infty} \pr{R > k} \\
    & = \frac{5}{6} + \paren{\frac{5}{6}}^2 + \paren{\frac{5}{6}}^3 + \ldots \\
    & = \frac{5}{6} \cdot
            \paren{1 + \frac{5}{6} + \paren{\frac{5}{6}}^2 + \ldots} \\
    & = \frac{5}{6} \cdot \frac{1}{1 - 5/6} \\
    & = 5
\end{align*}
}

\ppart Before doing laundry, an \term{unlucky} student must recover
from illness for a number of days equal to the product of the numbers
rolled on two fair, 6-sided dice.  Let $U$ be the expected number of
days an unlucky student delays laundry.  What is $\expect{U}$?

Example: If the rolls are 5 and 3, then the student delays for $U =
15$ days.

\solution{Let $D_1$ and $D_2$ be the two die rolls.  Recall that a die
roll has expectation $7/2$.  Thus:
%
\begin{align*}
\expect{U}
    & = \expect{D_1 \cdot D_2} \\
    & = \expect{D_1} \cdot \expect{D_2} \\
    & = \frac{7}{2} \cdot \frac{7}{2} \\
    & = \frac{49}{4}
\end{align*}
}

\ppart A student is \term{busy} with probability $1/2$, \term{relaxed}
with probability $1/3$, and \term{unlucky} with probability $1/6$.
Let $D$ be the number of days the student delays laundry.  What is
$\expect{D}$?

\solution{
\[
\expect{D} = \frac{1}{2} \expect{B} + \frac{1}{3} \expect{R} + \frac{1}{6} \expect{U}
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
There are about 250,000,000 people in the United States who might use
a phone.  Assume that each person is on the phone during each minute
mutually independently with probability $p = 0.01$.

(To keep the problem simple, we are putting aside the fact that people
are on the phone more often at certain times of day and on certain
days of the year.)

\bparts

\ppart What is the expected number of people on the phone at a given
moment?

\solution{Let $I_i$ be an indicator for the event that the $i$-th
person is one the phone.  The number of people on the phone is then:
\[
\sum_{i=1}^{250,000,000} I_i.
\]
The expectation of this sum is $250,000,000 \cdot 0.01 = 2,500,00$ by
linearity of expectation.
}

\ppart Suppose that we construct a phone network whose capacity is a
mere \textbf{one percent} above the expectation.  Upper bound the
probability that the network is overloaded in a given minute.  (Use
the approximation formula given in the notes.  You may need to
evaluate this expression in a clever way because of the size of
numbers involved.  For example, you could first evaluate the {\em
logarithm} of the given expression.)

\solution{The network is overloaded if the fraction of people calling
is greater than $1.01 \cdot 0.01 = 0.0101$.  In complementary terms,
the network is overloaded if the fraction of people {\em not} calling
is less than $1 - 0.0101 = 0.9899$.  Define the following variables:
\begin{eqnarray*}
n & \eqdef & 250,000,000 \quad \text{people in the US} \\
p & \eqdef & 0.99 \quad \text{prob. not on phone} \\
\alpha & \eqdef & 0.9899 \quad \text{min. allowable fraction not on phone}
\end{eqnarray*}

In these terms, the solution to the problem is $F_{n,p}(\alpha n)$.
We can upper bound this approximately using the formula from the
notes:
\[
F_{n,p}(\alpha n) \approx
	\frac{1 - \alpha}{1 - \alpha / p} \cdot
	\frac{2^{n H(\alpha)}}{\sqrt{2 \pi \alpha (1 - \alpha) n}} 
	\cdot p^{\alpha n} (1-p)^{(1 - \alpha) n}.
\]
By first evaluating the logarithm of this expression, we find that
this is about $e^{-120}$.}

\ppart What is the expected number of minutes (approximately) until
the system is overloaded for the first time?

\solution{Applying the ``expected time to failure'' formula with
probability $p = e^{-120}$ gives $1 / p = e^{120}$.}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\iffalse
\begin{problem}
I have twelve cards:
%
\[
\fbox{1}\ \fbox{1}\quad \fbox{2}\ \fbox{2}\quad \fbox{3}\ \fbox{3}\quad
\fbox{4}\ \fbox{4}\quad \fbox{5}\ \fbox{5}\quad \fbox{6}\ \fbox{6}
\]
%
I shuffle them and deal them in a row.  For example, I might get:
%
\[
\fbox{1}\ \fbox{2}\ \fbox{3}\ \fbox{3}\ \fbox{4}\ \fbox{6}\ 
\fbox{1}\ \fbox{4}\ \fbox{5}\ \fbox{5}\ \fbox{2}\ \fbox{6}
\]
%
What is the expected number of adjacent pairs with the same value?  In
the example, there are two adjacent pairs with the same value, the 3's
and the 5's.  
\end{problem}

\solution{Consider an adjacent pair.  The left card matches only one
of the other 11 cards, which is equally likely to be in any of the 11
other positions.  Therefore, the probability that an adjacent pair
matches is $1/11$.  Since there are 11 adjacent pairs, the expected
number of matches is $11 \cdot 1/11 = 1$ by linearity of expectation.}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





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


\begin{problem}
We are given a set of  $n$ distinct 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, perform
an ``update'':  that is, change the
current maximum to be the current element. 
Either way, change the current element to 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{problem} In a certain card game, each card has a point value.

\begin{itemize}

\item Numbered cards in the range 2 to 9 are worth five points each.

\item The card numbered 10 and the face cards (jack, queen, king) are
worth ten points each.

\item Aces are worth fifteen points each.

\end{itemize}

\bparts

\ppart Suppose that you thoroughly shuffle a 52-card deck.  What is the
expected total point value of the three cards on the top of the deck after
the shuffle?

\solution{Let the random variable, $X$, be the total point value of the
three cards on the top of the deck.  Then we can write:
\[
X  =  X_1 + X_2 + X_3
\]
where the random variables $X_1$, $X_2$, and $X_3$ are the point values of
the first, second, and third cards.  By the definition of expectation:
\begin{eqnarray*}
\expect{X_i}
	& = &	\sum_{r \in X_i(S)} r \cdot \pr{X_i = r} \\
	& = &	5 \cdot \frac{8}{13} + 10 \cdot \frac{4}{13} +
		15 \cdot \frac{1}{13} \\
	& = &	\frac{95}{13}
\end{eqnarray*}

Now we can solve the problem by taking the expected value of both
sides of our original equation and then using linearity of
expectation:
\begin{eqnarray*}
\expect{X}	& = &	\expect{X_1 + X_2 + X_3} \\
	& = &	\expect{X_1} + \expect{X_2} + \expect{X_3} \\
	& = &	\frac{95}{13} + \frac{95}{13} + \frac{95}{13} \\
	& = &	\frac{285}{13}
\end{eqnarray*}
}

\ppart Suppose that you throw out all the red cards and shuffle the
remaining 26-card, all-black deck.  Now what is the expected total
point value of the top three cards?  (Note that drawing three aces,
for example, is now impossible!)

\solution{The expected point value is the same as before, since
expected point value of a single card is unchanged.  Nothing in our
solution assumed a 52 card deck.}

\eparts

\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$?
(Assume for simplicity that $n$ is divisible by $k$.)

\solution{
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}
\expect{\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}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%  Fall 2000     %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
%[[[expectation, variance, Chebyshev]]]
% Spring 00, problem set 10.5, problem 4
% Fall 01, problem set 12, problem 2

\begin{problem}
The hat-check staff has had a long day, and at the end of the party they
decide to return people's hats at random.  Suppose that $n$ people have
their hats returned at random.  We previously showed that the expected
number of people who get their own hat back is 1, irrespective of the
total number of people.  In this problem we will calculate the variance in
the number of people who get their hat back.

Let $X_i = 1$ if the $i$th person gets his or her own hat back and 0
otherwise.  Let $S_n \eqdef \sum_{i=1}^n X_i$, so $S_n$ is the total number
of people who get their own hat back.  Show that

\begin{problemparts}

\problempart $\expect{X_i^2} = 1/n$.

\solution{
$X_i = 1$ with probability $1/n$ and 0 otherwise. Thus $X_i^2 = 1$
with probability $1/n$ and 0 otherwise. So $\expect{X_i^2} = 1/n$.
}

\problempart $\expect{X_i X_j} = 1/n(n-1)$ for $i \neq j$.

\solution{
The probability that $X_i$ and $X_j$ are both 1 is $1/n \cdot 1/(n-1) =
1/n(n-1)$.  Thus $X_i X_j = 1$ with probability $1/n(n-1)$, and is zero
otherwise.  So $\expect{X_i X_j} = 1/n(n-1)$.
}

\problempart $\expect{S_n^2} = 2$. \hint Use (a) and (b).

\solution{
\begin{eqnarray*}
\expect{S_n^2} & = & \sum_i \expect{X_i^2} + \sum_i \sum_{j \neq i} \expect{X_i X_j} \\
         & = & n \cdot \frac{1}{n} + n(n-1) \cdot \frac{1}{n(n-1)} \\
         & = & 2.
\end{eqnarray*}}


\problempart $\variance{S_n} = 1$.

\solution{
\begin{eqnarray*}
\variance{S_n} & = & \expect{S_n^2} - \expectsq{S_n} \\ 
       & = & 2 - (n (1/n))^2 \\
       & = & 2 - 1 \\
       & = & 1.
\end{eqnarray*}
}

\problempart Explain why you cannot use the variance of sums formula to
calculate $\variance{S_n}$.

\solution{The indicator random variables, $X_i$, are not even pairwise
independent.  This can be seen by comparing the marginal and conditional
probability of a particular person, Alice, getting her hat back.  The
marginal probability, unconditioned on any other events, is $1/n$ as we've
computed before.  However, if compute this probability conditioned on the
event that a second person, Bob, got his hat back, we find that the
probability of Alice getting her hat back is $1/(n-1)$.}

\problempart Using Chebyshev's Inequality, show that $\pr{S_n \geq 11}
\leq .01$ for any $n \geq 11$.

\solution{
\begin{eqnarray*}
\pr{S_n \geq 11} &=& \pr{S_n - \expect{S_n} \geq 11 - \expect{S_n}} \\
                 &=& \pr{S_n - \expect{S_n} \geq 10} \\
                 &\leq& \frac{\variance{S_n}}{10^2} = .01
\end{eqnarray*}

Note that the $X_i$'s are Bernoulli variables but are \emph{not}
independent, so $S_n$ does not have a binomial distribution and the
binomial estimates from Lecture Notes do not apply.
}


\end{problemparts}
\end{problem}



\begin{problem}
Let $R_1$ and $R_2$ be independent random variables, and $f_1$ and $f_2$ be any
functions such that $\domain{f_i} = \codomain{R_i}$ for $i=1,2$.  Prove that
$f_1(R_1)$ and $f_2(R_2)$ are independent random variables.

\solution{The event $[f_i(R_i) = a]$ is the disjoint union of all the events
$[R_i = r]$ for $r \in f_i^{-1}(a)$, so
\[
\pr{f_i(R_i) = a} = \sum_{r \in f_i^{-1}(a)} \pr{R_i = r}.
\]
Also, the event $[f_1(R_1) = a \mbox{ and } f_2(R_2) = b]$ is the disjoint
unon of the events $[R_1 = r\mbox{ and }R_2 = t]$ for $(r,t) \in
f_1^{-1}(a) \times f_2^{-1}(b)$.  Hence,
\begin{eqnarray*}
\lefteqn{\pr{f_1(R_1) = a \mbox{ and } f_2(R_2) = b}}\\
& = & \sum_{(r,t) \in f_1^{-1}(a) \times f_2^{-1}(b)}
                \pr{R_1 = r \mbox{ and } R_2 = t}\\
& = & \sum_{(r,t) \in f_1^{-1}(a) \times f_2^{-1}(b)} \pr{R_1 = r} \pr{R_2 = t}
            \hspace{0.5in}\mbox{[because $R,R_2$ independent]}\\
& = & \sum_{t \in f_2^{-1}(b)} \sum_{r \in f_1^{-1}(a)} \pr{R_1 = r} \pr{R_2 =
               t}\\
& = & \sum_{t \in f_2^{-1}(b)} \pr{R_2 = t}
            \paren{\sum_{r \in f_1^{-1}(a)} \pr{R_1 = r}}\\
& = & \sum_{t \in f_2^{-1}(b)} \pr{R_2 = t} (\pr{f(R) = a})\\
& = & \pr{f(R) = a} \sum_{t \in f_2^{-1}(b)} \pr{R_2 = t}\\
& = & \pr{f(R) = a} \pr{f_2(R_2) = b}
\end{eqnarray*}
}
\end{problem}

\begin{problem}
Let $A,B,C$ be events, and let $I_A,I_B,I_C$ be the corresponding
indicator variables.  Prove that $A,B,C$ are mutually independent iff the
random variables $I_A,I_B,I_C$ are mutually independent.

\solution{
($\implies$):  
\begin{eqnarray*}
\pr{I_A = 1 \wedge I_B= 0 \wedge I_C = 1} & = & \pr{A \intersect \bar{B}
\intersect C}\\
& = & \pr{A \intersect C} - \pr{A \intersect B \intersect C}\\
& = & \pr{A} \cdot \pr{C} - \pr{A} \cdot \pr{B} \cdot \pr{C}\\
& = & \pr{A} \cdot \pr{C} (1 -  \pr{B})\\
& = & \pr{A} \cdot \pr{C} \pr{\bar{B}}\\
& = & \pr{I_A = 1} \cdot \pr{I_C = 1} \pr{I_B = 0}\\
& = & \pr{I_A = 1} \cdot \pr{I_B = 0} \cdot \pr{I_C = 1}
\end{eqnarray*}
and similarly for any other three binary values in place of 101.

($\longleftarrow$):  
\begin{eqnarray*}
\pr{A \intersect B \intersect C} & = & 
        \pr{I_A = 1 \wedge I_B = 1 \wedge I_C = 1}\\
& = & \pr{I_A = 1} \cdot \pr{I_B = 1 } \cdot \pr{I_C = 1}\\
& = & \pr{A} \cdot \pr{B} \cdot \pr{C}
\end{eqnarray*}
Also,
\begin{eqnarray*}
\pr{A \intersect B} & = & \pr{A \intersect B \intersect C}
                       + \pr{A \intersect B \intersect \bar{C}}\\
& = & \pr{I_A = 1 \wedge I_B = 1 \wedge I_C = 1} + \pr{I_A = 1 \wedge I_B = 1 \wedge I_C = 0}\\
& = & \pr{I_A = 1} \cdot \pr{I_B = 1} \cdot \pr{I_C = 1}
       + \pr{I_A = 1} \cdot \pr{I_B = 1} \cdot \pr{I_C = 0}\\
& = & \pr{A} \cdot \pr{B} \cdot \pr{C} + \pr{A} \cdot \pr{B}
                       \cdot \pr{\bar{C}}\\
& = & \pr{A} \cdot \pr{B} (\pr{C} + \pr{\bar{C}})\\
& = & \pr{A} \cdot \pr{B}
\end{eqnarray*}
and similarly for ${B \intersect C}$ and ${A \intersect C}$.
}
\end{problem}



\end{document}
