\begin{problem}[15]
The administrators of the major computer networks around MIT have noticed
that the daily number of attempts to hack into each network has a pretty
stable distribution.  In fact, the distribution in each case appears to be
binomial, though with different parameters $n$ and $p$ for different
networks.

The main Athena computer staff would like an accurate estimate of the
average number of hacks per day for all of MIT.  They were about to ask
for the network administrators for complete statistics for the past year,
when they realized they could get a very accurate estimate by having each
of the network administrators report the actual number of hacks on a
randomly selected day in the last couple of months.

When they got that day's data, they discovered that the total number of
hacks was 3,762,314.  The staff is willing to assume that the daily hack
attempts on each network really are binomially distributed, and they are
sure the average is at least 1,000,000.  In addition, it appears that hack
attempts on different networks occur independently of each other.  Based
on these assumptions, they claim that the Chernoff Bound allows them to
be overwhelmingly confident that the actual average number of hack
attempts per day on MIT networks totals to at least 3,700,000.

\bparts

\ppart[8] Using the Chernoff Bound, explain why the Athena staff's
confidence is justified.  \hint $c \ln c - c +1 > 1/20,000$ for $c =1.01$.

\solution[\vspace*{3in}]{

Applying the Chernoff bound to the random variable, $H$, equal to the
total number of hack attempts per day, we have
\begin{equation*}%\label{CH}
\pr{H \geq c \expect{H}}
   \leq \textup{exp}(- (c\ln c -c + 1) \expect{H}).
\end{equation*}
Letting $c= 1.01$, we have
\begin{align*}
\pr{H \geq 1.01 \expect{H}}
  & \leq \textup{exp}(- \frac{1}{20,000} \expect{H})\\
  & \leq \textup{exp}(- \frac{1,000,000}{20,000})\\
  & = e^{-50} \approx 0.
\end{align*}
So the probability that the actual average, $\expect{H}$, is lower than
$H/1.01$ is essentially negligible.  Hence, given our sample value
3,762,314 for $H$, we have
\[
\expect{H} > 3,762,314/1.01 > 3,725,000 > 3,700,000
\]
with essentially 100\% confidence.
}

\ppart[7] Explain why the Chernoff bound is applicable in this situation.

\solution{The Chernoff bound applies to a sum of independent Bernoulli
variables.

But the distribution of hack attempts at each network is binomial, which
means it can be modelled as a sum of some number of independent Bernoulli
variables with some bias.  The number of hack attempts for all of MIT is
the independent sum of those at each network, and so can be modelled as an
independent sum of independent sums of Bernoulli variables (with differing
$p$'s depending on the network), which is simply a large sum of Bernoulli
variables.  So the Chernoff bound applies.}

\eparts

\end{problem}
