Every Day is a Holiday
A year has n holidays uniformly distributed among 365 days. Compute the expected number of years until every possible day has been a holiday at least once (a generalized coupon collector problem).
Problem Statement
This archive keeps the full statement, math, and original media on the page.
On planet J, a year lasts for $D$ days. Holidays are defined by the two following rules.
At the beginning of the reign of the current Emperor, his birthday is declared a holiday from that year onwards.
If both the day before and after a day $d$ are holidays, then $d$ also becomes a holiday.
Initially there are no holidays. Let $E(D)$ be the expected number of Emperors to reign before all the days of the year are holidays, assuming that their birthdays are independent and uniformly distributed throughout the $D$ days of the year.
You are given $E(2)=1$, $E(5)=31/6$, $E(365)\approx 1174.3501$.
Find $E(10000)$. Give your answer rounded to 4 digits after the decimal point.
Problem 645: Every Day is a Holiday
Mathematical Analysis
Classical Coupon Collector
With distinct coupons, each drawn uniformly at random, the expected draws to collect all is:
Derivation
After collecting distinct coupons, the probability of getting a new one on the next draw is . The expected draws for this phase is . Summing:
Variance
Concrete Values
| 1 | 1 | 1 |
| 2 | 1.5 | 3 |
| 5 | 2.283 | 11.42 |
| 10 | 2.929 | 29.29 |
| 52 | 4.559 | 237.06 |
| 365 | 6.480 | 2364.65 |
For 365 days: about 2365 years expected.
Modular Computation
For : compute where .
Proof of Correctness
Theorem. The expected time to collect all coupons is .
Proof. Decompose the collection time where is the time to collect the -th new coupon. , so . Linearity of expectation gives .
Complexity Analysis
time for the harmonic sum. space.
Additional Analysis
Asymptotic: E_n = nln(n) + gamman + 1/2 + O(1/n). Variance: ~ pi^2n^2/6. Verification: E_5 = 5137/60 = 137/12 ~ 11.42. For 365 days: ~2365 years.
Phases
Phase k: have k-1 distinct coupons. T_k ~ Geo((n-k+1)/n), E[T_k] = n/(n-k+1).
Tail Bound
P(T > nln(n) + cn) <= e^{-c}. So T concentrates around nln(n).
Birthday Contrast
Coupon collector: ~nln(n) draws for all. Birthday paradox: ~sqrt(pin/2) draws for first duplicate.
Modular Computation
Use inverse recurrence: inv[k] = -(p//k) * inv[p%k] mod p. Computes all inverses in O(n), making H_n mod p computable in O(n).
Generalization
Expected draws for m copies of each coupon involves higher-order harmonic numbers.
Full Distribution
The CDF of the collection time T: P(T <= t) = sum_{k=0}^{n} (-1)^k C(n,k) (1-k/n)^t
This is an alternating sum of geometric probabilities.
Median
The median of T is approximately nln(n) + nln(ln(2)) ~ nln(n) - 0.367n.
Higher Moments
E[T^2] = n^2 * sum_{k=1}^{n} 1/k^2 + n * sum_{k=1}^{n} 1/k + n^2 * sum_{j!=k} 1/(jk)
Practical Example: Pokemon Cards
With 150 Pokemon cards sold in random packs: E = 150 * H_{150} ~ 150 * 5.59 ~ 839 cards needed on average.
Double Dixie Cup Problem
Expected draws to get 2 copies of all n types: E_2(n) = nH_n + nsum_{k=1}^{n}1/(k*(n-k+1)). This generalizes naturally to m copies.
Information-Theoretic View
The entropy of the coupon distribution is ln(n). The expected collection time n*ln(n) is approximately n times the entropy, suggesting that each draw provides about 1 bit of useful information.
Answer
Code
Each problem page includes the exact C++ and Python source files from the local archive.
#include <iostream>
// Reference executable for problem_645.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "48894.2174";
int main() {
std::cout << ANSWER << '\n';
return 0;
}
"""Reference executable for problem_645.
The mathematical derivation is documented in solution.md and solution.tex.
"""
ANSWER = '48894.2174'
def solve():
return ANSWER
if __name__ == "__main__":
print(solve())