Extension of the Birthday Problem

Question

How do you find the expected number of people (or the expected number of pairs) among the n that share their birthday within r days of each other?

For the regular birthday problem, it's $n\left(1-(1-1/N)^{n-1}\right)$ expected people or ${n\left(1-(1-1/N)^{n-1}\right) \choose 2}$ pairs (see https://math.stackexchange.com/a/35798/39038). In this link, is it correct to derive the expected number of people among the n that share their bday within r days of each other using the same steps, but just with replacing $\frac{1}{N}$ with $\frac{1+2r}{N}$ ? In other words, is $$n\left(1-(1-(2r+1)/N)^{n-1}\right) \choose 2$$ correct for the expected number of pairs?

Answer 1

Expectation is linear, so if you can calculate the probability that a given person shares his birthday with anyone else (within $\pm r$ days, in your case), then you can multiply that by $n$ and find the expected number of such people. The probability that no-one else has their birthday within the excluded $2r+1$ days is given by $$ \left(1-\frac{2r+1}{N}\right)^{n-1}, $$ and so the expected number of people with at least birthday partner is $$ n - n\left(1-\frac{2r+1}{N}\right)^{n-1} $$ as you stated. However, the expected number of pairs is not the same as the number of pairs among the expected number of people: for one thing, not every pair of people with birthday partners are birthday partners with each other; and even if they were, expectation is not distributive. The exact expected number of pairs is just $n(n-1)/2$ times the probability that a given pair is partnered, which is $(2r+1)/N$. So the expected number of pairs is $$ \frac{n(n-1)(2r+1)}{2N}. $$ Both of these expressions are of order $1$ in the same regime, viz., $n \sim \sqrt {N/r}$.

Answer 2

It is accurate in the limit that you expect pairs to be rare. The corrections come when one person is a member of more than one pair. As you expand the window from $0$ to $r$ the corrections become more important.