3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Henry
    May 13 '20 at 9:57
  • $\begingroup$ Sorry --- I have edited to correct the error. $\endgroup$
    – Ben
    May 13 '20 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.