3
$\begingroup$

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?

  • 0
    Your link to an earlier question does not discuss pairs. It would have been been $\frac{n(n-1)}{2N}$, counting triplets as three pairs and quadruplets as six pairs.2012-09-03

2 Answers 2

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

  • 0
    @Wuschelbeutel Kartoffelhuhn: mjqxxxx's answers are exact within the assumptions: $n$ i.i.d. birthdays selected from $N$ equally probable days.2012-09-03
0

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.