Page 482 - Discrete Mathematics and Its Applications

7.2 Probability Theory 461

Solution: The random variable X takes on the following values:

X((1, 1)) = 2,
X((1, 2)) = X((2, 1)) = 3,
X((1, 3)) = X((2, 2)) = X((3, 1)) = 4,
X((1, 4)) = X((2, 3)) = X((3, 2)) = X((4, 1)) = 5,
X((1, 5)) = X((2, 4)) = X((3, 3)) = X((4, 2)) = X((5, 1)) = 6,
X((1, 6)) = X((2, 5)) = X((3, 4)) = X((4, 3)) = X((5, 2)) = X((6, 1)) = 7,
X((2, 6)) = X((3, 5)) = X((4, 4)) = X((5, 3)) = X((6, 2)) = 8,
X((3, 6)) = X((4, 5)) = X((5, 4)) = X((6, 3)) = 9,
X((4, 6)) = X((5, 5)) = X((6, 4)) = 10,
X((5, 6)) = X((6, 5)) = 11,
X((6, 6)) = 12. ▲

We will continue our study of random variables in Section 7.4, where we will show how
they can be used in a variety of applications.

The Birthday Problem

A famous puzzle asks for the smallest number of people needed in a room so that it is more likely
than not that at least two of them have the same day of the year as their birthday. Most people
find the answer, which we determine in Example 13, to be surprisingly small. After we solve
this famous problem, we will show how similar reasoning can be adapted to solve a question
about hashing functions.

EXAMPLE 13 The Birthday Problem What is the minimum number of people who need to be in a room so
that the probability that at least two of them have the same birthday is greater than 1/2?

Solution: First, we state some assumptions. We assume that the birthdays of the people in the
room are independent. Furthermore, we assume that each birthday is equally likely and that
there are 366 days in the year. (In reality, more people are born on some days of the year than
others, such as days nine months after some holidays including New Year’s Eve, and only leap
years have 366 days.)
To find the probability that at least two of n people in a room have the same birthday,
we first calculate the probability p n that these people all have different birthdays. Then, the
probability that at least two people have the same birthday is 1– p n . To compute p n , we consider
the birthdays of the n people in some fixed order. Imagine them entering the room one at a time;
we will compute the probability that each successive person entering the room has a birthday
different from those of the people already in the room.
The birthday of the first person certainly does not match the birthday of someone already in
the room. The probability that the birthday of the second person is different from that of the first
person is 365/366 because the second person has a different birthday when he or she was born
on one of the 365 days of the year other than the day the first person was born. (The assumption
that it is equally likely for someone to be born on any of the 366 days of the year enters into this
and subsequent steps.)
The probability that the third person has a birthday different from both the birthdays of
the first and second people given that these two people have different birthdays is 364/366. In
general, the probability that the jth person, with 2 ≤ j ≤ 366, has a birthday different from the