Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process†

We study the random variable B(c, n), which counts the number of balls that must be thrown into n equally-sized bins in order to obtain c collisions. The asymptotic expected value of B(1, n) is the well-known appearing in the solution to the birthday problem; the limit distribution and asymptotic moments of B(1, n) are also well known. We calculate the distribution and moments of B(c, n) asymptotically as n goes to ∞ and c = O(n). We have two main tools: an embedding of the collision process — realizing the process as a deterministic function of the standard Poisson process — and a central limit result by Renyi. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015