% 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 one-sided Chebyshev bound is
\[
\pr{R - 400 \geq 100} \leq \frac{1900/12}{1900/12 + 100^2} = 1900/121,900
\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 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.}

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

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

\end{problemparts}
\end{problem}

