Variance of the number of shared-birthday pairs

Question

In a room of n people with birthdays independent and uniform over d = 365 days, let X be the number of pairs of people who share a birthday. What are E[X] and \mathrm{Var}(X)?

Accepted Answer

Write X = \sum{\{i,j\}} I{ij}, an indicator over all \binom{n}{2} pairs, with I{ij} = 1 iff persons i and j share a birthday. A specific pair matches with probability 1/d, so E[X] = \binom{n}{2}\cdot\frac1d. Variance, the surprise. Consider two pairs and their covariance P(I{ij} = I{kl} = 1) - \frac{1}{d^2}. - Disjoint pairs (four different people): the two matches are independent, so P(	ext{both}) = \frac{1}{d^2}, and the covariance is \frac{1}{d^2} - \frac{1}{d^2} = 0. - Overlapping pairs (sharing one person, say \{i,j\} and \{i,k\}): both match iff i, j, k all share a birthday, which has …

Variance of the number of shared-birthday pairs

Your answer

More Probability questions