Problem 550593 · hard · Level 05 Advanced Algorithms & Graphs

A Bootstrap Interval That Leans

bootstrap · confidence interval · jackknife · skewed data · normal distribution

A garage wants a 95% interval for the variance of its repair bills, which are skewed: many small jobs and a few very expensive ones. The simple bootstrap percentile interval is known to be too short on the long side for such data. A corrected version moves the two percentile positions, using two numbers estimated from the data. Implement both.

Write leaning_interval(data, stat, reps, seed, level). stat is a function that takes a list and returns a number (the tests pass the setup's mean_of, sample_var or median_of). Follow these steps exactly:

  1. theta = stat(data), n = len(data).
  2. Create rng = random.Random(seed). Make reps resamples one after the other, each with n calls rng.choice(data), and record stat of each. Sort these reps bootstrap values.
  3. Bias correction z0 = Φ⁻¹(q), where q is (the number of bootstrap values < theta, plus half the number == theta) divided by reps, and Φ⁻¹ is the inverse of the standard normal cumulative distribution (statistics.NormalDist().inv_cdf computes it).
  4. Acceleration acc: let t_i = stat(data without its i-th value) for every i, and tbar their mean. Then acc = Σ (tbar - t_i)³ / (6 · (Σ (tbar - t_i)²) ** 1.5), or 0.0 if the denominator is 0.
  5. With tail = (1 - level) / 2, zl = Φ⁻¹(tail) and zu = Φ⁻¹(1 - tail), the corrected probabilities are α1 = Φ(z0 + (z0 + zl) / (1 - acc · (z0 + zl))) and α2 the same with zu, where Φ is the standard normal cumulative distribution.
  6. The bootstrap value "at probability α" is the sorted list's entry at position int(α · (reps - 1) + 0.5).

Return a tuple (theta, z0, acc, (p_low, p_high), (c_low, c_high)): the percentile interval uses the probabilities tail and 1 - tail, the corrected interval uses α1 and α2.

The setup provides mean_of(v), sample_var(v) (dividing by n - 1), median_of(v) and repair_costs(n, seed), a skewed list of n repair bills.

Examples

Input:  data = [3, 1, 4, 1, 5, 9, 2, 6], stat = mean_of, reps = 10, seed = 1, level = 0.8
Output: (3.875, 0.12566134685507413, 0.03937932181342675, (3.0, 4.125), (3.0, 5.125))

Input:  data = [12, 15, 11, 30, 14, 13, 55, 16, 12, 18], stat = sample_var, reps = 2000, seed = 3, level = 0.95
Output: (184.7111111111111, 0.2326927491830447, 0.13882264501534705,
         (3.511111111111111, 401.2111111111111), (28.233333333333334, 482.94444444444446))
Explanation: most resamples miss the bill of 55 at least partly, so the bootstrap
variances pile up below 184.7 (z0 > 0), and one value dominates the jackknife (acc > 0).
Both corrections push the interval up, towards the long tail.

Constraints

  • 3 <= len(data) <= 300, 10 <= reps, len(data) * reps <= 10**5
  • the tests make sure that 0 < q < 1
  • floats are compared with a tolerance of 1e-6; use no randomness other than rng

Goals

  • Build a percentile bootstrap interval for any statistic
  • Measure the bootstrap distribution's median bias and the statistic's skewness with the jackknife
  • Shift the percentile positions to correct for both, using the normal distribution
Starting Python…