Birthday Paradox

Question: Given a room of $k$ people, how likely is it that two of them will have the same birthday?

Assumptions:

• there are $n=365$ 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 ($q$). The probability that two people have the same birthday is $p=\frac{1}{n}$, so we can find $q$ in terms of $p$ and thus in terms of $n$:

$q=1-p=1-\frac{1}{n}=\frac{n-1}{n}$

Given $k$ people, there are $C(k,2)=(\genfrac{}{}{0ex}{}{k}{2})$ possible pairs of birthdays to compare, and so the probability that none of the $(\genfrac{}{}{0ex}{}{k}{2})$ pairs have the same birthday ($Q$) is

$Q=q^{(\genfrac{}{}{0ex}{}{k}{2})}={\left(\frac{n-1}{n}\right)}^{(\genfrac{}{}{0ex}{}{k}{2})}$

In other words, $Q$ 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 $k$ people share the same birthday in a "year" containing $n$ days is

$P=1-Q=1-{\left(\frac{n-1}{n}\right)}^{(\genfrac{}{}{0ex}{}{k}{2})}$

Analysis

Figure 1. Plot of $P$ vs. $k$ for $n=365$

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

Table 1. Values of $P$ for various $k$ up to $P\ge 0.99$

$k$	$P$
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 $c=2$ people have the same birthday. Suppose we want to find the probability that at least any $c$ people have the same birthday?

Let's start by generalizing the probability $q$ that all members of a group of $c$ people have different birthdays. For the sake of argument, let's suppose that each member of a group of $c$ 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 ($n$ valid choices out of $n$ total; gives $q_1=\frac{n}{n}$)
• The second person may choose any day except the one that the first person picked ($n-1$ valid choices out of $n$ total; gives $q_2=\frac{n-1}{n}$)
• The third person may choose any day except for those taken by the first two people ($n-2$ valid choices out of $n$ total; gives $q_3=\frac{n-2}{n}$)
• ...
• The last person may choose any day except for those taken by the other $c-1$ people ($n-(c-1)$ valid choices out of $n$ total; gives $q_c=\frac{n-c+1}{n}$)

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

$q_k=\frac{n-(k-1)}{n}0<k\le c$

Let's shift this index to make the formula easier: Let $k\to k-1$:

$q_k=\frac{n-k}{n}0\le k<c$

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

$\begin{array}{rl}q& =\prod _{k=0}^{c-1}{q}_k=\prod _{k=0}^{c-1}\frac{n-k}{n}=\frac{n}{n}\cdot \frac{n-1}{n}\cdot \frac{n-2}{n}\dots \frac{n-c+1}{n}\\ & =\frac{n^{\underset{\_}{c}}}{n^c}=\frac{P(n,c)}{n^c}\\ \end{array}$

Where $n^{\underset{\_}{c}}$ is a falling power. Note that $q=0$ when $c=n+1$ in keeping with the pigeonhole principle (the numerator of the last term becomes $n-c+1=n-(n-1)+1=0$).

Given $k$ people, there are $C(k,c)=(\genfrac{}{}{0ex}{}{k}{c})$ possible ways to put them in groups of size $c$. Now we can generalize the probability $Q$ that none of these groups have the same birthday.

$Q=q^{(\genfrac{}{}{0ex}{}{n}{c})}={\left(\frac{n^{\underset{\_}{c}}}{n^c}\right)}^{(\genfrac{}{}{0ex}{}{k}{c})}$

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

$P=1-{\left(\frac{n^{\underset{\_}{c}}}{n^c}\right)}^{(\genfrac{}{}{0ex}{}{k}{c})}$

See Also

• Understanding the Birthday Paradox on Better Explained
• Birthday problem on Wikipedia