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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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)={\binom {k}{2}}$ possible pairs of birthdays to compare, and so the probability that none of the ${\binom {k}{2}}$ pairs have the same birthday ($Q$) is

$Q=q^{\binom {k}{2}}=\left({\frac {n-1}{n}}\right)^{\binom {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)^{\binom {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\geq 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} -th person picks a different birthday than all prior people is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_k = \frac{n-(k-1)}{n} \quad \quad 0 < k \le c}

Let's shift this index to make the formula easier: Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \rightarrow k-1} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_k = \frac{n-k}{n} \quad \quad 0 \le k < c}

Therefore, we can find an expression for the probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} that all people have different birthdays given any value for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} q &= \prod_{k=0}^{c-1} q_k \quad = \quad \prod_{k=0}^{c-1} \frac{n-k}{n} \quad = \quad \frac{n}{n} \cdot \frac{n-1}{n} \cdot \frac{n-2}{n} \dots \frac{n-c+1}{n} \\ &= \quad \frac{n^{\underline{c}}}{n^c} \quad = \quad \frac{P(n,c)}{n^c} \\ \end{align}}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\underline{c}}} is a falling power. Note that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q=0} when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c=n+1} in keeping with the pigeonhole principle (the numerator of the last term becomes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-c+1 = n-(n-1)+1 = 0} ).

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} people, there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C(k,c) = \binom{k}{c}} possible ways to put them in groups of size Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} . Now we can generalize the probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q} that none of these groups have the same birthday.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q = q^{\binom{n}{c}} = \left( \frac{n^{\underline{c}}}{n^c} \right)^{\binom{k}{c}}}

In general, the probability Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} that at least one Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} -way collision occurs among Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} candidates from a codomain of cardinality Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = 1 - \left( \frac{n^{\underline{c}}}{n^c} \right)^{\binom{k}{c}}}

See Also

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