Distribution-Free Comparison When the Data Is Not Normal

Latency measurements are rarely well behaved. The distribution of per-request time is bounded below by the work that must happen, has a dense body, and then a right tail that extends over orders of magnitude when interrupts, queueing, or garbage collection intervene. Some workloads are bimodal because a fast path and a slow path both exist. In that setting the $t$ interval’s assumption of approximate normality for the mean breaks down, and two families of methods take its place: tests based on ranks, and tests based on resampling.

Ranks discard the magnitudes

A rank test replaces each observation with its position in the combined sorted sample and analyses the positions. The Mann–Whitney statistic, equivalently the Wilcoxon rank-sum statistic, is computed from the sum of ranks in one group, and its null distribution is determined by the group sizes alone, with no reference to the shape of the underlying distribution.

Discarding magnitudes buys robustness. A single observation that is a thousand times the median shifts the mean and inflates the $t$ statistic’s variance, but it moves ranks by only one position. That is why the procedures are called distribution-free: their error rate under the null holds regardless of shape, for any continuous distribution.

The cost is a different estimand. The null hypothesis of the rank test is that the two samples come from the same distribution, formally that the probability of a randomly chosen observation from group A exceeding one from group B is one half. This is weaker than equality of means: two distributions can have identical means and different shapes, and the rank test will reject. It is also less specific than equality of medians, which the test only tests when the two distributions are assumed to differ by a shift. Reporting a rank test as evidence that medians differ is a claim the test does not support on its own; the shift assumption must be checked with a plot of the two samples.

Ties break the distribution-free property in the strict sense. With discrete measurements, such as timings quantised to a clock tick, the exact null distribution is no longer available from the rank counts alone, and both the normal approximation with a tie correction and an exact computation over tied configurations are used. Heavily quantised data, where most observations land on a handful of values, is the case where the rank test’s approximation is least reliable.

Exact p-values are coarse in small samples

The null distribution of the rank statistic is a distribution over the $\binom{n_1 + n_2}{n_1}$ ways of splitting the combined ranks into groups, so the exact two-sided p-values are multiples of $2/\binom{n_1+n_2}{n_1}$, which places a floor on how small a p-value the test can produce and coarsens the scale near that floor.

With five runs per arm the combinatorial count is $\binom{10}{5} = 252$. The most extreme arrangement of ranks gives a two-sided p-value of about $0.008$, the next about $0.016$, and the one after that about $0.032$; the following arrangement is already just above the conventional threshold at about $0.056$. A decision at the five percent level is therefore possible, but only from one of the three most extreme orderings of the ten runs. With three runs per arm the count is $\binom{6}{3} = 20$ and the most extreme two-sided p-value is $0.1$, so no result can reach the five percent level. The experiment cannot produce a significant result at that level at all, which is the small-sample version of the power problem described in Power, the Minimum Detectable Effect, and the Cost of Repeated Looks.

Permutation tests generalise the rank idea

A permutation test keeps the observed magnitudes and asks a direct question about the reference distribution: under the hypothesis that the two versions are interchangeable, how often a statistic as extreme as the observed one arises from a random reassignment of labels. The set of all reassignments is that reference distribution, the statistic can be anything, and the procedure is exact for the chosen statistic under the assumption that labels are exchangeable under the null.

The statistic can be the difference of means, which makes the permutation test an exact analogue of the $t$ test without the normality assumption. It can be the difference of medians, which answers a question the $t$ test does not. It can be the difference of a quantile, which no parametric test addresses directly. The randomness of the reference distribution is not the source of uncertainty; the limited number of relabelings is a computational constraint, and when the full set is too large the test samples from it, adding Monte Carlo error that can be made small by drawing more permutations.

Exchangeability is the assumption that matters and the one that paired designs test. If the two versions were run in separate sessions, the labels are confounded with the session, so permuting labels permutes the sessions and the test measures the machine’s variation rather than the code’s. This is the strongest argument for the interleaved designs in Variance Reduction by Pairing, Interleaving, and Blocking: they make the exchangeability assumption plausible rather than heroic.

The bootstrap estimates the estimator’s distribution

The bootstrap treats the sample as an approximation to the population, draws resamples of the same size with replacement, and recomputes the statistic on each. The resulting spread estimates the sampling distribution of the statistic, which is what an interval needs.

For a comparison the resampling unit matters. Resampling each group independently and recomputing the difference gives an interval for the difference of independent samples. Resampling pairs, when the data is paired, preserves the pairing and gives an interval that excludes the block effect, which is the resampling counterpart of the paired $t$ interval.

The percentile interval, taking the appropriate quantiles of the bootstrap distribution, is the simplest construction and the least accurate at the extremes. The bias-corrected and accelerated variant adjusts for median bias and for the skewness of the statistic’s distribution, and is the recommendation when the statistic is a quantile or a ratio. Both are approximations with known failure modes: the percentile interval for a p99 drawn from a few hundred observations piles mass on the top few order statistics and cannot represent a heavier tail than was observed, as discussed in Quantiles from Finite Samples and Their Confidence Bands.

import random

def bootstrap_median_diff(a, b, trials=10000, seed=1):
    """Percentile bootstrap interval for median(b) - median(a), independent groups."""
    rng = random.Random(seed)
    out = []
    for _ in range(trials):
        ra = [a[rng.randrange(len(a))] for _ in a]
        rb = [b[rng.randrange(len(b))] for _ in b]
        out.append(sorted(rb)[len(rb) // 2] - sorted(ra)[len(ra) // 2])
    out.sort()
    return out[int(0.025 * trials)], out[int(0.975 * trials)]

The estimator and the resampling scheme must agree: a bootstrap of the mean of a heavy-tailed distribution converges slowly, because the sample mean’s own distribution is dominated by rare large observations that the resample may or may not contain. A bootstrap of a median or of a trimmed mean is far better behaved, which is another reason those summaries appear in tail-sensitive reporting.

What to do when the methods disagree

Rank and resampling methods frequently disagree with the normal-theory answer on the same data, and the disagreement is informative rather than a reason to choose the more convenient result. When the $t$ test rejects and the rank test does not, the difference is usually carried by a few large observations that the rank test discounts; whether that matters depends on whether total time or typical time is the quantity of interest. When the rank test rejects and the $t$ test does not, the distributions usually differ in shape or spread rather than in location, such as a change that improves the common case and worsens the tail.

The resolution is to report the estimand and its interval from the method that matches it, and to show the distributions. A statement about total cost uses the mean and a mean-based interval; a statement about the typical operation uses the median and a rank or bootstrap interval; a statement about the tail uses a high quantile and a distribution-free interval on it. Claiming all three from one number is the mistake the choice of method is meant to prevent. What remains after the statistics is the question of whether the measured situation resembles the situation the change will face in practice, which is the subject of External Validity and the Limits of What a Benchmark Shows.