Problem 403315 · medium · Level 04 Non-Linear Data Structures

Bursty or Steady?

Poisson distribution · mean equals variance · expected frequencies · model checking

A shop logs how many returns it receives each day. If returns arrive independently at a steady rate, the daily counts follow a Poisson distribution, whose variance equals its mean. If they come in clumps (a faulty product line, a holiday) the variance is larger; if they are spread out more evenly than chance (an appointment system), it is smaller.

Write dispersion_report(counts) for a list of daily counts. Let n = len(counts) and m = max(counts). Return a dict with:

  • "mean": the mean of the counts,
  • "variance": the sample variance (dividing by n - 1),
  • "dispersion": the variance divided by the mean,
  • "observed": a list of m + 1 integers, where entry k is the number of days with exactly k returns (for k = m, that is also the number of days with m or more),
  • "expected": a list of m + 1 floats, the number of days a Poisson distribution with the same mean predicts for each entry of "observed": n · P(K = k) for k < m, and n · P(K >= m) for the last entry,
  • "verdict": "bursty" if the dispersion is above 1 + b, "regular" if it is below 1 - b, and "poisson" otherwise, where b = 2 * sqrt(2 / (n - 1)).

The setup provides daily_counts(kind, n, seed), which returns n simulated days of kind "steady", "bursty" or "regular", so you can try your function with Run.

Examples

Input:  counts = [2, 3, 1, 4, 2, 0, 3, 2, 5, 1]
Output: {"mean": 2.3, "variance": 2.2333333333333334, "dispersion": 0.9710144927536233,
         "observed": [1, 2, 3, 2, 1, 1],
         "expected": [1.0025884372280376, 2.305953405624486, 2.6518464164681586,
                      2.0330822526255883, 1.1690222952597131, 0.8375071927940159],
         "verdict": "poisson"}
Explanation: a Poisson distribution with mean 2.3 predicts 10 · e^-2.3 = 1.0 days with no
returns, 10 · e^-2.3 · 2.3 = 2.3 days with one, and so on; the last entry is 10 · P(K >= 5).
The variance is close to the mean, well inside 1 ± 0.943.

Input:  counts = [0, 0, 7, 1, 0, 9, 0, 2, 0, 1]
Output: dispersion 5.333333333333333, verdict "bursty"
Explanation: same total of 20 returns as a mean of 2 per day, but the variance is 10.67.

Constraints

  • 2 <= len(counts) <= 2000, every count is an integer >= 0, and at least one count is positive
  • floats are compared with a tolerance of 1e-6

Goals

  • Fit a Poisson model to count data by matching its mean
  • Compare observed frequencies with the frequencies a model predicts
  • Use the ratio of variance to mean to tell clumped, random and regular counts apart
Starting Python…