Data Mining - Mining of Massive Datasets - page 6

1.2.3 An Example of Bonferroni's Principle

Suppose there are believed to be some “evil-doers” out there, and we want to detect them.
Suppose further that we have reason to believe that periodically, evil-doers gather at a hotel
to plot their evil. Let us make the following assumptions about the size of the problem:

(1) There are one billion people who might be evil-doers.
(2) Everyone goes to a hotel one day in 100.
(3) A hotel holds 100 people. Hence, there are 100,000 hotels - enough to hold the 1% of
a billion people who visit a hotel on any given day.
(4) We shall examine hotel records for 1000 days.

To find evil-doers in this data, we shall look for people who, on two different days, were
both at the same hotel. Suppose, however, that there really are no evil-doers. That is, every-
one behaves at random, deciding with probability 0.01 to visit a hotel on any given day,
and if so, choosing one of the 10 5 hotels at random. Would we find any pairs of people who
appear to be evil-doers?
We can do a simple approximate calculation as follows. The probability of any two
people both deciding to visit a hotel on any given day is .0001. The chance that they will
visit the same hotel is this probability divided by 10 5 , the number of hotels. Thus, the
chance that they will visit the same hotel on one given day is 10 − 9 . The chance that they
will visit the same hotel on two different given days is the square of this number, 10 − 18 .
Note that the hotels can be different on the two days.
Now, we must consider how many events will indicate evil-doing. An “event” in this
sense is a pair of people and a pair of days, such that the two people were at the same hotel
on each of the two days. To simplify the arithmetic, note that for large is about n 2 /2. We
shall use this approximation in what follows. Thus, the number of pairs of people is
The number of pairs of days is The expected number of events that look like evil-
doing is the product of the number of pairs of people, the number of pairs of days, and the
probability that any one pair of people and pair of days is an instance of the behavior we
are looking for. That number is

5 × 10 17 × 5 × 10 5 × 10 − 18 = 250 , 000

That is, there will be a quarter of a million pairs of people who look like evil-doers, even
though they are not.
Now, suppose there really are 10 pairs of evil-doers out there. The police will need to
investigate a quarter of a million other pairs in order to find the real evil-doers. In addition