General birthday problem

The birthday problem, sometimes called the birthday paradox, says that it’s more likely than you’d expect that two people in a group have the same birthday. Specifically, in a random sample of 23 people, there’s about a 50-50 chance that two people share the same birthday.

The birthday problem makes a nice party trick, but generalizations of the problem come up frequently in applications. I wrote in the previous post how it comes up in seeding distributed Monte Carlo simulations. In computer science, it’s a concern in hashing algorithms.

If you have a set of N things to choose from, such as N = 365 birthdays, and take r samples, the probability that all r samples are unique is

p = \frac{N!}{N^r (N-r)!}

and the probability that at least two of the samples are the same is 1 – p. (This assumes that N is at least as big as r. Otherwise the denominator is undefined, but in that case we know p is 0.)

With moderately large values of N and r the formula is likely to overflow if implemented directly. So as usual the trick is to use logarithms to avoid overflow or underflow. Here’s how you could compute the probability above in Python. SciPy doesn’t have a log factorial function, but does have a log gamma function, so we use that instead.

    from scipy import exp, log
    from scipy.special import gammaln

    def prob_unique(N, r):
        return exp( gammaln(N+1) - gammaln(N-r+1) - r*log(N) )

 

Related: Need help with randomization?

2 thoughts on “General birthday problem

  1. IIRC, I once worked out that if you are sampling from an arbitrary discrete, possibly non-uniform distribution in the birthday problem (as in the real world not all birthdays are equally likely) you can show that that the probability p that at least two people share a birthday among N people is maximized when the distribution is uniform. There is a paper on this I found here: http://www.ism.ac.jp/editsec/aism/pdf/044_3_0479.pdf

  2. Correction to pervious post: Again, IIRC, it should be that p is minimized when there is an equal distribution. If you have a distribution f_1 = 1 and f_i = 0 for i =/= 1 then the probability there is a collision is 1.

Comments are closed.