On average, how many friends would I need to have to have at least one friend's birthday every day?

Question

I know that because of the birthday problem, even after 365 friends, you're going to have a lot of doubles and that there's also an infinitesimal chance that even with infinite friends that there's one day left out. But I was curious how many friends you'd need on average to have every day represented (this is ignoring leap day and assuming birthdays are equally distributed). Or to generalize it further, given n unique boxes and you're placing balls in them with an equal 1/n chance for the ball to go into any box, how many balls would you have to place on average before every box had at least one ball?

Answer 1

This is known as the coupon collector's problem, with the coupons in this case being birthdays.

If you keep adding friends one by one until you have one with each birthday, it will take 1 friend until you have the friend with one birthday. After the first friend, each new friend has a probability of $\frac{364}{365}$ to have a birthday you haven't seen yet, and the expected number of friends to go through until you see a new birthday is the reciprocal of that probability, that is $\frac{365}{364}$. After this, the expected number of friends until you see the third unique birthday is $\frac{365}{363}$, and so forth.

The key insight here is that once you have seen, say, 42 different birthdays, the expected number of more friends you have to inspect until you see a new birthday does not depend on how many friends it took you to reach 42, so we can calculate the expectation for each next-unseen-birthday wait separately and just sum them.

The total expected number of friends until you have seen all birthdays is $$ 1+\frac{365}{364}+\frac{365}{363}+\cdots+\frac{365}{2}+\frac{365}{1} = 365\left(\frac1{365}+\frac1{364}+\frac1{363}+\cdots+\frac12+1\right)=365 H_{365} $$ where $H_{365}$ is the 365th harmonic number, which is approximately $\ln(365)+0.577$ (the added term is the Euler-Mascheroni constant).

So you need about $365\cdot(\ln(365)+0.577)=2364$ friends.

---

If we take leap days into account (but still assume all birthdays except February 29 are uniformly distributed and the probability of being born on Feb 29 is $\frac{0.25}{365.25}$), things begin to get more complex.

To compute the expected time until all other days than February 29 have been seen, the numerators in the first sum above all become $365.25$ instead of $365$, so this expectation is $\frac{365.25}{365}2364 \approx 2366$. That's not much of a difference, so the main correction comes from the risk that we won't have seen any February 29 by the time all of the other days have been hit.

We can estimate the risk of this happening crudely as $(\frac{365}{365.25})^{2364}\approx 0.1982$ -- but this is not at all exact because (among other reasons) the averaging that led to 2364 does not commute with the non-linear $x\mapsto (365/365.25)^x$ mapping.

The exact risk is $$ \frac{365}{365.25} \times \frac{364}{364.25} \times \frac{363}{363.25} \times \cdots \times \frac{1}{1.25} = \frac{\Gamma(366)\Gamma(1.25)}{\Gamma(366.25)} \approx 0.2073$$ namely, each time we wait for a new birthday the risk that the next new birthday will be non-leap.

(To evaluate the gammas we can either cheat and use Wolfram Alpha, or use the approximation $\Gamma(a+\varepsilon)/\Gamma(a)\approx (a+\frac\varepsilon2-\frac12)^{\varepsilon}$ which gives plenty of precision here and allows us to compute the risk as $\frac{\Gamma(\frac14)}{4 \sqrt[4]{365\frac58}}$ if only we can find $\Gamma(\frac14)$ in a reference work).

So the expected number of friends in the leap-day scenario should be $$ 2366 + 0.2073 \frac{365.25}{0.25}\approx 2669 $$