How many people should be invited to a party in order to make it likely that there are three people with the same birthday?
This problem extends the birthday paradox from finding two people with the same birthday to finding three people with the same birthday. We want to find the number of people \(k\) such that the probability of at least three sharing a birthday is at least \(1/2\).
Indicator random variable approach
Let’s use indicator random variables similar to the birthday paradox analysis in Section 5.4.1. For each day \(d \in \{1, 2, \ldots, n\}\) (where \(n = 365\)), let \(X_d\) be the number of people with birthday on day \(d\).
If we have \(k\) people, then \(X_d\) follows a binomial distribution:
\[X_d \sim \text{Binomial}\left(k, \frac{1}{n}\right)\]The probability that day \(d\) has at least 3 people is:
\[\begin{align*} \Pr\{X_d \geq 3\} &= 1 - \Pr\{X_d = 0\} - \Pr\{X_d = 1\} - \Pr\{X_d = 2\} \\ &= 1 - \left(\frac{n-1}{n}\right)^k - k\left(\frac{1}{n}\right)\left(\frac{n-1}{n}\right)^{k-1} - \binom{k}{2}\left(\frac{1}{n}\right)^2\left(\frac{n-1}{n}\right)^{k-2} \end{align*}\]Let \(I_d\) be the indicator random variable for the event that day \(d\) has at least 3 people. The expected number of days with at least 3 people is:
\[\begin{align*} \mathrm{E}\left[\sum_{d=1}^n I_d\right] &= \sum_{d=1}^n \mathrm{E}[I_d] \\ &= n \cdot \Pr\{X_d \geq 3\} \end{align*}\]When this expected value is at least 1, we can expect that there’s likely to be a day with at least 3 people.
Approximation using Poisson distribution
For large \(n\) and small \(k/n\), we can approximate the binomial distribution with a Poisson distribution with parameter \(\lambda = k/n\):
\[X_d \approx \text{Poisson}(\lambda)\]Then:
\[\begin{align*} \Pr\{X_d \geq 3\} &\approx 1 - e^{-\lambda}\left(1 + \lambda + \frac{\lambda^2}{2}\right) \end{align*}\]Setting \(\lambda = k/n\) and requiring that the expected number of days with at least 3 people is 1:
\[\begin{align*} n \cdot \left(1 - e^{-k/n}\left(1 + \frac{k}{n} + \frac{k^2}{2n^2}\right)\right) &= 1 \end{align*}\]For \(k\) much smaller than \(n\), we can approximate \(e^{-k/n} \approx 1 - k/n + k^2/(2n^2)\). After some algebra:
\[\begin{align*} n \cdot \left(\frac{k^3}{6n^3}\right) &\approx 1 \\ \frac{k^3}{6n^2} &\approx 1 \\ k^3 &\approx 6n^2 \\ k &\approx (6n^2)^{1/3} \\ k &\approx n^{2/3} \cdot 6^{1/3} \\ k &\approx 1.817 \cdot n^{2/3} \end{align*}\]For \(n = 365\):
\[\begin{align*} k &\approx 1.817 \times 365^{2/3} \\ &\approx 1.817 \times 49.5 \\ &\approx 88 \end{align*}\]
Numerical verification
We can verify this numerically. The exact probability that at least one day has 3 or more people can be computed, though it’s complex. For \(k = 88\):
Using the Poisson approximation with \(\lambda = 88/365 \approx 0.241\):
\[\begin{align*} \Pr\{X_d \geq 3\} &\approx 1 - e^{-0.241}(1 + 0.241 + 0.029) \\ &\approx 1 - 0.786 \times 1.270 \\ &\approx 1 - 0.998 \\ &\approx 0.002 \end{align*}\]Expected number of days: \(365 \times 0.002 \approx 0.73\)
For \(k = 94\), with \(\lambda = 94/365 \approx 0.258\):
Expected number of days \(\approx 1.03\)
Through more careful calculation (or simulation), the answer is approximately \(k \approx 88\) to \(94\) people for the probability to be around \(1/2\).