Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process1. Issue 3 (6th July 2015) - Arratia, Richard; Garibaldi, Skip; Kilian, Joe
Abstract: 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 n π / 2 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 Rényi. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 480–502, 2016