aez-notes

If (r) persons compare birthdays in the pairing problem, the probability is \(P_R\) that at least 2 have the same birthday. What should \(n\) be in the personal birthmate problem to make your probability of success approximately \(R_R\)?

The probability that none of the \(r\) share a birthday is \(1-P_R\). If \(r\) is small we can probably treat these as independent trials. There are \(r (r-1) / 2\) pairings here, so we consider there being this many trials. So asking \(r (r-1) / 2\) people will give you a probability of approximately \(P_R\).