When are there too many collisions? Variants of the birthday problem

Abstract

Due to restrictions on the use of unique identifiers of individuals in data sets, there may be instances in which two or more data sets have some of the individuals in common, with no direct way to detect such occurrences. More generally, a collision occurs when two or more observations are in agreement with respect to variables associated with the observations. This article discusses several possible statistical/probabilistic approaches to determining when the number of collisions (or near-collisions) exceeds what would be expected by chance if in fact the observations are all distinct. The methods and results are related to the Birthday Problem and to Occupancy Problems.

Keywords:

• collisions
• coincidences
• birthday problem
• occupancy problem

Notes

1 Note that this formula is valid even when L > N, since $0!=1,$ and $f_i^0=1.$

2 In fact birthdays appear not to be evenly distributed. In a sample of 481,040 people listed on insurance applications in the United States, the percents of various birthdays (excluding February 29) ranged from 0.23% (December 26) to 0.31% (September 15). See: http://www.panix.com/ ∼murphy/bday.html.