Permutation Test for ML: What Null Hypothesis It Tests and What It Does Not Prove

Wake up on white rabbit/

Disclosure: This article was written with AI assistance in structuring and editing. The core concepts, arguments, and code are the author’s work. AI was used for: organizing thoughts through Q&A, suggesting improvements to clarity, and reviewing for logical consistency. All technical claims were verified by the author.

Suppose you have tried several model variants, tuned the parameters, and obtained a good R² on a holdout set. Can you conclude that the model has found a real pattern?

Not necessarily. It is possible that the result is genuinely related to the structure of the data. But it is also possible that the search process itself is so active in trying out variants that it can find a good metric even where there is no signal at all.

In this article, I want to test exactly that. For the experiment, we will take three situations: data with a deliberately planted dependency, pure noise, and two independent random walks. The last case is especially interesting: it will show why a standard permutation test can produce a convincing but incorrect conclusion.

1. The Practical Question

At the moment when the process shows good results, you think you have built a reliable system: the hypothesis holds up, and the metrics look good. But this is exactly where you should start treating the results with suspicion. Permutation testing is needed to try to break this hypothesis, destroy the relationship between the features and the target variable, and check whether the search process itself is fooling us. Are we not training the search to produce the positive result we expect, regardless of what is actually in the data?

Formally, we expect permuted data to produce only noise and low metric values, not signal, not correlation, and not “anything at all.” If the search space and the operations within it still produce a high metric value on permuted data under pure noise, then we have simply drawn a winning lottery ticket. It is the best case out of noise, a signal that got lucky, and in reality it means nothing.

2. The Null Hypothesis (Formally)

In Plain Language

Imagine that you fully trust your workflow: feature selection, model choice, parameter tuning. You run it on real data and get high quality metrics. The question is: are these metrics due to the data or due to the pipeline itself?

The permutation test answers it as follows: we break the relationship between the features and the target values. We take the same X, but shuffle y randomly. Now there is guaranteed to be no dependency between them. Then we run the entire search procedure on this broken data.

If the procedure still produces a high score on noise, we can conclude that it generates “signal” by itself. It sees figures in clouds. And then a high score on real data proves nothing: it is a lottery ticket, not a discovery.
If, on the other hand, the procedure consistently shows a low score on permuted data, then we consider it adequate: it does not see signal where there is none. And then a high score on real data becomes convincing.

Formal Statement

The null hypothesis of the permutation test:

H0H0​: the distribution of the target variable y does not depend on the feature matrix X. The target variable is exchangeable with respect to the sample objects: under the null hypothesis, any permutation of its values is equally likely.

In practice, this means the following: the observed metric value of the procedure Sobs=search_procedure(X,y) is indistinguishable from what the procedure produces on data in which the relationship between X and y has been destroyed by a random permutation.

The p-value is estimated by the Monte Carlo method over B random permutations:

The p-value is estimated by Monte Carlo over B random permutations:

p̂ = (1 + k) / (B + 1)

where k is the number of permutations where the null score ≥ observed score,
and B is the total number of permutations. The +1 correction ensures p̂ > 0
on finite samples.

In code:

exceed = sum(1 for s_null in null_scores if s_null >= s_observed)
p = (exceed + 1) / (n_permutations + 1)

A small p-value means: if there were no relationship, it would be extremely unlikely for the procedure to produce such a high metric on permutations. The null hypothesis is rejected, but this does not prove causality.

Test statistic TT: the R2R2 metric on the holdout set for the candidate with the best R2R2 on the training set among all one-feature and two-feature linear regressions built by search_procedure. Under the null hypothesis, the sample is exchangeable given the features X; a substantially larger observed value of TT compared with the null permutation distribution provides evidence against H0H0​.

Why We Test the Procedure, Not a Single Model

When we train a model, we make many choices before that model appears: which features to select, which to discard, which architecture to try, and other decisions as we see fit. Each of these choices is an opportunity to “peek” into the data and adapt to noise.

If we test only the final model on a holdout set, we check whether this particular model generalizes. But we do not check whether this model itself was chosen by chance, because we tried a hundred variants and took the one that gave the best metric on the test set.
The permutation test wraps the entire search process — from raw data to final metrics. We shuffle y and rerun search_procedure in full: with feature selection, tuning, and splits. If the procedure is honest, it will produce noise on noise. If the procedure is “contaminated” by over-searching or leakage, it will produce a high metric even on permuted data.
That is why in the code we see:

observed = search_procedure(X, y) # observed score on real data
null[b] = search_procedure(X, rng.permutation(y)) # score on broken data

Here we call not model.predict and not model.score, but search_procedure. We are not testing the model. We are testing ourselves.

Below are three scenarios from the code. The first two show the test operating normally: it finds a real signal and catches the illusion of signal in noise. The third demonstrates the limit of the method: a case where the test formally passes, but its conclusion is incorrect.

3. What the Code Shows

Part A: Planted Signal

What we check. We take 120 objects and 6 features. The target is generated as a linear combination of the first two features: y = 3·X₀ − 2·X₁ + ε, where ε is small Gaussian noise. The remaining four features carry no information. This is a control experiment: we know in advance that the signal exists, and we want to make sure that the permutation test can confirm it.

Get Evgeniy V. Dolgov’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Expected result. The search procedure will find the dependency and produce a high metric. On permuted data, this metric value will collapse because the linear relationship between X₀, X₁, and y is destroyed by permutation.

The null distribution will be concentrated around zero (for the metric in our search procedure), around the variance of the target variable for MSE, and around the random guessing level (the share of the most frequent class) for accuracy, while the observed value will be far in the tail.

The resulting p-value will be small: the test confidently rejects H₀. This is normal behavior. The procedure finds what is genuinely present in the data and does not find signal where there is none.

What this shows. The permutation test works as a detector: if there is real structure in the data, the procedure passes the check. We see a high share of the distribution in the tail exactly where there is a clear signal. This is a check of the tool’s adequacy: before applying it to questionable data, you need to make sure it distinguishes signal from noise under ideal conditions.

Part B: Noise + Wide Search

What we check. We take only 60 objects and 12 features. The target is pure Gaussian noise, unrelated to X. There is no signal by construction. But the ratio of few objects to many features creates a wide search space: the procedure tries many feature combinations, and at least one of them will accidentally be “well correlated” with this particular noise. This imitates a typical pipeline where we run selection over a hundred candidates and take the best one.

Expected result. The observed score will look suspiciously high. The procedure will find the “best lottery ticket” among 12 features on 60 objects. But when we shuffle y and run the same search again, the procedure will just as easily find a random combination with a high score. The null distribution will be approximately at the same level as the observed value. The resulting p-value will be large: the test cannot reject H₀, because the procedure “finds signal” equally well in real data and in noise.

What this shows. This is the lottery ticket in its purest form. Wide search turns pure noise into the illusion of signal. The permutation test catches this illusion: it says, “Stop — your procedure will find a high score on any garbage, so your result on real data proves nothing.” This is the main practical scenario for which the test exists.

Nick is dangerous!

killed by steamy Miss America! (^^)

Part C: Spurious Regression (Limitations of the Method)

Now for the catch :) We take two independent random walks: x = cumsum(N(0,1)) and y = cumsum(N(0,1)). There is no relationship between them by construction; they are generated independently. But both series have a trend over time, and a classical regression between two such series produces a high R². This is a textbook example of spurious regression: two trends look related simply because both grow over time.

Expected result. The observed metric value will be high: the model will learn the common trend and show an excellent metric. But when we shuffle y, we destroy its temporal structure: instead of a smooth random walk, we get a “mess” of values without a trend. The model cannot predict this mess from x, and the null metric values will be low. As a result, the observed value will be far from the null distribution, the p-value will be small, and the test will say: “The signal is real; this is not chance.” But the signal is spurious; x and y are independent. The test produces a false-positive result.

What this shows. This is exactly where the permutation test breaks down. It checks whether the found pattern is random, but it does not check whether it is causal. Spurious regression is not noise at all; it is a real mathematical structure in the data. Permuting the labels destroys this structure, so the test cannot distinguish “both series grow because of a hidden common cause” from “both series grow randomly and independently.” The permutation test assumes exchangeability of observations, and non-stationary series violate this assumption. The test will honestly confirm that the pattern is not random, but it will miss the fact that the pattern is useless for prediction. This is a case of forcing a mathematical relationship onto the data: the relationship exists, but there is no predictive power — like fitting a square peg into a round hole.

Run the Code

# Clone the repository
git clone https://github.com/sensus-stoa/permutation-test-ml.git
cd permutation-test-ml

# Install dependencies
pip install -r requirements.txt
# Run the test
python src/permutation_test.py

Seed is fixed: SEED=7. Runtime: a few seconds.

4. Limitations

1. It does not test a ready-made model. Here we test the statistical significance of a hypothesis, not of already trained models.
2. It produces false-positive results on non-stationary data. The test formally runs, but its conclusion is incorrect: permutation destroys the temporal structure, and the test interprets spurious regression as a real signal.
3. It says nothing about causation.
4. It is sensitive only to the dependence that the search procedure is capable of capturing. If the procedure looks for a linear relationship, the test will not detect a nonlinear one.

5. What I Did Not Test

1. I did not test block permutation or other methods that preserve the autocorrelation structure during shuffling and potentially produce correct results on non-stationary data.
2. The search procedure was tested only on synthetic data from this script. No validation was performed on real production datasets or real working pipelines.
3. Only linear dependencies that the search procedure can capture were tested (one-feature and two-feature linear regressions).
4. Only 200 permutations were tested — no more, no less.
   With 200 permutations, the minimum achievable p-value is ≈ 1/201 ≈ 0.005. If you need to distinguish p = 0.001 from p = 0.0001, 200 permutations are not enough.
5. The Type I error rate across repeated runs (e.g., repeated independent runs under pure noise) was not measured in this article. The script experiments/repeated_runs.py in the repository provides this measurement.

Code and Reproducibility

All code is available at: https://github.com/sensus-stoa/permutation-test-ml

• Clean run by one documented command: python src/permutation_test.py
• Versions of data, code, and dependencies are frozen in requirements.txt
• Numbers are reconciled with code and reproducible with fixed seed SEED=7

Charts: Tyler Vigen, tylervigen.com (Spurious Correlations). Underlying data: CDC, IMDb, Wikipedia.