Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 http://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?

share|improve this question
    
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. –  Henry Sep 3 '12 at 21:26

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Thanks for pointing out my mistake. Your E(X) expression is simpler than I expected: the number of pairs times the success probability (binomial dist mean). However, I'm not sure if this is an approximation or if it is exact (correlation issues after you've accounted for a pair already) –  Wuschelbeutel Kartoffelhuhn Sep 3 '12 at 17:41
    
@Wuschelbeutel Kartoffelhuhn: mjqxxxx's answers are exact within the assumptions: $n$ i.i.d. birthdays selected from $N$ equally probable days. –  Henry Sep 3 '12 at 21:23

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.