Every box of a cereal brand contains one sticker. There are len(weights) different stickers, and each box contains sticker j with probability weights[j] / sum(weights), independently of the other boxes. A collector only wants the stickers whose numbers are in the list needed. Let B be the number of boxes she opens until she owns every needed sticker.
Write boxes_to_complete(weights, needed) that returns the tuple (E[B], sd(B)): the expected number of boxes and the standard deviation of that number, computed exactly (not by simulation).
With equal weights this is the Level 4 lesson's question about seeing all six faces of a die, where the answer is 14.7. With unequal weights the rare stickers dominate and the lesson's argument no longer works directly.
The setup provides sticker_weights(m, seed) (random print frequencies for m stickers) and open_boxes(weights, needed, trials, seed), which simulates trials collectors and returns the list of their box counts, so you can check your answer by simulation.
Examples
Input: weights = [1, 1, 1, 1, 1, 1], needed = [0, 1, 2, 3, 4, 5]
Output: (14.7, 6.244197306299665)
Input: weights = [3, 1], needed = [0, 1]
Output: (4.333333333333333, 3.2317865716108862)
Explanation: sticker 0 comes in 3 boxes out of 4, sticker 1 in 1 out of 4. You wait on
average 4 boxes for the rare one, and in the rare case that it comes first you still
need the common one: 4.333 boxes on average, with a large spread.
Constraints
1 <= len(weights) <= 40, every weight a positive integerneededholds0to15different indices of stickers; if it is empty,B = 0- floats are compared with a tolerance of
1e-6(relative or absolute)
Goals
- Compute an expected waiting time exactly when outcomes have unequal probabilities
- Relate the time to collect everything to the times until each set of items first appears
- Obtain the variance as well as the mean, and check both against a simulation