16.4. The Birthday Principle 685
16.4.1 Exact Formula for Match Probability
There arednsequences ofnbirthdays, and under our assumptions, these are
equally likely. There ared.d 1/.d 2/.d .n 1//lengthnsequences of
distinct birthdays. That means the probability that everyone has a different birthday
is:^3
d.d 1/.d 2/.d .n 1//
dn
D
d
d
d 1
d
d 2
d
d .n 1/
d
(16.4)
D
1
0
d
1
1
d
1
2
d
1
n 1
d
< e^0 e 1=de 2=de .n 1/=d (since 1 Cx < ex)
De
Pn 1
iD 1 i=d
De .n.n 1/=2d/: (16.5)
FornD 95 andd D 365 , the value of (16.5) is less than1=200;000, which
means the probability of having some pair of matching birthdays actually is more
than 1 1=200;000 > 0:99999. So it would be pretty astonishing if there were no
pair of students in the class with matching birthdays.
Fordn^2 =2, the probability of no match turns out to be asymptotically equal
to the upper bound (16.5). FordDn^2 =2in particular, the probability of no match
is asymptotically equal to1=e. This leads to a rule of thumb which is useful in
many contexts in computer science:
The Birthday Principle
If there areddays in a year and
p
2dpeople in a room, then the probability that
two share a birthday is about 1 1=e0:632.
For example, the Birthday Principle says that if you have
p
2 365 27 people
in a room, then the probability that two share a birthday is about0:632. The actual
probability is about0:626, so the approximation is quite good.
Among other applications, it implies that to use a hash function that mapsn
items into a hash table of sized, you can expect many collisions ifn^2 is more than
(^3) The fact that 1 x < e xfor allx > 0follows by truncating the Taylor seriese xD 1 xC
x^2 =2Š x^3 =3ŠC. The approximatione x 1 xis pretty accurate whenxis small.