Birthday Paradox

From Notes
(Redirected from Birthday paradox)
Jump to navigation Jump to search
Question: Given a room of people, how likely is it that two of them will have the same birthday?


Assumptions:

  • there are possible birthdays
  • all birthdays are equally (uniformly) randomly distributed


Solution

The basis for this paradox is finding the probability that no two people have the same birthday (). The probability that two people have the same birthday is , so we can find in terms of and thus in terms of :

Given people, there are possible pairs of birthdays to compare, and so the probability that none of the pairs have the same birthday () is

In other words, describes the event that all birthdays are unique. The complement of this is at least one pair of people share the same birthday. Thus the probability that two people out of people share the same birthday in a "year" containing days is


Analysis

Figure 1. Plot of vs. for

It's worth noting that for by the pigeonhole principle (recall the assumption that there are days in a year). However, approaches 1 much more quickly than one might think (See Figure 1). In fact, for people. Table 1 Gives the values of up to 0.99 with significant confidence probabilities (0.50, 0.75, 0.90, 0.95, 0.99) highlighted.

Table 1. Values of for various up to
0 0.00
1 0.00
2 0.00
3 0.01
4 0.02
5 0.03
6 0.04
7 0.06
8 0.07
9 0.09
10 0.12
11 0.14
12 0.17
13 0.19
14 0.22
15 0.25
16 0.28
17 0.31
18 0.34
19 0.37
20 0.41
21 0.44
22 0.47
23 0.50
24 0.53
25 0.56
26 0.59
27 0.62
28 0.65
29 0.67
30 0.70
31 0.72
32 0.74
33 0.77
34 0.79
35 0.80
36 0.82
37 0.84
38 0.85
39 0.87
40 0.88
41 0.89
42 0.91
43 0.92
44 0.93
45 0.93
46 0.94
47 0.95
48 0.95
49 0.96
50 0.97
51 0.97
52 0.97
53 0.98
54 0.98
55 0.98
56 0.99


Generalization

The above discussion, we found an expression for the probability that at least people have the same birthday. Suppose we want to find the probability that at least any people have the same birthday?

Let's start by generalizing the probability that all members of a group of people have different birthdays. For the sake of argument, let's suppose that each member of a group of people take turns picking their birthday, and when everyone is done, all of them must have different birthdays.

  • The first person may choose any day ( valid choices out of total; gives )
  • The second person may choose any day except the one that the first person picked ( valid choices out of total; gives )
  • The third person may choose any day except for those taken by the first two people ( valid choices out of total; gives )
  • ...
  • The last person may choose any day except for those taken by the other people ( valid choices out of total; gives )

In general, any person may pick any day except those taken by all prior people. Hence the probability that the -th person picks a different birthday than all prior people is:

Let's shift this index to make the formula easier: Let :

Therefore, we can find an expression for the probability that all people have different birthdays given any value for :

Where is a falling power[1]. Note that when in keeping with the pigeonhole principle (the numerator of the last term becomes ).

Given people, there are possible ways to put them in groups of size . Now we can generalize the probability that none of these groups have the same birthday.

In general, the probability that at least one -way collision occurs among candidates from a codomain of cardinality is


See Also


Footnotes

  1. Falling powers, also called the Pochhammer symbol, are another way of representing the permutation function .