Coupon Collector’s Problem

The Coupon Collector’s Problem is about how many draws it is expected to take in order to collect all coupons by random draw. ¹

Solution

The solution to the problem is $n\ast H_n$, where $n$ is the number of coupons to collect and $H_n$ is the $n$-th harmonic number: ¹

$$n\ast \sum _{k=1}^n\frac{1}{k}$$

In Haskell: ¹

expected :: Int -> Float
expected n =
  fromIntegral n * sum [ 1.0 / (fromIntegral k) | k <- [1..n] ]

Footnotes

1. 20250419063935 ↩ ↩² ↩³