Message Authentication - Codes: The Guide to Secrecy from Ancient to Modern Times - page 252

Let P j ( n, m ) be the probability that one ball is drawn at least j times. Then,
we are seeking

P 1 ( n, m ) .
To find P 1 ( n, m ), note that the probability that the second drawn ball is different
from the first is 1

P 2 ( n, m )=1 −

−

1 /n , the probability that the third ball is different from the

−

first two is 1 2 /n , and so the probability that the first three balls are all

different is (1 2 /n ). Continuing in this fashion, we see that the

probability that all of the m balls drawn are different is,

− 1 /n )(1 −

1 =

m − 1 m − 1

j
n

1
n m − 1

P 1 ( n, m )= − ( n − j )=

j =1 j =1

( n − 1)( n − 2) ··· ( n − m +1)

.

n m − 1

Thus,

( n − 1)( n − 2) ··· ( n − m +1)

P 2 ( n, m )=1 − .

n m − 1

In particular, suppose we want to prove that in any room of 23 people, the
probability that at least two of them have the same birthday is greater than
50%. From the above this is a fact since

P 2 (365 , 23) ≈ 0 . 5072972343 .

This phenomenon is called the birthday paradox .
The birthday paradox is a special case of the occupancy problem , which is
given as follows. Suppose that a container has n balls numbered 1 through
n inclusive. Again assume that m balls are drawn one at a time, listed, and
replaced each time. Then the probability that exactly of the m balls are
different for 1 ≤ ≤ m is given by

1) − j
j

j m P 1 ( n, m ) ,

1
!

( −

j =0

where j is the binomial coe:cient (see Definition A.14 on page 473 and the
discussion following it, as well as Appendix E on probability theory.).
Now we return to the birthday attack that began this discussion. We initially
asked how we can find a collision. From the above, the probability that there
do not exist any collisions is

m − 1

(1 − j/n ) ,

j =1

so

e − x 1 − x ≈