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 be the number of items we draw with replacement from the pool with items. is the probability that at least one item is drawn more than once.
def birthday(n, k): if k > n: return 1 return 1 - (Permutations(n, k).cardinality() / (n ^ k))