1.2. STATISTICAL LIMITS ON DATA MINING
7
than evidence of what you are looking for. This observation is the informal
statement of Bonferroni’s principle.
In a situation like searching for terrorists, where we expect that there are
few terrorists operating at any one time, Bonferroni’s principle says that we
may only detect terrorists by looking for events that are so rare that they are
unlikely to occur in random data. We give an extended example below.
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 periodi-
cally, 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 ﬁnd evil-doers in this data, we shall look for people who, on two diﬀerent
days, were both at the same hotel. Suppose, however, that there really are no
evil-doers. That is, everyone behaves at random, deciding with probability 0.01
to visit a hotel on any given day, and if so, choosing one of the 105 hotels at
random. Would we ﬁnd 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 105,
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
diﬀerent given days is the square of this number, 10−18. Note that the hotels
can be diﬀerent 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 n,
n
2

is about n2/2. We shall use this approximation in what
follows. Thus, the number of pairs of people is
109
2

= 5 × 1017. The number
of pairs of days is
1000
2

= 5 × 105. 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 × 1017 × 5 × 105 × 10−18 = 250, 000
