
\subsection{Auto Risk}

How dangerous are cars?  Suppose that person $Z$ would ordinarily live
50 years, but let $E_k$ be the event that $Z$ dies in a car wreck in
year $2006 + k$.  Thus, the probability that $Z$'s demise is
car-related is:
%
\[
\pr{E_0 \cup \ldots \cup E_{49}}
\]
%
The US population will be about 295 million at the start of 2006 and
is growing at about 1\% per year.  Auto fatalities have stayed at
around 42,000 per year due to safety improvements.  Assuming that
person $Z$ is as likely to be a victim as anyone else, we have:
%
\[
\pr{E_k} = \frac{42,000}{295,000,000 (1.01)^k}
\]
%
The probability that person $Z$ dies in a car crash is at most:
%
\begin{align*}
\pr{E_1 \cup \ldots \cup E_{50}}
    & \leq \pr{E_1} + \ldots + \pr{E_{50}} \\
    & = \sum_{k=0}^{49} \frac{42,000}{295,000,000 (1.01)^k} \\
    & = \frac{42,000}{295,000,000} \sum_{k=0}^{49} \left(\frac{1}{1.01}\right)^k \\
    & = \frac{42,000}{295,000,000} \cdot \frac{1 - (1 / 1.01)^{50}}{1 - 1 / 1.01} \\
    & \approx 0.56\%
\end{align*}
%
We're using the Union Bound on the first line, and the next-to-last
line follows from the formula for a geometric sum.  In this case, the
events $E_i$ are disjoint; if person $Z$ dies in year $i$ then he
can't be killed again in a later year.  Thus, we're in the situation
where the Union Bound is tight.  So given our assumptions, those are
person $Z$'s real chances.

\subsection{Independent Events}

Suppose that our spacecraft design is a bit more edgey.  Now the
critical components have the following characteristics:
%
\begin{itemize}
\item 10 components each which fail with probability $1/5$.
\item 100 components each which fail with probability $1/40$.
\item 1000 components each which fail with probability $1/200$.
\end{itemize}
%
In this design, components are carefully isolated so that they fail
mutually independently.  Suppose we just ``light the candle'' and hope
for the best.  What is the probability that some component fails?

We could work out the exact answer, but let's use a handy
approximation instead.  You can regard this as a probabilistic version
of Murphy's Law: \textit{if you expect several things to go wrong,
then something almost certainly will.}

\begin{theorem}[``Murphy's Law'']
If events $E_1, \ldots E_n$ are mutually independent, then:
%
\[
\pr{E_1 \cup \ldots \cup E_n} \geq 1 - e^{-\ex{X}}
\]
\end{theorem}

\begin{proof}
\begin{align*}
\pr{E_1 \cup \ldots \cup E_n}
    & = 1 - \pr{\overline{E_1 \cup \ldots \cup E_n}} \\
    & = 1 - \pr{\overline{E_1} \cap \ldots \cap \overline{E_n}} \\
    & = 1 - \pr{\overline{E_1}} \cdots \pr{\overline{E_n}} \\
    & = 1 - (1 - \pr{E_1}) \cdots (1 - \pr{E_n}) \\
    & \leq 1 - e^{-\pr{E_1}} \cdots e^{-\pr{E_n}} \\
    & = 1 - e^{-(\pr{E_1} + \ldots + \pr{E_n})} \\
    & = 1 - e^{-\ex{X}}
\end{align*}
%
The inequality follows from $1 - x \leq e^{-x}$.
\end{proof}

For the spaceship problem, let $E_k$ be the event that the $k$-th
component fails.  Then the expected number component failures is:
%
\[
\ex{X} = 10 \cdot \frac{1}{5} + 100 \cdot \frac{1}{40}
          + 1000 \cdot \frac{1}{200} = 9.5
\]
%
So the probability of a successful flight is at most $e^{-9.5} \approx
0.000075$.  Not a good gamble!


Let's put this question in a broader context.  Let $X$ be the number
of parts that fail.  Then the probability density function of $X$
doesn't look even remotely like this:
%
\begin{center}
\includegraphics{pdf-x}
\end{center}
%
But this inaccurate picture helps put the question in perspective.
The spaceship flies successfully only if no critical parts fail; that
is, if $X = 0$.  In terms of the picture, the flight is successful
only at the absolute leftmost tail of the distribution.  (The picture
makes this look unlikely, but actually it isn't.  If the picture were
drawn correctly, the big lump in the middle would be pixel-wide
pancake smashed against the vertical axis.)  So our larger objective
is to answer the question, ``How likely are we to be somewhere other
than the absolute tip of the distribution's tail?''

Now let's return to the spaceship.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

One can only hope to dodge Murphy's Law: ``If anything can go wrong,
it will go wrong.''  We're going to prove a probabilistic version of
Murphy's Law that can help decide whether or not that hope is in vain.

Suppose that $E_1, \ldots, E_n$ are things that can go wrong and
suppose that these events are mutually independent.  We can use the
Union Bound to \textit{upper bound} the probability that something
goes wrong.  We can also compute the exact probability as follows:
%
\begin{align*}
\pr{E_1 \cup \ldots \cup E_n}
    & = 1 - \pr{\overline{E_1 \cup \ldots \cup E_n}} \\
    & = 1 - \pr{\overline{E_1} \cap \ldots \cap \overline{E_n}} \\
    & = 1 - \pr{\overline{E_1}} \cdots \pr{\overline{E_n}} \\
    & = 1 - (1 - \pr{E_1}) \cdots (1 - \pr{E_n})
\end{align*}
%
There is also a nice lower bound from the previous problem set, which
says that \textit{if you expect things to go wrong, then something
almost surely will.}

Suppose that we needed to store credit histories for a great many
people.  We could create $n = 26^2$ bins labeled $AA, AB, AC, \ldots,
ZZ$.  Then we would store a person's record based on the first two
letters of their name.  For example, the record for ``Lee, Edmond''
would be stored in the bin labeled $LE$.  Then, when we needed to look
up Edmond's credit history, we would only need to search through the
records in bin $LE$, rather than all of them.

In computer science, this trick for rapidly storing and retrieving
records is called \textit{hashing}.  Each record consists of a
\textit{key} and \textit{value}.  A \textit{hash function} maps each
record's key to a bin.  In our example, the keys were names, the
values were credit histories, and the hash function mapped each name
to its first two letters.

The great fear in hashing is that one bin somehow ends up with too
many records.  If that happens, then retrieving any record in that bin
is time-consuming, since there are so many to search through.  This
sort of imbalance is inevitable if the hash function is chosen poorly.
For example, the hash function that maps each name to its first two
letters is actually a bad choice, because some two letter prefixes are
quite common (\underline{Le}e, \underline{Le}hman,
\underline{Le}ighton) and others extremely uncommon (qz, vj, rr).

An ideal hash function would assign records to bins uniformly and
independently at random.  We can not achieve this goal in a rigorous
sense--- the only possible randomization is in the choice of records,
about which we know nothing--- but this is still a decent practical
model of a good hash function.

So let's assume that records \textit{are} hashed to bins uniformly and
independently at random.  In particular, suppose that $n$ records are
hashed to $n$ bins.  How will the records be distributed?  The answer
to this question will employ all the tools we've introduced so far.

In the best case, every bin would end up with exactly 1 record.  But
we can rule that out immediately: the birthday principle says that
some bin will probably contain two records after we've inserted only
$\Theta(\sqrt{n})$ records.  On the other hand, if something weird
happened, we might end up with $n/2$ records in a single bin.  Then
half the records would be almost inaccessible.