A night market has m food stalls. Each of n visitors buys from exactly one stall, choosing stall j with probability proportional to its popularity weights[j], independently of the other visitors. A stall that gets no visitor at all is a quiet stall.
Write quiet_stalls(weights, n) that returns a tuple of three floats for the number Q of quiet stalls:
- the expected value
E[Q], - the variance
Var(Q), - the value you would get for the variance if the stalls' "quiet or not" outcomes were independent, that is, the sum of the variances of the individual stalls' 0/1 outcomes.
The last two differ because the stalls compete for the same visitors: if one stall is quiet, the others got more visitors. The setup provides stall_weights(m, seed) (a list of popularity weights) and market_days(weights, n, days, seed) (simulates days market days and returns the list of quiet-stall counts), so you can compare your formulas with a simulation.
Examples
Input: weights = [1, 1], n = 2
Output: (0.5, 0.25, 0.375)
Explanation: the two visitors choose (A, A), (A, B), (B, A) or (B, B), each with
probability 1/4. Q is 1, 0, 0, 1, so E[Q] = 0.5 and Var(Q) = 0.5 - 0.25 = 0.25.
Each stall alone is quiet with probability 1/4 and has variance 1/4 · 3/4 = 0.1875;
treating them as independent would give 0.375.
Input: weights = [2, 1, 1], n = 4
Output: (0.6953125, 0.35247802734375, 0.491180419921875)
Constraints
1 <= len(weights) <= 600, every weight a positive number0 <= n <= 10**5- floats are compared with a tolerance of
1e-6
Goals
- Write a count as a sum of dependent indicator variables
- Compute the variance of a sum from the variances and covariances of its terms
- See how much the variance changes when dependence is ignored