Can You Salvage Your Rug?

People enter a room one at a time with independent uniform birthdays (no leap day). The moment two share a birthday, everyone stops and eats cake. On average, how many people are in the room? Extra credit: if instead they wait for the first triple birthday?

Solution

Let $N$ be the number of people present when the cake is cut. Use $\mathbb{E}[N] = \sum_{n \ge 1}\Pr(N \ge n)$. The party is still going when the $n$-th person walks in only if the first $n - 1$ birthdays were all distinct, so $$\Pr(N \ge n) = \prod_{i=0}^{n-2}\frac{365 - i}{365},$$ and summing these survival probabilities, $$\mathbb{E}[N] = \sum_{n \ge 1}\ \prod_{i=0}^{n-2}\frac{365 - i}{365} = \boxed{24.62}.$$ The newcomer who creates the match is counted too, which is why the answer sits a little above the familiar $23$ from the classic “better-than-even” birthday question.

For the triple version, track how many days have been hit exactly once ($a$) and exactly twice ($b$). A newcomer lands on a fresh day (with probability $\tfrac{365 - a - b}{365}$), on a once-hit day (probability $\tfrac{a}{365}$, making a pair), or on a twice-hit day (probability $\tfrac{b}{365}$, ending the party). Propagating this little chain and again summing survival probabilities, $$\mathbb{E}[N] = \boxed{88.74}.$$

The computation

Sum the survival probabilities. For the pair version this is a single product; for the triple version, push the distribution over (once-hit, twice-hit) days forward one arrival at a time.

P = 1.0; E = 0.0                                # pair version
for n in range(1, 400):
    E += P                                      # P(N >= n)
    P *= (365 - (n - 1)) / 365
print(E)                                        # 24.6166

def triple():
    dist = {(0, 0): 1.0}; E = 1.0               # (once-hit, twice-hit) days
    while dist:
        nxt = {}
        for (a, b), pr in dist.items():
            fresh, once = (365 - a - b) / 365, a / 365
            if fresh: nxt[(a+1, b)] = nxt.get((a+1, b), 0) + pr * fresh
            if once:  nxt[(a-1, b+1)] = nxt.get((a-1, b+1), 0) + pr * once
        dist = {k: v for k, v in nxt.items() if v > 1e-17}
        E += sum(dist.values())
    return E
print(triple())                                 # 88.7389