\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,782,314.  The staff is willing to assume that the daily hack
attempts on each network really are binomially distributed, and they are
sure they average is at least 1,000,000.  Based on these assumptions, they
claim that the Chernoff bounds allows them to be overwhelmingly confident
that the actual average number of hack attempts per day on MIT networks is
at most 1\% more than the number they observed.

\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}]{
\begin{align*}
\pr{\text{Hacks} \geq 1.01 \expect{\text{Hacks}}}
& \leq \textup{exp}(- (c\ln c -c + 1) \expect{T}) & \text{(with $c = 1.01$)}\\
& \leq \textup{exp}(- (1/20,000) \cdot 1,000,000)\\
& = e^{-50} \approx 0.
\end{align*}
So the actual average is at most $1.01 \cdot 3,782,314$ with essentially
100\% confidence.
}

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

\solution{The distribution of hacks at each network is binomial, which means it is a
sum of Bernoulli variables.  The distribution of hacks for all of MIT is a
sum of those at each network, and so is also a sum of Bernoulli variables
(with differing $p$'s depending on the network).  So the Chernoff bound
applies.
}


\eparts

\end{problem}
