Permutation test on dependent data

Question

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?

Answer 1

Glen_b's comment was illuminating, so let me try to answer.

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.

Now to answer what happens when the regular permutation test is used to test this hypothesis, instead of the paired permutation test.

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.