“Birthday problem” paper to appear in Random Structures & Algorithms

My paper Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process, joint with Richard Arratia (a probabilist) and Joe Kilian (a computer scientist), will appear in the journal Random Structures & Algorithms. It contains several new results on the birthday problem: how many people do you need to have c birthdays in common? We give the asymptotic distribution as c grows with the number n of days as well as the moments of the asymptotic distribution via an uniform integrability result.

We address the case where c = O(n), because that is the case of interest for computer science. If you are interested in this subject, you might take a look at the variance in the coupon collector regime, where c is slightly larger than n — we did not address this in our paper.