The analysis of singletons in generalized birthday problems

This paper describes techniques to characterize the number of singletons in the setting of the generalized birthday problem, that is, the birthday problem in which the birthdays are non-uniformly distributed over the year. Approximations for the mean and variance presented which explicitly indicate the impact of the heterogeneity (expressed in terms of the Kullback-Leibler distance with respect to the homogeneous distribution). Then an iterative scheme is presented for determining the distribution of the number of singletons. The approximations are validated by experiments with demographic data.