\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \tutsol{13}{December 6, 2001}{\stamp}
\else
  \tutprobn{13}{December 6, 2001}{\stamp}
\fi

%% TUTORIAL 13: Chernoff bound, Possion distribution, Central Limit Theorem

\section{Problems}

\begin{problems}


\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.

\bparts

\ppart 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.

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

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

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

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

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

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

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

\ppart 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$.)

\solnospace{
\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*}
}

\ppart 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?

\solnospace{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 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$.  Plugging this value
into the one-sided Chebyshev bound gives
\[
\pr{R - 400 \geq 100} \leq \frac{400^2}{400^2 + 100^2} =
      \frac{160,000}{170,000} = \frac{16}{17}
\]
which is worse than the Markov bound.

This bound could be improved a bit further using the additional constraint
that $R$ must be a sum of two independent nonnegative integer-valued
variables with expectations 100 and 300, respectively.  In this case the
maximum variance is $100^2 + 300^2 = 100,000$, yielding a one-sided
Chebyshev bound of $100,000/(100,000 + 10,000) = 10/11$, still not as good
as the Markov bound in this case.}

\ppart Ben argues that we should model the spider's situation by assuming
that the captures of large and small flies are 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?

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

\eparts


\problem Let $R$ be the sum of a finite number of Bernoulli variables.

\bparts

\ppart For $y \geq \mu_R$, write formulas in terms of $y$, $\mu_R$ and
$\sigma_R$ for the Markov, one-sided Chebyshev, and Chernoff bounds on
$\pr{R \geq y}$.

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

\item the bound from the one-sided Chebyshev result is
\begin{align*}
\pr{R \geq y} & = \pr{R - \mu_R \geq y - \mu_R}\\
  & \leq \frac{\sigma_R^2}{(y - \mu_R)^2 + \sigma_R^2}.
\end{align*}

\item the bound from the Chernoff result 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}
}


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

\solnospace{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 one-sided Chebyshev result is
\[
\frac{\sigma_R^2}{(y - \mu_R)^2 + \sigma_R^2} = \frac{1/4}{(1-(1/2))^2
+ 1/4} = \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 over-estimate.

\end{itemize}}

\iffalse

Consider the case where $c$ is small, say $c=1+\epsilon$ and
$\epsilon <1$. The Markov bound is $\frac{1}{1+\epsilon}$.  If we further
assume that $\variance{R}=\expect{R}$, then the Chebyshev one-sided
bound becomes
\[
\pr{R-\expect{R} \geq \epsilon \expect{R}} \leq
\frac{\variance{R}}{\variance{R}+\epsilon^2 \expect{R}} =
\frac{1}{1+\epsilon^2}.
\]
Since $\frac{1}{1+\epsilon}< \frac{1}{1+\epsilon^2}$, the Markov bound is
tighter than the Chebyshev one-sided bound.}

\ppart Discuss when the Chebyshev one-sided 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.)

\solnospace{ Still 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

\eparts


\problem \textbf{Central Limit Theorem.} Let $B_n$ be a random variable
with binomial distribution $f_{n,p}$.

\bparts

\ppart Write a formula defining the random variable, $B^*_n$, which is the
``normalized'' version of $B_n$ (normalized to have mean 0 and standard
deviation 1).

\solnospace{
The normalized version of any variable, $R$, is $(R - \mu_R)/\sigma_R$.
But $\expect{B_n} = np$ and $\variance{B_n} = np(1-p)$, so
\[
B^*_n = \frac{B_n-np}{\sqrt{np(1-p)}}.
\]
}

\ppart Explain why
\[
\lim_{n \rightarrow \infty}\pr{B^*_n < \beta} = N(\beta),
\]
where $N(\beta)$ is the normal distribution from the Central Limit Theorem
(see Appendix).

\solnospace{

Note that $B_n$ has the same distribution as the sum, $S_n$, of $n$
mutually independent Bernoulli random variables, $G_i$, with mean $p$ and
variance $p(1-p)$.  So the normalized version, $B^*_n$ of $B_n$ has the same
distribution as the normalized version, $T_n$, of $S_n$.  The Central
Limit Theorem says that
\begin{equation}\label{T}
\lim_{n \rightarrow \infty}\pr{T_n < \beta} = N(\beta),
\end{equation}
and since the distributions of $T_n$ and $B^*_n$ are the same,
equation~(\ref{T}) holds for $B^*_n$ as well.
}

\iffalse
\ppart Suppose you flip a fair coin 100 times.  The coin flips are all
mutually independent.  Use the standard normal distribution to approximate
the probability that the number of heads is between $30$ and $70$.  Can you
give a lower bound on this probability using the generalized Chernoff
bound?  (You can leave $N(\beta)$ and $e$ in your answer.)

\solnospace{ We have an unbiased binomial distribution for this case.  The
expected number of heads is $50$ and the variance of the number of heads
is $100/4 = 25$.  Let $S_{100}$ be the number of heads.  We have
\begin{align*}
\pr{ 30 < S_{100} < 70} & = \pr{-4 < T_{100} < 4}\\
& \approx N(4)-N(-4)\\
& = 2N(4)-1=0.9999.
\end{align*}
Note that to make this approximation practical $n$ needs to be
``sufficiently large''.  A rule often stated is that $n$ is ``sufficiently
large'' if $np\leq 5$ and $n(1-p)\leq 5$.

Since the distribution is symmetric, $\pr{30 < S_{100} <
70}=1-2\pr{S_{100} \geq 70}$. Applying the generalized Chernoff bound
derived in the lecture note, we have
$$\pr{S_{100} \geq 70} \leq e^{-4^2/2}$$
where $4=\frac{20}{5}$. Therefore, 
$$\pr{30 < S_{100} < 70}=1-2\pr{S_{100} \geq 70} \geq 1-2e^{-4^2/2}=0.9993$$ 
which gives us a good lower bound on $\pr{ S_{100} \geq 70}$.
}
\fi

\eparts

\problem \textbf{Generalized Law of Large Numbers.}

The Weak Law of Large Numbers in Notes 13 was given for a sequence $G_1,
G_2, \dots$ of mutually independent random variables with the same mean
and variance.  We can generalize the Law to sequences of mutually
independent random variables, possibly with different means and variances,
as long as their variances are bounded by some constant.  Namely,

\begin{theorem*}
Let $X_1, X_2, \dots$ be a sequence of mutually independent random
variables such that $\variance{X_i} \leq b$ for some $b\geq 0$ and all
$i\geq 1$.  Let
\begin{align*}
\bar{X}_n & \eqdef (X_1 + X_2 + \cdots + X_n)/n, &
\mu_n & \eqdef \expect{\bar{X}_n}.
\end{align*}
Then for every $\epsilon > 0$,
\[
\pr{\abs{\bar{X}_n - \mu_n} \geq \epsilon} \leq \frac{b}{n\epsilon^2}.
\]
\end{theorem*}

\bparts
\ppart Prove this Theorem.

\hint Adapt the proof (attached) of the Weak Law of Large Numbers from
Notes 13.

\solnospace{Essentially identical to the proof attached, except that
$\variance{G_i}$ gets replaced by $b$, and the equality becomes $\leq$
where the $b$ is first used.}

\ppart Conclude
\begin{corollary*}[Weak Law of Large Numbers]

For every $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty}
        \pr{\abs{\bar{X}_n - \mu_n}  \geq \epsilon} = 0.
\]
\end{corollary*}

\solnospace{For fixed $\epsilon$, the bound $b/(n\epsilon^2)
\rightarrow 0$ as $n \rightarrow \infty$.}

\eparts


\problem \textbf{One-sided Chebyshev Bound.}  Prove the one-sided
Chebyshev bound.  \hint $R-\mu_R \geq x$ implies $(R-\mu_R + a)^2 \geq (x
+ a)^2$ for all nonnegative $a \in \reals$.  By Markov,
\[
\pr{(R-\mu_R + a)^2 \geq (x + a)^2} \leq \frac{\expect{(R-\mu_R + a)^2}}{(x+a)^2}.
\]
Choose $a$ to minimize this last bound.

\solnospace{
\begin{proof}

\begin{align}
\pr{R-\mu_R \geq x} & \leq \pr{(R-\mu_R + a)^2 \geq (x + a)^2}
                          & \text{(from the hint)} \notag\\
   & \leq \frac{\expect{(R-\mu_R + a)^2}}{(x+a)^2}
                          & \text{(Markov  bound)} \notag\\
   & =  \frac{\expect{(R-\mu_R)^2} +2a(\expect{R}-\mu_R) + a^2}{(x+a)^2}
                & \text{(linearity of expectation)} \notag\\
   & =  \frac{\expect{(R-\mu_R)^2} + a^2}{(x+a)^2} & (\expect{R} = \mu_R) \notag\\
   & =  \frac{\variance{R} + a^2}{(x+a)^2} & \text{(def of variance)\label{Va}}.
\end{align}

Setting the derivative of~(\ref{Va}) with respect to $a$ to zero, we find
that $a = \variance{R}/x$ minimizes~(\ref{Va}).  Plugging in this value for
$a$, we have
\begin{align*}
\pr{R-\mu_R \geq x} & \leq \frac{\variance{R} +
\left(\variance{R}/x\right)^2}{\left(x+ \variance{R}/x\right)^2}
    & \text{($a = \variance{R}/x$ in~(\ref{Va}))}\\
    & = \frac{\variance{R}x^2 + \varsq{R}}{\left(x^2+
         \variance{R}\right)^2}
       & \text{(multiply by $x^2/x^2$)}\\
    & = \frac{\variance{R}(x^2 + \variance{R})}{\left(x^2+
\variance{R}\right)^2}\\
    & = \frac{\variance{R}}{x^2+ \variance{R}}.
\end{align*}

\end{proof}
}

\end{problems}

\section{Appendix}

\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 (two-sided)]
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*}


\begin{theorem*}[Chebyshev (one-sided)]
Let $R$ be a random variable, and let $x$ be a positive real number.
\begin{equation}\label{1Cher}
\pr{R - \expect{R} \geq x} \leq \frac{\variance{R}}{\variance{R} + x^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*}

\subsection{Weak Law of Large Numbers}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.

\begin{theorem*}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
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{proof}
By linearity of expectation,
\[
\expect{\frac{S_n}{n}} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{n\mu}{n} = \mu.
\]

Since the $G_i$'s are independent, their variances will also add, so
\begin{eqnarray*}
\variance{\frac{S_n}{n}} & = & \left(\frac{1}{n}\right)^2 \variance{S_n}\\
& = & \left(\frac{1}{n}\right)^2 \sum_{i=1}^n \variance{G_i}\\
& = & \left(\frac{1}{n}\right)^2 n\sigma^2\\
& = & \frac{\sigma^2}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that for any random variable, $R$,
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
So, letting $R$ be $S_n/n$ yields~(\ref{Sndev}), as required.

\end{proof}


\subsection{Central Limit Theorem}

\begin{theorem*}[Central Limit Theorem]
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_i, \dots$ are
mutually independent variables with same mean, $\mu$, and deviation,
$\sigma$, and let
\[
T_n \eqdef \frac{\sqrt{n}}{\sigma} \cdot(\frac{S_n}{n}-\mu).
\]
Then
\[
\lim_{n\rightarrow\infty} \pr{T_n < \beta}= N(\beta).
\]
\end{theorem*}

\end{document}


