Birthday Problem

Subject: Mathematics
Name：Dmitry Kozyrev
Passport Number：N07797989
Date: 16.06.2015
Mark:

Contents
Abstract _______________________________________________ 3
Keywords______________________________________________ 3
1. Basis of Probability ___________________________________ 4
1.1 Conditional Probability _____________________________ 4
1.2 Independence _____________________________________ 4
2. Birthday Problem______________________________________5
2.1 What is Birthday Problem? _________________________ 5
2.2 Understanding the probability_________________________ 6
2.3 Calculating the probability of birthday problem___________ 7
2.4 Abstract proof______________________________________10
3 Examples______________________________________________11
4 References_____________________________________________13

2

Abstract
The subject of probability can be traced back to the 17th century when it arose out of the study of gambling games. As we see, the range of applications extends beyond games into business decisions, insurance, law, medical tests, and the social sciences. The stock market, “the largest casino in the world,” cannot do without it. The telephone network, call centers, and airline companies with their randomly fluctuating loads could not have been economically designed without probability theory. To quote Pierre-Simon, marquis de Laplace from several hundred years ago:
«It is remarkable that this science, which originated in the consideration of games of chance, should become the most important object of human knowledge...The most important questions of life are, for the most part, really only problems of probability.»

Keywords: experiment; outcomes; empty set; union; intersection; probability; birthday problem.

3

1. Basis of probability
1.1 Conditional Probability
Conditional Probability is the probability of some event A, given the occurrence of some other event B. Conditional probability is written P(A|B) , and is read "the probability of A, given B". It is defined by ( | ) =

( ∩ )
()

If P(B)=0 then P(A|B) is formally undefined by this expression. However, it is possible to define a conditional probability for some zero-probability events using a σ-algebra of such events (such as those arising from a continuous random variable). For example, in a bag of 2 red balls and 2 blue balls (4 balls in total), the probability of taking a red ball is 1/2 ; however, when taking a second ball, the probability of it being either a red ball or a blue ball depends on the ball previously taken, such as, if a red ball was taken, the probability of picking a red ball again would be 1/3 since only 1 red and 2 blue balls would have been remaining.

1.2 Independence
In probability theory, two events are independent, statistically independent, or stochastically independent if the occurrence of one does not affect the probability of the other. Similarly, two random variables are independent if the realization of one does not affect the probability distribution of the other.
The concept of independence extends to dealing with collections of more than two events or random variables, in which case the events are pairwise independent if each pair are independent of each other, and the events are mutually independent if each event is independent of each other combination of events.
If the two events are considered independent, each can occur individually and the outcome of one event does not affect the outcome of the other event in any way. Let's say that A and B are independent events. We'll examine what this means for this type of probability. Independent events technically do not have a conditional probability, because in this case, A is not dependent on B and vice versa. Therefore, the probability of A given that B has already occurred is equal to the probability of A (and the probability of B given A is equal to the probability of
B). This can be expressed as:
P(A|B) = P(A)
P(B|A) = P(B)
4

2. Birthday Problem
2.1 What is Birthday Problem?
In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are 366 possible birthdays, including
February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people. These conclusions include the assumption that each day of the year (except February 29) is equally probable for a birthday. The history of the problem is obscure. W. W. Rouse Ball indicated (without citation) that it was first discussed by Harold Davenport. However, Richard von Mises proposed an earlier version of what we consider today to be the birthday problem.
The mathematics behind this problem led to a well-known cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function.

5

2.2 Understanding the probability
The birthday problem is to find the probability that, in a group of N people, there is at least one pair of people who have the same birthday. See "Same birthday as you" further for an analysis of the case of finding the probability of a given, fixed person having the same birthday as any of the remaining people. In the example given earlier, a list of 23 people, comparing the birthday of the first person on the list to the others allows 22 chances for a matching birthday, the second person on the list to the others allows 21 chances for a matching birthday (in fact the 'second' person also has total 22 chances of matching birthday with the others but his/her chance of matching birthday with the 'first' person, one chance, has already been counted with the first person's 22 chances and shall not be duplicated), third person has 20 chances, and so on. Hence total chances are: 22+21+20+…+1=253, so comparing every person to all of the others allows
253 distinct chances (combinations): in a group of 23 people there are distinct possible combinations of pairing.
23 ∗ 22
23
( )=
= 253
2
2
Presuming all birthdays are equally probable, the probability of a given
1
birthday for a person chosen from the entire population at random is
(ignoring
365
February 29). Although the number of pairings in a group of 23 people is not statistically equivalent to 253 pairs chosen independently, the birthday problem becomes less surprising if a group is thought of in terms of the number of possible pairs, rather than as the number of individuals.

6

2.3 Calculating the probability of birthday problem
The problem is to compute the approximate probability that in a group of n people, at least two have the same birthday. For simplicity, disregard variations in the distribution, such as leap years, twins, seasonal or weekday variations, and assume that the 365 possible birthdays are equally likely. Real-life birthday distributions are not uniform since not all dates are equally likely.
The goal is to compute P(A), the probability that at least two people in the room have the same birthday. However, it is simpler to calculate P(A'), the probability that no two people in the room have the same birthday. Then, because
A and A' are the only two possibilities and are also mutually exclusive, P(A) = 1
− P(A').
In deference to widely published solutions concluding that 23 is the minimum number of people necessary to have a P(A) that is greater than 50%, the following calculation of P(A) will use 23 people as an example.
When events are independent of each other, the probability of all of the events occurring is equal to a product of the probabilities of each of the events occurring. Therefore, if P(A') can be described as 23 independent events, P(A') could be calculated as P(1) × P(2) × P(3) × ... × P(23).
The 23 independent events correspond to the 23 people, and can be defined in order. Each event can be defined as the corresponding person not sharing his/her birthday with any of the previously analyzed people. For Event 1, there are no previously analyzed people. Therefore, the probability, P(1), that Person 1 does not share his/her birthday with previously analyzed people is 1, or 100%. Ignoring
365
leap years for this analysis, the probability of 1 can also be written as , for
365
reasons that will become clear below.
For Event 2, the only previously analyzed people are Person 1. Assuming that birthdays are equally likely to happen on each of the 365 days of the year, the
364
probability, P(2), that Person 2 has a different birthday than Person 1 is . This
365
is because, if Person 2 was born on any of the other 364 days of the year, Persons
1 and 2 will not share the same birthday.
Similarly, if Person 3 is born on any of the 363 days of the year other than the birthdays of Persons 1 and 2, Person 3 will not share their birthday. This makes
363
the probability P(3) = .
365

This analysis continues until Person 23 is reached, whose probability of not
343
sharing his/her birthday with people analyzed before, P(23), is
.
365

P(A') is equal to the product of these individual probabilities:

7

365

364

363

362

343

The P(A’)=
∗
∗
∗
∗ …∗ terms of equation (1) can be collected to
365 365 365 365
365
arrive at:
P(A’)=(

1

)23 ∗ (365 ∗ 364 ∗ 363 ∗ … ∗ 343)

365

(2)

Evaluating equation (2) gives P(A') ≈ 0.492703
Therefore, P(A) ≈ 1 − 0.492703 = 0.507297 (50.7297%)
This process can be generalized to a group of n people, where p(n) is the probability of at least two of the n people sharing a birthday. It is easier to first calculate the probability p(n) that all n birthdays are different. According to the pigeonhole principle, p(n) is zero when n > 365. When n ≤ 365:

̅ ( ) = 1 ∗ (1 −

1
2
−1
) ∗ (1 −
) ∗ … ∗ (1 −
)
365
365
365

365
! ∗
365 ∗ 364 ∗ … ∗ (365 − + 1)
365!

=
=
=

(365 − )!

365
365
365
365
=
365
365

where '!' is the factorial operator, ( ) is the binomial coefficient and kPr

denotes permutation. The equation expresses the fact that the first person has no one to share a birthday, the second person cannot have the same birthday as the
364
363 first ( ), the third cannot have the same birthday as the first two (
), and in
365
365 th general the n birthday cannot be the same as any of the n − 1 preceding birthdays.
The event of at least two of the n persons having the same birthday is complementary to all n birthdays being different. Therefore, its probability p(n) is p(n)=1-̅ (n).
1

This probability surpasses for n = 23 (with value about 50.7%). The following
2
table shows the probability for some other values of n (this table ignores the existence of leap years, as described above, as well as assuming that each birthday is equally likely):

8

9

2.4 Abstract proof
Here we prove the same result as above, but with results about sets and functions to provide a simpler proof. Firstly, define S to be a set of N people and let B be the set of dates in a year.
Define the birthday function b : S →B to be the map that sends a person to their birthdate. So everyone in S has a unique birthday if and only if the birthday function is injective.
Now we consider how many functions, and how many injective functions, exist between S and B.
Since |S|=N and |B|=366, it follows that there are 366N possible functions, and 366/(366-N)! possible injective functions (see Twelvefold way#case i).
Let A be the statement "Everybody in the set S has a unique birthday" (so
P(A') is what we are actually looking for). By definition, P(A) is the fraction of injective functions out of all possible functions (i.e., the probability of the birthday function being one that assigns only one person to each birthdate), which gives:
366!
( ) =
.
(366−)!
366

Hence: ( ′ ) = 1 −

366!
366

(366−())!

10

3. Examples
Example 1:
There are 30 people at a party. Someone wants to bet you $10 that there are
2 people with exactly the same birthday. Should you take the bet?
To pose a mathematical problem we ignore February 29 which only comes in leap years, and suppose that each person at the party picks their birthday at random from the calendar. There are 36530 possible outcomes for this experiment.
The number of outcomes in which all the birthdays are different is: 365 ・ 364 ・
363 ・ ・ ・ ・ ・ 336 since the second person must avoid the first person’s birthday, the third the first two birthdays, and so on, until the 30th person must avoid the 29 previous birthdays. Let D be the event that all birthdays are different.
Dividing the number of outcomes in which all the birthdays are different by the total number of outcomes, we have:
( ) =

365 ∗ 364 ∗ 363 ∗ … ∗ 336
= 0.293684
36530

In words, only about 29% of the time all the birthdays are different, so you will lose the bet 71% of the time.
At first glance it is surprising that the probability of 2 people having the same birthday is so large, since there are only 30 people compared with 365 days on the calendar. Some of the surprise disappears if you realize that there are (30 ・ 29) / 2
= 435 pairs of people who are going to compare their birthdays. Let pk be the probability that k people all have different birthdays. Clearly, p1 = 1 and pk+1 = pk
(365 − k) / 365. Using this recursion it is easy to generate the values of pk for 1 ≤ k
≤ 40.

11

Example 2:
Let A = “Alice and Betty have the same birthday,” B = “Betty and Carol have the same birthday,” and C =“Carol and Alice have the same birthday.” Each pair of events is independent but the three are not.
Since there are 365 ways 2 girls can have the same birthday out of 3652 possibilities (as in Example 1.6, we are assuming that leap year does not exist and that all the birthdays are equally likely), P (A) = P (B) = P (C) = 1/365. Likewise, there are 365 ways all 3 girls can have the same birthday out of 3653 possibilities,
1
so ( ∩ ) =
= ()() that is, A and B are independent. Similarly, B
2
365

and C are independent and C and A are independent, so A, B, and C are pairwise independent. The three events A, B, and C are not independent; however, since A ∩
B = A ∩ B ∩ C and hence: ( ∩ ∩ ) =

12

1
3652

≠(

1

3

) = ()()()

365

4. References:
1.
"Elementary Probability for Applications"; Department of Mathematics,
Cornell University, Rick Durrett; 2009
2.
[Online].Available:http://www.teacherlink.org/content/math/interactive/pr obability/lessonplans/birthday/home.html 3.
[Online].Available:http://en.wikipedia.org/wiki/Birthday_problem#Abstra
ct_proof

13