# All dates covered

I had dinner with some old 🙂 university friends recently. Mike actually mentioned the problem about birthday pairings, but said he was wondering…

*What is the average number of people he should expect to add to a birthday book before he would have at least one person for each of the 365 dates?*

I thought about this for a while. Mike doesn’t care how many people in each date, just that there’s at least one person for each date. So each date is either live (awaiting its first entry) or not (already has at least one entry).

If n dates (out of 365) are still unused, then the average waiting time for one to be filled is 365/n days. For example, when half the days are filled (and so half are unused), there would be on average 2 days before another previously unused day was used.

So the total expected time to wait for all 365 dates to be filled is

365 365 365 … 365 365 365

*=== + === + === + = + === + === + ===
365 364 363 … 3 2 1*

Reversing the order of the terms, and taking out the common factor of 365, we get the number of days is

* 1 1 1 … 1 1 1
365 x (= + = + = + = + === + === + ===)
1 2 3 … 363 364 365
*The expression in parentheses is called the harmonic series (deserving of a post all by itself – hmm…)

The sum of the harmonic series up to 1/n becomes (very!) close to log_{e}(n)+γ.

Notes:

– e is Euler’s number, about 2.71828, the base of natural logarithms, and (as does π) appears just about *everywhere*.

– γ is the so-called Euler-Mascheroni constant, 0.5772156649015329… (and is defined by this very difference).

So the expected (i.e. average) total wait for all dates to be used at least once is 365 x (log_{e}(365)+γ) = 2365 days (rounded up) = 6.48 years.

Of course, a birthday book to accommodate 2365 people’s names will have to be quite a size!

Actually it’s worse than that. You can expect about 5% (i.e. 18) of dates to have 12 or more entries. Because you can’t predict which dates will be well used, you’ll need 365 x 12 = 4380 name spaces, if you want enough space to cover 95% of the dates.

Taking February 29 into account is tricky (i.e. it’s too difficult for me) in an exact (algebraic) way. It occurs only once every 1461 days (just under 1/4 as often as all other dates), and so will add noticeably to the expected time. An Excel simulation suggests an average wait of about 2750 days, or 7.5 years.