Why Step-Down Max-T Testing?
A genomic analysis may test thousands of features whose test statistics are correlated. A single-step max-T procedure calibrates every feature against the largest statistic in the entire family. This controls familywise error under suitable conditions, but the same stringent reference distribution is used even for hypotheses that are less extreme. The Westfall–Young step-down max-T procedure retains the joint permutation calibration while progressively removing the most extreme hypotheses from the set used to calculate later permutation maxima.
The result is a separate adjusted p-value for each hypothesis. The procedure can be more powerful than single-step max-T because, at later steps, it takes a maximum over fewer hypotheses. Its error-control guarantee depends on valid permutations and conditions such as subset pivotality; it is not a general correction that works regardless of the data-generating design.
Assumptions and the Algorithm
The procedure starts from a valid permutation scheme for the design. Under the relevant null hypothesis, the allowed transformations must leave the data or errors exchangeable in the way required by that scheme. In paired or blocked data, for example, permutations must respect the pairing or blocks. Each permutation must be applied jointly across the features, so the reference distribution preserves their dependence. Permuting each feature independently would generally destroy that dependence and would not reproduce the joint maximum distribution.
For strong familywise error control, a central condition is subset pivotality: the joint distribution of the test statistics for any subset of true null hypotheses does not depend on which other hypotheses are false. In addition, the permutation calibration must correctly represent the joint null distribution for those statistics. These conditions let a permutation distribution constructed under the complete null provide valid, potentially conservative calibration when only a subset of null hypotheses is true.
The steps below use two-sided statistics, so evidence is measured by absolute value. For a one-sided test, use statistics oriented so that larger values always indicate stronger evidence, and omit the absolute-value signs. The observed ordering is fixed throughout the permutation calculation: each permuted statistic remains attached to its original hypothesis label.
Sort \(|T_j|\) from largest to smallest and record the hypothesis labels in that order. Ties may be ordered by a prespecified rule; tied statistics should be treated consistently.
At rank \(k\), for each permutation replicate, take the maximum absolute statistic among the hypotheses in \(R_k\), the hypotheses not yet passed in the ordered list.
Compare each replicate maximum with \(S_{(k)}\). With \(B\) randomly sampled permutations and \(r_k\) exceedances, use \(\tilde p_{(k)}=(r_k+1)/(B+1)\). The added one accounts for the observed arrangement and avoids a zero Monte Carlo p-value.
Set \(p^{\mathrm{adj}}_{(k)}=\max_{\ell\le k}\tilde p_{(\ell)}\). These adjusted p-values cannot decrease as the observed statistics become less extreme. Map each value back to its hypothesis label.
If all valid transformations are enumerated, the exact permutation p-value is the fraction of the full reference set whose maximum is at least the observed statistic, with the observed arrangement included in that set. The plus-one expression above is for Monte Carlo sampling. When using a finite random sample, the reported values also have Monte Carlo uncertainty; more permutations improve their numerical resolution.
Worked Example: Calculating Step-Down Adjusted P-Values
Suppose three hypothetical genomic features have observed two-sided statistics \(T_A=3.1\), \(T_B=-2.4\), and \(T_C=1.8\). Their ordered absolute statistics are \(S_{(1)}=3.1\) for A, \(S_{(2)}=2.4\) for B, and \(S_{(3)}=1.8\) for C. The following table gives eight randomly sampled valid permutation replicates. The table entries are absolute statistics, kept in the original feature order.
| Replicate | A | B | C |
|---|---|---|---|
| 1 | 3.4 | 1.2 | 0.8 |
| 2 | 2.8 | 2.6 | 1.0 |
| 3 | 2.0 | 2.1 | 2.0 |
| 4 | 1.5 | 1.7 | 1.9 |
| 5 | 1.4 | 2.3 | 1.4 |
| 6 | 3.0 | 1.0 | 1.2 |
| 7 | 1.1 | 2.5 | 1.6 |
| 8 | 1.3 | 1.9 | 2.2 |
At rank 1, the maximum is over A, B, and C. Only replicate 1 has a maximum at least 3.1: its maximum is 3.4. Thus \(r_1=1\) and \(\tilde p_{(1)}=(1+1)/(8+1)=2/9\approx0.222\).
At rank 2, the maximum is over B and C and is compared with 2.4. Replicates 2 and 7 exceed or equal 2.4, so \(r_2=2\) and \(\tilde p_{(2)}=(2+1)/9=3/9\approx0.333\).
At rank 3, only C remains, and its permuted absolute statistic is compared with 1.8. Replicates 3, 4, and 8 meet or exceed 1.8, so \(r_3=3\) and \(\tilde p_{(3)}=(3+1)/9=4/9\approx0.444\). These stage p-values are already nondecreasing, so the adjusted p-values are \(0.222\) for A, \(0.333\) for B, and \(0.444\) for C. They are dimensionless p-values, not effect sizes.
Why the Adjustment Is Monotone
The stage p-values are computed from different reference maxima and need not be nondecreasing in every finite permutation sample. The adjusted values use the running maximum to ensure that a less extreme observed statistic cannot receive a smaller adjusted p-value than a more extreme one. This is also the step-down logic: a hypothesis at rank \(k\) cannot be declared significant unless it and every more extreme hypothesis have passed their corresponding stages.
The familywise error rate (FWER) is the probability of rejecting at least one true null hypothesis in the family. To see why the step-down construction can control this rate, let \(I\) be the set of true null hypotheses. If any true null is rejected, consider the first true null reached in the ordered testing sequence, at rank \(k\). The remaining set \(R_k\) contains every true null that has not already been considered, including that first true null. In particular, the maximum over the true null statistics in the remaining set cannot exceed the maximum over all of \(R_k\).
Under subset pivotality, the joint distribution of the true-null statistics is the same as it would be under their joint null. The permutation calibration for the remaining-set maximum therefore gives a valid, and potentially conservative, bound for the chance that a true null at that stage crosses its threshold. If the procedure uses valid level-\(\alpha\) tests for the successive intersection hypotheses, the probability of reaching and rejecting a true null is at most \(\alpha\). This yields strong FWER control: control holds when any subset of the family is null, not only when all hypotheses are null. The argument depends on valid calibration and subset pivotality; it does not establish those conditions for a particular study design.
Worked Example: Comparing with Single-Step Max-T
Use the same hypothetical permutation table. Single-step max-T uses the maximum over all three features for every hypothesis. For feature B, compare that full-family maximum with \(2.4\). Replicates 1, 2, 6, and 7 have a full-family maximum at least \(2.4\), so its Monte Carlo adjusted p-value is \((4+1)/9=5/9\approx0.556\). The step-down value for B was \(3/9\approx0.333\), because at B’s step the maximum is taken only over B and C.
For C, the single-step comparison uses the full-family maximum against \(1.8\). All eight replicates have a full-family maximum at least \(1.8\), giving \((8+1)/9=1.000\). The step-down value for C is \(4/9\approx0.444\), using C alone at the final step. For A, both procedures use the maximum over all features at the first step, so both give \(2/9\approx0.222\). This illustrates the potential gain for later-ranked hypotheses; it does not guarantee that step-down testing will always produce smaller p-values in every dataset or at every rank.
Worked Example: Enforcing Monotonicity with Monte Carlo Counts
Suppose four hypothetical features have ordered observed absolute statistics \(4.2, 3.1, 2.7,\) and \(2.0\). In \(B=999\) valid Monte Carlo permutations, suppose the respective numbers of exceedances for the remaining-set maxima are \(7,4,6,\) and \(29\). These counts need not increase at every step because both the observed cutoff and the remaining set change.
The stage p-values are \((7+1)/1000=0.008\), \((4+1)/1000=0.005\), \((6+1)/1000=0.007\), and \((29+1)/1000=0.030\). Taking the running maximum gives adjusted p-values \(0.008, 0.008, 0.008,\) and \(0.030\). At significance level \(\alpha=0.01\), the first three hypotheses are rejected and the fourth is not. This conclusion uses adjusted p-values, not the uncorrected stage values: the second and third hypotheses do not get to use a value below the earlier stage’s \(0.008\).
Diagnostics, Alternatives, and Limitations
Before interpreting the adjusted p-values, check the permutation design and the computation. The permutations must respect the experimental units and any restrictions in the design, and the same transformation must be used across features to preserve their joint dependence. Confirm that the observed ordering is by the intended statistic, that each stage maximum includes exactly the remaining hypotheses, and that exceedances use a consistent \(\ge\) rule. Ties at an observed threshold count as exceedances. A useful numerical check is that the final adjusted p-values are nondecreasing down the ranked list and lie between zero and one.
The main alternatives answer related but different needs:
| Procedure | Calibration | Main consideration |
|---|---|---|
| Single-step max-T | Uses the maximum over the full family for every feature | Simple joint calibration; may be more conservative for less extreme features |
| Step-down max-T | Uses maxima over successively smaller remaining sets | Can gain power by using the observed ordering and dependence structure |
| Bonferroni or Holm | Uses marginal p-values and a family-size-based adjustment | Does not require permutation calibration of the joint dependence, but may not exploit it as effectively |
Step-down max-T is not automatically more powerful than every alternative under every configuration. Its advantage is most relevant when the permutation scheme is valid, the joint distribution is informative, and the family has dependence that a joint maximum can use. If exchangeability is implausible, if the permutation unit is wrong, or if subset pivotality fails, the stated strong-control guarantee may fail. A large number of tests does not repair a misspecified permutation scheme.
With Monte Carlo permutations, adjusted p-values have finite simulation precision. If a decision depends on a value near \(\alpha\), increase the number of permutations and assess the resulting Monte Carlo uncertainty rather than treating a noisy estimate as exact. Also report the testing family and the permutation restrictions: an adjusted p-value applies to the specified family and reference scheme, not automatically to every feature or analysis that could have been tested.
Common Pitfall
A common error is to sort the statistics separately within every permutation and then treat the largest permuted statistic as the reference for every observed rank. That is single-step calibration, not step-down calibration. At rank \(k\), the procedure must take the maximum over the fixed set of hypotheses remaining after the observed ordering, \(R_k\), while retaining each permuted statistic’s feature label. Re-sorting can change the set being compared from replicate to replicate and no longer implements the stated step-down algorithm.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- For two-sided testing, how should hypotheses be ordered, and what quantity is compared with the observed statistic at rank \(k\)?
- At a step, 19 of 999 Monte Carlo permutation maxima meet or exceed the observed statistic. What is the stage p-value?
- Three successive stage p-values are \(0.04, 0.02,\) and \(0.07\). What are the adjusted p-values?
- Why should one shared permutation be applied across all features rather than permuting each feature independently?
- What condition helps extend complete-null permutation calibration to strong familywise control when only some hypotheses are true nulls?
Solutions. (1) Order by decreasing absolute observed statistic. At rank \(k\), compare \(S_{(k)}\) with the permutation maximum over the fixed remaining set \(R_k\). (2) The stage p-value is \((19+1)/(999+1)=0.020\). (3) The running maxima are \(0.04\), \(\max(0.04,0.02)=0.04\), and \(\max(0.04,0.02,0.07)=0.07\), so the adjusted values are \(0.04,0.04,0.07\). (4) Shared permutations preserve the dependence among feature statistics that determines the distribution of their joint maximum; independent feature-wise permutations generally destroy it. (5) Subset pivotality, together with valid permutation calibration, supports strong familywise control.