An ice-cream stand sells a "surprise scoop": each day you buy one, and the stand picks flavour i with probability weights[i] / sum(weights), independently of every other day. After days days, how many different flavours do you expect to have tasted?
Write expected_flavours(weights: list[int], days: int) -> Fraction returning the exact expectation as a fractions.Fraction.
expected_flavours([1, 1], 1) # Fraction(1, 1) one scoop, one flavour
expected_flavours([1, 1], 2) # Fraction(3, 2) same flavour twice with prob 1/2
expected_flavours([1, 3], 2) # Fraction(11, 8)
expected_flavours([5, 2, 9], 0) # Fraction(0, 1)
Tracking which set of flavours you have seen is hopeless with 30 flavours, and listing every sequence of scoops is len(weights) ** days.
Constraints: 1 <= len(weights) <= 30, 1 <= weights[i] <= 100, 0 <= days <= 500.
Hint: Flavour i is never picked in days independent days with probability (1 - p_i) ** days, so the answer is Σ (1 - (1 - p_i) ** days) with p_i = Fraction(weights[i], sum(weights)).
Show hint
Write the number of flavours tried as a sum over flavours of "did I taste flavour i at least once?". The expectation of a sum is the sum of the expectations, even though these events are not independent.