Calculating the Birthday Paradox in SciPy
John Cook looks at how to calculate the probability that two people in a group have the same birthday in SciPy.
Join the DZone community and get the full member experience.
Join For FreeThe 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
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) )
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments