Problem 580844 · easy · Level 05 Advanced Algorithms & Graphs

Eight Study Tips, One Lucky Result?

multiple testing · Bonferroni correction · Holm method · false discovery rate · type I error

A school tried eight study tips, each in its own small experiment, and got one p-value per tip. p_values[i] belongs to tip i. Testing each at alpha finds several "working" tips, but with eight tests some of those may be luck. Compare four ways of deciding which tips to declare effective. Let m = len(p_values).

  • "uncorrected": every tip with p <= alpha.
  • "bonferroni": every tip with p <= alpha / m.
  • "holm": sort the p-values from smallest to largest; go through them in that order and declare the tip at position r (counting from 0) effective while p <= alpha / (m - r); stop at the first one that fails.
  • "bh": sort the p-values from smallest to largest and find the largest rank r (counting from 1) with p_(r) <= r · alpha / m; declare the tips with the r smallest p-values effective (none if there is no such rank).

Write many_tests(p_values, alpha) that returns a dict with these four keys, each mapping to the sorted list of indices of the tips declared effective, plus the key "chance_of_false_alarm": the probability 1 - (1 - alpha) ** m that at least one of m independent tests of useless tips would come out below alpha. When sorting, equal p-values keep their index order.

The setup provides study_p_values(m, real, seed), which returns the p-values of m simulated experiments of which real tips truly work.

Examples

Input:  p_values = [0.003, 0.04, 0.012, 0.3, 0.007, 0.62, 0.021, 0.08], alpha = 0.05
Output: {"uncorrected": [0, 1, 2, 4, 6], "bonferroni": [0], "holm": [0, 4], "bh": [0, 2, 4, 6],
         "chance_of_false_alarm": 0.33657956871093775}
Explanation: Bonferroni needs p <= 0.00625. Holm accepts 0.003 (<= 0.05/8), then 0.007
(<= 0.05/7 = 0.00714), and stops at 0.012 (> 0.05/6). The last rule allows rank 4 with
0.021 <= 4 * 0.05 / 8 = 0.025.

Input:  p_values = [0.2, 0.01, 0.6], alpha = 0.05
Output: {"uncorrected": [1], "bonferroni": [1], "holm": [1], "bh": [1],
         "chance_of_false_alarm": 0.1426250000000001}

Constraints

  • 1 <= len(p_values) <= 10**4, every p in [0, 1], 0 < alpha < 1
  • floats are compared with a tolerance of 1e-6

Goals

  • Compute the chance of at least one false alarm among many tests
  • Apply a family-wise correction, in its simple and its step-down form
  • Apply a step-up rule that controls the share of false discoveries
Starting Python…