Paper Info
Title
Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process.
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 root n pi/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 infinity 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. (C) 2015 Wiley Periodicals, Inc.
Year
DOI
Venue
2016
10.1002/rsa.20591
RANDOM STRUCTURES & ALGORITHMS
Keywords
Field
DocType
birthday problem,collisions,Renyi,urn problem,size bias,chi distribution
Discrete mathematics,Combinatorics,Birthday problem,Central limit theorem,Random variable,Embedding,Ball (bearing),Chi distribution,Expected value,Mathematics,Asymptotic distribution
Journal
Volume
Issue
ISSN
48.0
3.0
1042-9832
Citations 
PageRank 
References 
0
0.34
3
Authors
3
Name
Order
Citations
PageRank
Richard Arratia118221.00
Skip Garibaldi221.46
Joe Kilian370788.92