Mathematics for Computer Science

18.5. Estimation by Random Sampling 631

Unlike the situation with voter preferences, having matching birthdays for dif-
ferent pairs of students are not mutually independent events, but the matchings are
pairwise independent—as explained in Section 16.7 (and proved in Problem 17.2).
This will allow us to apply the same reasoning to Birthday Matching as we did for
voter preference. Namely, letB 1 ;B 2 ;:::;Bnbe the birthdays ofnindependently
chosen people, and letEi;jbe the indicator variable for the event that theith and
jth people chosen have the same birthdays, that is, the eventŒBiDBjç. So our
probability model, theBi’s are mutually independent variables, theEi;j’s are pair-
wise independent. Also, the expectations ofEi;jfori¤jequals the probability
thatBiDBj, namely,1=d.
Now,D, the number of matching pairs of birthdays among thenchoices, is
simply the sum of theEi;j’s:

DWWD

X

1 i<jn

Ei;j: (18.20)

So by linearity of expectation

ExŒDçDEx

2

4

X

1 i<jn

Ei;j

3

(^5) D

X

1 i<jn

ExŒEi;jçD

n

2

!

1

d

:

Similarly,

VarŒDçDVar

2

4

X

1 i<jn

Ei;j

3

5

D

X

1 i<jn

VarŒEi;jç (by Theorem 18.4.8)

D

n

2

!

1

d



1

1

d



: (by Lemma 18.4.2)

In particular, for a class ofnD 95 students withdD 365 possible birthdays, we
have ExŒDç < 12:23and VarŒDç > 12:22.11=365/ > 12:19. So by Chebyshev’s
Theorem

PrŒjD12:23jxç <

12:19

x^2

:

LettingxD 7 , we conclude that there is a better than 75% chance that in a class of
95 students, the number of pairs of students with the same birthday will be between
6 and 20.