52
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by joriki probability Jun 25 '16 at 16:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 7
    $\begingroup$ Depends on how you pick your friends. :-) Potentially, you just need 365 (366 in leap years, but you can chuck 'em the three years in-between.) $\endgroup$ – T.J. Crowder Sep 9 '15 at 15:40
  • 6
    $\begingroup$ @T.J.Crowder Craigslist ad: "Looking for new friend interested in hanging out, nothing weird. Must be born on April 28 or December 27." $\endgroup$ – Michael Sep 10 '15 at 16:06
  • $\begingroup$ I think my facebook friends cover every year. $\endgroup$ – Jorge Fernández Hidalgo Sep 15 '15 at 23:01
81
$\begingroup$

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 $$

$\endgroup$
  • 41
    $\begingroup$ As real coupon-collectors know, the trick is to swap friends with other collectors ;-) $\endgroup$ – Steve Jessop Sep 9 '15 at 14:26
  • 4
    $\begingroup$ @SteveJessop, those born on 29 February are going to be precious :) $\endgroup$ – zhoraster Sep 9 '15 at 14:38
  • 7
    $\begingroup$ @SteveJessop: I think real human friends count as Rares among Real Coupon-Collectors... $\endgroup$ – Phil H Sep 9 '15 at 14:46
  • 12
    $\begingroup$ A quick Monte-Carlo simulation suggests 2364 friends averages a 57% success rate; 3000 friends around 90%; around 3235 friends for 95% and roughly 3830 to get to 99% confidence. $\endgroup$ – TripeHound Sep 10 '15 at 10:06
  • 5
    $\begingroup$ @BobJarvis Biasing the dates using the figures in your link (assuming I've done it right), 2364 now gives about 43%; around 2450 is needed for 50%; about 4500 for 95% and as high as 6900 for 99%. $\endgroup$ – TripeHound Sep 10 '15 at 13:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.