The Facebook Birthday Problem（Birthday Problem Variation）

Question

The Facebook Birthday Problem:

This problem stems from the classic Birthday Paradox.
It says:

How many friends do you need for the probability of having at least one friend with a birthday each day to be greater than 50%?
Answer: If there are 23 friends, the probability of two or more people sharing a birthday exceeds 50%. If there are 60 people, the probability exceeds 99%.

If there are birthdays every day among my friends on Facebook, and I want to send birthday wishes to them every day, how many friends do I need to achieve this daily occurrence? How is the probability calculated?

Q1-1: If I have 1000 friends on Facebook, what is the probability that there will be a friend's birthday every day?
Q1-2: If I have 5000 friends on Facebook, what is the probability that there will be a friend's birthday every day?

Q2-1: How many friends do I need at least to ensure that there is a friend's birthday every day with a probability of more than 50%?
Q2-2: How many friends do I need at least to ensure that there is a friend's birthday every day with a probability of more than 99%?

(Calculations are made without considering leap years.)

This problem is not really a "Birthday Problem", but more like a "coupon collector's problem".

Answer 1

If you have $n$ friends, the probability that you have a friend with each birthday is $$ \frac{{n\brace 365}\cdot 365!}{365^n}. $$ The notation ${n\brace k}$ refers to the Stirling numbers of second kind, which can be calculated using this formula: $$ {n\brace k}=\frac1{k!}\sum_{j=0}^k(-1)^{j}\binom kj(k-j)^n. $$ Plugging in $1000$ and $5000$ for $n$ into that formula answers your first two questions. For $1000$ friends, the probability is nearly zero (one in a trillion), while for $5000$ friends, the probability is $\approx 99.96\%$. You can then use a computer to find the smallest value of $n$ for which that formula is greater than $0.5$ and $0.99$. Doing so, I found that you need $2287$ friends to succeed more than $50\%$ of the time, and you need $3828$ friends to succeed more than $99\%$ of the time.

Answer 2

When you have $n$ friends on Facebook, the probability that there is a friend's birthday every day is given by

$$P_n=\mathbb P \left (\cap_{i=1}^{365} D'_i \right )=\\1-\mathbb P \left (\cup_{i=1}^{365} D_i \right )=\\1- \sum_{i=1}^{365} (-1)^{i-1} \binom{365}{i} \left (1-\frac{i}{365} \right )^n=$$ $$\color{blue}{\sum_{i=0}^{365} (-1)^{i} \binom{365}{i} \left (1-\frac{i}{365} \right )^n} \tag{1}$$

where $D_i$ is the event that there is no birthday in day $i$ (the inclusion-exclusion principle is applied to find the probability of the union $\cup_{i=1}^{365} D_i$).

Using (1), the answers to both parts of $Q1$ can be obtained by setting $n=1000$ and $n=5000$.

To solve Q2, you need to find the smallest $n$ that satisfies:

$$ P_n \ge \alpha$$

for $\alpha=0.5$ and $\alpha= 0.99$.

Working with the sum appearing in (1) seems difficult. Fortunately, using

$$ e^{-\frac{i}{365}} \approx 1-\frac{i}{365},$$

the formula (1) can be well approximated by the following simple formula:

$$\color{blue}{P_n \approx \left (1-e^{-\frac{n}{365}} \right)^{365}}.$$

This approximation enables us to compute the probability $P_n$ easily. For $n=1000$ and $n=5000$, it returns $2.6 \times 10^{-11}$ and $0.9995898$, which are very close to the actual values.

Moreover, to have $P_n \ge \alpha$, we get the closed-form lower bound for $n$:

$$\color{blue}{n \ge -365 \log \left (1-\alpha^{\frac{1}{365}} \right)}.$$