# Calculating the probability of duplication in a random number sample

If I sample 23 random numbers from 1-365, how could I calculate the probability of there being a duplicate?

Context to this question: I was looking into the birthday paradox and I wanted to explore it using the pigeonhole principle. This got me thinking that we could represent the birthday paradox as a random number process.

## 1 Answer

This calculation can be done using simple combinatorial reasoning. However, more general problems like this can be done using the classical occupancy distribution (see e.g., O'Neill 2020). Suppose you take a sample of size $$n$$ from a set of $$m$$ distinct numbers, and let $$K$$ be the number of distinct numbers you sample. This random variable follows the clssical occupancy distribution $$K \sim \text{Occ}(n,m)$$. With your values you get:

\begin{aligned} \mathbb{P}(K < n) &= 1 - \mathbb{P}(K = n) \\[12pt] &= 1 - \text{Occ}(23|23, 365) \\[6pt] &= 1 - \frac{(365)_{23}\cdot S(23,23)}{365^{23}} \\[6pt] &= 1 - \frac{364}{365} \cdot \frac{363}{365} \cdot \ ... \ \cdot \frac{343}{365} \\[12pt] &= 0.5072972. \\[12pt] \end{aligned}

Thus, with $$n=23$$ sampled values, you have an $$50.73%$$ chance of at least one duplicated day. You can use the classical occupancy distribution to compute the probabilities for any given number of distinct values in the sample, or to find the expected number of distinct numbers, etc.

• I don't quite follow how P(K>0) is the probability of at least duplicate. If K is the number of distinct numbers, isn't P(K>0) the probability of there at least 1 distinct number? May 13 '20 at 9:57
• Sorry --- I have edited to correct the error.
– Ben
May 13 '20 at 10:16