Skip to Content

Drawing the Same Item More Than Once is Surprisingly Likely

When drawing items from a pool with replacement, the probability that you’ll draw the same item more than once is much higher than intuition would suggest.

Often called the Birthday Paradox and framed thus: in a group of 23 people, there is a greater than 50% chance that at least two people will share a birthday.


Let kk be the number of items we draw with replacement from the pool with nn items. p(n,k)p(n,k) is the probability that at least one item is drawn more than once.

p(n,d)={1nPknkkn1k>np(n,d)=\begin{cases} 1 - \frac{_{n}P_{k}}{n^{k}} &k \leq n \\ 1 &k \gt n \end{cases}

In SageMath:

def birthday(n, k):
    if k > n:
        return 1
    return 1 - (Permutations(n, k).cardinality() / (n ^ k))