# Permutation test on dependent data

Say that I have a sample of observations which are pairs of real numbers $$(x_i, y_i)$$. Pairs are i.i.d., but $$x_i$$ and $$y_i$$ are not independent. I want to test whether the mean of $$x$$ is equal to the mean of $$y$$ using a permutation test. I know that the correct way to do it is with a paired permutation test. But what happens if I insist on using a regular permutation test? Does the p-value become incorrect? Or does it affect only the power of the test?

What if the pairs are also not independent, e.g. from a time series? In that case even a paired permutation test would fail to reproduce the correlations in the sample. However the mean is permutation invariant, so I'm not sure that it would matter. Would the p-value be incorrect in this case?

• The paired test and two-sample test address different questions. The paired test is a one-sample test on the differences, not on the original data. What do you want to test?
– Dave
Sep 22, 2021 at 16:37
• I want to test whether the mean of x is equal to the mean of y. Since the mean of the differences is equal to the difference of the means, it's the same as testing whether the mean of the differences is zero, which is what you are saying. Sep 22, 2021 at 16:54
• Permutation tests rely on the things that are permuted being exchangeable rather than independent, assuming you have a suitable statistic. What is your proposed statistic? Sep 23, 2021 at 0:21
• The test statistic would be the difference of the means $\bar{y}-\bar{x}$, or equivalently, the mean of the differences $\bar{d}$, $d_i = y_i - x_i$. Sep 23, 2021 at 13:50

The null hypothesis for the paired permutation test is that $$x_i$$ and $$y_i$$ can be freely exchanged. That is, if $$p(x, y)$$ is the joint probability (density) of $$x_i$$ and $$y_i$$, then the null hypothesis is that $$p$$ is symmetric: $$p(x, y) = p(y, x)$$.
This condition implies that the mean of $$x$$ is equal to the mean of $$y$$, but the converse is not necessarily true. So the null hypothesis of the paired permutation test is more specific than the one I initially envisioned.
Replicates generated by the paired permutation tests are composed of pairs $$(x_i, y_i)$$ or $$(y_i, x_i)$$. A regular permutation test will instead shuffle $$(x_1, y_1, x_2, y_2, ...)$$ and form new pairs, so the typical replicate pair will be $$(x_i, y_j)$$ or $$(y_j, x_j)$$ with $$i\ne j$$. Therefore, if $$x$$ and $$y$$ are positively correlated, the typical pair under the paired permutation test will have a smaller difference $$|x - y|$$ than the typical pair under the regular permutation test. Consequently the regular permutation test will have a lower probability of rejecting the null hypothesis than the paired permutation test, i.e. it will yield an incorrect p-value.