\documentclass[11pt]{article}	
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightyear}{2002}
\renewcommand{\coursecopyrightnames}{Prof. Albert~R.~Meyer}


\begin{document}
\inclassproblems{14, Fri}


\begin{problem}
In this problem you will check a proof of the following:
\begin{theorem}\label{th:none}
Let $A_1, A_2, \dots A_n$ be mutually independent events, and let $T$ be
the number of these events that occur.  The probability that none of the
events occur is at most $e^{-\expect{T}}$.
\end{theorem}

To prove Theorem~\ref{th:none}, note that
\begin{equation}\label{Tsum}
T = T_1 + T_2 + \dots + T_n,
\end{equation}
where $T_i$ is the indicator variable for the event $A_i$.  Also, remember
that
\begin{equation} \label{1+xeleq}
1 + x \leq e^x
\end{equation}
for all $x$ and
\begin{equation}
1 + x \approx e^x \label{1+xesim},
\end{equation}
for $0 \leq x \leq 1$.  Both~(\ref{1+xeleq}) and~(\ref{1+xesim}) follow
from the Taylor's expansion of $e^x$.

\bparts

\ppart
Justify each line in the following derivation:

\instatements{\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \bar{A_1 \union A_2 \union \cdots \union A_n}\\
  & =  \pr{\bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_n}}\\
  & =  \prod_{i=1}^n \pr{\bar{A_i}}\\
  & =  \prod_{i=1}^n 1 - \pr{A_i}\\
  & \leq  \prod_{i=1}^n e^{-\pr{A_i}}\\
  & =  e^{-\sum_{i=1}^n \pr{A_i}}\\
  & =  e^{-\sum_{i=1}^n \expect{T_i}}\\
  & =  e^{-\expect{T}}.
\end{align*}
\end{proof}
}

\solution{
\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \bar{A_1 \union A_2 \union \cdots \union A_n} & \text{(def. of $T$)}\\
  & =  \pr{\bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_n}} &
          \text{(De Morgan's law)}\\
  & =  \prod_{i=1}^n \pr{\bar{A_i}} & \text{(mutual independence of $A_i$'s)}\\
  & =  \prod_{i=1}^n 1 - \pr{A_i} & \text{(complement rule)}\\
  & \leq  \prod_{i=1}^n e^{-\pr{A_i}} & \text{(by~(\ref{1+xeleq}))}\\
  & =  e^{-\sum_{i=1}^n \pr{A_i}} & \text{(exponent algebra)}\\
  & =  e^{-\sum_{i=1}^n \expect{T_i}} & \text{(expectation of indicator variable)}\\
  & =  e^{-\expect{T}}. & \text{((\ref{Tsum}) \& linearity of expectation)}
\end{align*}
\end{proof}
}

\eparts

Two special cases of Theorem~\ref{th:none} are worth singling out
because they come up all the time.
\begin{corollary}\label{1/mtrials}
Suppose an event has probability $1/m$.  Then the probability that the
event 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}

\bparts

\ppart
Prove Corollary~\ref{1/mtrials}.

\solution{
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 Theorem~\ref{th:none},
\[
\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.
\]
}
\eparts

\end{problem}

%spider for Chernoff bound
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance18.tex}
% fall 01 tutorial 13 prob. 1

\begin{problem}
The spider (remember her from the Tutor problem) is expecting guests
and wants to catch 500 flies for her dinner.  \emph{Exactly} 100 flies
pass by her web every hour.  Exactly 60 of these flies are quite small
and are caught with probability 1/6 each.  Exactly 40 of the flies are
big and are caught with probability 3/4 each.  Assume all fly
interceptions are mutually independent.  Using this information, the
methods from lecture can show that the poor spider has only about 1
chance in 100,000 of catching 500 flies within 10 hours.

Ben Bitdiddle knows he can get the best estimate using the approximations
to the binomial distribution developed in Notes 12.  He reasons that since
60\% of the flies are small and 40\% are large, the probability that a
random fly will be caught is $0.6(1/6)+0.4(3/4) = 0.4$, so he will use the
approximation for the binomial cumulative distribution function,
$F_{1000,0.4}$, to bound the probability that the spider catches at least
500 flies in 10 hours.

As usual, Ben hasn't got it quite right.

\begin{problemparts}

\problempart According to Ben's reasoning, what is the probability that the
spider will catch all 1000 flies that show up during the 10 hours?  Show
that this is not equal to the actual probability.

\solution{
According to Ben, the probability would be $(0.4)^{1000}= (2/5)^{1000}$.  But
the actual probability is $(1/6)^{600}(3/4)^{400}$, and we don't even need
to evaluate these expressions to see that they must have different values.
}

\problempart How would you explain to Ben what is wrong with his reasoning?

\solution{Ben's reasoning would be ok if the event that a fly is large
is independent of whether the next fly is large.  That's not the case
here: after the 99th fly in the first hour, we can predict whether the
100th fly will be large or small.  The number, $R$, of flies caught in 10
hours is actually the sum of a random variable with distribution
$f_{600,1/6}$ and another variable with distribution $f_{400,3/4}$, and
$R$ not only disagrees with Ben's model on the probability that all the
flies will be caught, it does not even have a binomial distribution.}

\problempart What would the Markov bound be on the probability that the spider will
catch her quota of 500 flies?

\solution{
The expected number of flies caught is $600(1/6)+400(3/4)=400$, so
by Markov, $\pr{R\geq 500} \leq 400/500 = 0.8$.
}

\problempart What would the Chebyshev bound be on the probability that the spider will
catch her quota of 500 flies?

\solution{
The variance is $600(1/6)(5/6)+ 400(3/4)(1/4) = 1900/12 \approx 158$, so
the Chebyshev bound is
\[
\pr{R - 400 \geq 100} \leq \pr{\abs{R - 400} \geq 100} \leq
 \frac{1900/12}{100^2} = 19/1200 \approx 1/64.
\]
}

\problempart What would the Chernoff bound be on the probability that the spider
will catch her quota of 500 flies?  (You can do this without a calculator
knowing that $\ln 5/4 \approx 0.223$, $e^3 \approx 20$ and $\sqrt{e}
\approx 1.6$.)

\solution{
\begin{align*}
\pr{R \geq 500} & = \pr{R \geq (5/4)400}\\
     &\leq \textup{exp}(- ((5/4)\ln (5/4) - 5/4 + 1)400)\\
     & = \textup{exp}(-(500\ln (5/4) - 500 + 400))\\
     & \approx \textup{exp}(-(500 (0.223) - 100))\\
     & = \textup{exp}(-(111.5 - 100))\\
     & = e^{-11.5}\\
     & = \frac{\sqrt{e}}{(e^3)^4}\\
     & \approx \frac{1.6}{20^4}\\
     & = \frac{1}{100,000}.
\end{align*}
}

\problempart Ben argues that he made his mistake because the description of the
spider's situation is absurd: knowing the \emph{expected} number of flies
per hour is one thing, but knowing the \emph{exact} number is far-fetched.

Which of the bounds above will hold if all we know is that the
\emph{expected} number of small flies caught per hour is 10 and of large
flies is 30?

\solution{We know the expectation is 400 flies in 10 hours, so Markov's
bound will hold because it only depends on the expectation and the
nonnegativity of the number of flies.  In the case of the Chernoff bound,
we also need to know that the number of flies is a sum of mutually
independent Bernoulli variables; we are no longer given this, so Chernoff
does not apply.  To apply Chebyshev we need the variance, which we aren't
given.

Actually, to apply Chebyshev, all we need is a bound on the variance, and
there is one given that the expectation is 400 and $R$ is nonnegative.
The maximum possible variance for a nonnegative distribution with mean 400
occurs for the two-valued variable taking values 0 and 800 with equal
probability.  In this case the variance is $400^2$.  But plugging this
value into the Chebyshev formula gives a bound greater than 1, which is
useless.}

\iffalse

\problempart Ben argues that we should model the spider's situation by
assuming that the captures of large and small flies are mutually
independent Poisson processes with respective rates of 100 small flies
captured per 10 hours and 300 large ones per 10 hours.  Under these
assumptions, what are the Markov, Chebyshev, and Chernoff bounds on the
spider's probability of meeting her quota?

\solution{ Let $S$ be the random variable equal to the number of small
flies caught in 10 hours, and $L$ the number of large flies.  We are given
that $S$ has a Poisson distribution with rate $\lambda_S = 100$ and
likewise for $L$ with rate $\lambda_L = 300$.  The total number of flies
caught in 10 hours is $R \eqdef S+L$.  We know that the arrival rate and
mean of a Poisson distribution are the same, so $\mu_S = 100$ and $\mu_L =
300$.  So $\mu_R = 100 + 300 = 400$ by linearity of expectation.

The Markov bound depends only on the expected number of flies caught.
Since this is still 400, we have the same probability bound of 0.8 as in
the previous case.

But since $S$ and $L$ are independent, we know from Notes 14 that $R$ has
a Poisson distribution with rate $\lambda_R = \lambda_S + \lambda_L =
400$.  So not only is $\mu_R = 400$, but $\variance{R} = 400$, so the
one-sided Chebyshev bound becomes $400/(400+100^2) = 1/26$, a little
larger than the previous case.

The standard Chernoff Bound \emph{Theorem} does not apply because $R$ is
not a sum of Bernoulli variables.  However, we know from Notes 14 that the
standard Chernoff \emph{bound} applies to the Poisson distribution even
though it is not such a sum.  Since the value of the Chernoff bound
depends only on the expectation, the bound in this case remains the same
$1/100,000$ as before.}
\fi

\end{problemparts}
\end{problem}


%compare bounding formulas algebraically
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance20.tex}

\begin{problem} 
Let $R$ be the sum of a finite number of mutually independent Bernoulli
variables.  Let $\mu_R \eqdef \expect{R}$, and let $\sigma_R$ be the
deviation of $R$.

\begin{problemparts}

\problempart Write formulas in terms of $y$, $\mu_R$ and $\sigma_R$ for
the Markov, Chebyshev, and Chernoff bounds on $\pr{R \geq y}$, where $y
\geq \mu_R$.  \hint To apply Chebyshev bounds, assume
\begin{equation}\label{C/2}
\pr{R-\mu_r \geq x} \approx \frac{\pr{\abs{R - \mu_R} \geq x}}{2}
\end{equation}
for all $x \geq 0$.

\solution{
\begin{itemize}
\item The Markov bound is $\mu_R/y$, directly from~(\ref{M}).

\item The Chebyshev bound is
\begin{align}
\pr{R \geq y} & = \pr{R - \mu_R \geq y - \mu_R}\notag\\
   & \approx \frac{\pr{\abs{R - \mu_R} \geq y - \mu_R}}{2} & \text{(by~(\ref{C/2}))}\notag\\
   & \leq \frac{\sigma_R^2}{2(y - \mu_R)^2}.\label{Chebbnd}
\end{align}


\item The Chernoff bound is
\begin{align*}
\pr{R \geq y} & = \pr{R \geq \frac{y}{\mu_R}\mu_R}\\
              & \leq \text{exp}(- (\frac{y}{\mu_R}\ln \frac{y}{\mu_R} -
              \frac{y}{\mu_R} + 1) \mu_R)\\
              & = \text{exp}(- (y\ln \frac{y}{\mu_R} - y + \mu_R)).
\end{align*}

\end{itemize}
}

\problempart  Compare these bounds when $R$ is a single unbiased Bernoulli
variable and $y=1$.

\solution{In this case $\mu_R = 1/2$ and $\sigma_R^2 = 1/4$, so

\begin{itemize}

\item Markov gives $\mu_R/y = 1/2$ which is exactly right,

\item the bound from the Chebyshev result~(\ref{Chebbnd}) is
\[
\frac{\sigma_R^2}{2(y - \mu_R)^2} = \frac{1/4}{2(1-(1/2))^2} = \frac{1}{2},
\]
and so is also exactly right,

\item the bound from the Chernoff result is
\[
\text{exp}(- (\ln (1/(1/2)) - 1 + 1/2)) = e^{1/2 - \ln 2} = \sqrt{e}/2 > 0.83,
\]
and so is a large overestimate.

\end{itemize}
}

\iffalse
\problempart Discuss when the Chebyshev bound on $\pr{R > c\expect{R}}$ is
tighter than the Chernoff bound, where R is positive and $c>1$. (Providing
an example is sufficient.)

\solution{Consider the case where $c$ is small, that is, $c=1+\epsilon$
and $\epsilon < 1$.  Assume that $\variance{R}=\expect{R}=1$.  The
Chernoff bound is $e^{-(c\ln{c}-c+1)}$.  Numerical experiments show that
\[
\frac{1}{1+\epsilon^2} < e^{-(c\ln{c}-c+1)}.
\]
Therefore, the Chebyshev one-sided bound on $\pr{R>c\expect{R}}$ is
tighter than the Chernoff bound.}
\fi

\end{problemparts}
\end{problem}


%derive 1-sided, Chebyshev, better for pset
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance23.tex}


\appendix
\section{Appendix}
\setcounter{secnumdepth}{0}

%\subsection{Bounds on Deviation from the Mean}

\begin{theorem*}[Markov's Theorem]
 If R is a nonnegative random variable, then for all $x > 0$
\begin{equation}\label{M}
\pr{R \geq x} \leq \frac{\expect{R}}{x}.
\end{equation}
\end{theorem*}

\begin{theorem*}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\begin{equation}\label{Cheb}
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\end{equation}
\end{theorem*}

Random variables $R_1, R_2, \dots$ are \emph{mutually independent} iff
\[
\pr{\lgintersect_{i} [R_i = x_i]} = \prod_{i} \pr{R_i = x_i},
\]
for all $x_1, x_2, \dots \in \reals$.  They are \emph{$k$-wise
independent} iff $\set{R_i \suchthat i\in J}$ are mutually independent for
all subsets $J \subset \naturals$ with $\card{J} = k$.

\begin{theorem*}[Pairwise Independent Sampling]
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are pairwise
independent variables with the same mean, $\mu$, and deviation, $\sigma$.
Then
\begin{equation}\label{Sndev}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} \leq \frac{1}{n}
\left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{theorem*}

\begin{theorem*}[Chernoff Bound] 
Let $T_1, T_2, \dots, T_N$ be mutually independent Bernoulli variables,
and let $T \eqdef T_1 + T_2 + \cdots + T_N$.  Then for all $c \geq 1$,
\begin{equation}\label{Cher}
\pr{T \geq c \expect{T}} \leq \textup{exp}(- (c\ln c -c + 1) \expect{T}).
\end{equation}
\end{theorem*}

\end{document}

\iffalse
%binomial tail re markov, cheby, chern
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance7.tex}

\begin{problem}

Suppose you independently flip a fair coin 100 times.  What is an upper
bound on the probability that the number of heads is at least 70 \dots
\begin{problemparts}

\problempart
according to Markov's Inequality?

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

\problempart
according to Chebyshev's Inequality?  \hint Since the density is symmetric,
\[
\pr{R-\mu_r \geq x} = \frac{\pr{\abs{R - \mu_R} \geq x}}{2}
\]
for $x \geq 0$.

\solution{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$.  So plugging into~(\ref{Cheb}),
\[
\pr{\abs{R - 50} \geq 20} \leq \frac{25}{20^2} = \frac{1}{16},
\]
so
\[
\pr{R \geq 70}  = \pr{R-50 \geq 20} = \frac{\pr{\abs{R - 50} \geq 20}}{2}
= 1/32 \approx 0.031.
\]}

\problempart
according to Chernoff's Bound?

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



