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 * H_n, where n is the number of coupons to collect and H_n is the n-th harmonic number: ¹

$$ n * \sum_{k=1}^n \frac 1 k $$

In Haskell: ¹

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