# Is the permutation test p-value valid for a distance metric?

I have two variables, $X \in \mathbb{R}^n$ and $Y \in \mathbb{R}^n$. Let $d$ be a distance metric that satisfies the conditions to be such a metric (non-negativity, symmetry, triangle inequality and identity of indiscernibles).

Let $t_0 = d(X,Y)$. That is, $t_0$ is the distance between my two vectors of data. I want to compute a p-value to figure out how significant the distance is in either direction.

For this I want to use a permutation test by re-ordering $Y$, calculating its distance to $X$ and repeating this many times in order to build the distribution of distances under the null hypothesis. I can then calculate the p-value for $t_0$ from this distribution.

My question is whether this is valid or not? If not, then why not? If it is, then why? What is it about an estimator (distance in this case) that makes it valid to use a permutation test as a significance test?

• What's the null hypothesis, and what is exchangeable under it? – Glen_b Mar 6 '17 at 19:06
• The null hypothesis is that there is no relationship between X and Y. But in reality X contains n entries sampled from some distribution F, and $Y=X+Z$, where Z is sampled from a different distribution G. The observed distance between X and Y is small, and I want to see how small it is in the distribution of distances between X and Y if there were no relationship between the two – Patrick Mar 7 '17 at 23:42
• In this situation, what is the correct way of saying what is exchangeable under the null hypothesis? Would you say "the labels Y corresponding to X are exchangeable"? – Patrick Mar 7 '17 at 23:52
• Thanks for the clarification. You could express it that way. I don't see any obvious problem with doing what you're trying to do, but there's enough not detailed here that there might perhaps be some lurking issue. – Glen_b Mar 8 '17 at 1:09