# Statistical significance of difference between distances

I have over 3000 vectors on a two-dimensional grid, with an approximately uniform discrete distribution. Some pairs of vectors fulfil a certain condition. Note: the condition is only applicable to pairs of vectors, not to individual vectors. I have a list of about 1500 such pairs, let's call it group 1. Group 2 contains all other vector pairs. I want to find out if the distance between vectors in a pair in group 1 is significantly smaller the average distance between two vectors. How can I do that?

Statistical test: Is the central limit theorem applicable to my case? That is, can I take means of samples of distances and use Student's t-test to compare means of samples that fulfil the condition with means of samples that don't fulfil the condition? Otherwise, what statistical test would be appropriate here?

Sample size and the number of samples: I understand that there are two variables here, for each of the two groups I need to take n samples of the size m and take the average of each of the samples. Is there any principled way to choose n and m? Should they be as large as possible? Or should they be as little as possible, as long as they show the statistical significance? Should they be the same for each of the two groups? Or should they be larger for group 2, which is contains many more vector pairs?

• Normally people aren't so lucky as to have definite boundaries for their data points--or else the boundaries are complicated. This, along with the correlations among distances (created by the triangle inequality), precludes developing a nice analytical expression for the sampling distribution of mean distances. Therefore they typically estimate the sampling distributions of mean distances by resampling from the data. – whuber Nov 21 '16 at 0:00
• @whuber I'm not sure if I understand you correctly, are you suggesting that I take n samples from each of the two groups, and use the t-test to compare means of those samples? I edited my question, I hope it's clearer now. – michau Nov 21 '16 at 15:21

The question of "significantly" different always, always presupposes a statistical model for the data. This answer proposes one of the most general models that is consistent with the minimal information provided in the question. In short, it will work in a wide array of cases, but it might not always be the most powerful way to detect a difference.

Three aspects of the data truly matter: the shape of the space occupied by the points; the distribution of the points within that space; and the graph formed by the point-pairs having the "condition"--which I will call the "treatment" group. By "graph" I mean the pattern of points and interconnections implied by the point-pairs in the treatment group. For instance, ten point-pairs ("edges") of the graph could involve up to 20 distinct points or as few as five points. In the former case no two edges share a common point, whereas in the latter case edges consist of all possible pairs between five points.

To determine whether the mean distance among edges in the treatment group is "significant," we may consider a random process in which all $n=3000$ points are randomly permuted by a permutation $\sigma$. This permutes the edges, too: the edge $(v_i, v_j)$ is replaced by $(v_{\sigma(i)}, v_{\sigma(j)})$. The null hypothesis is that the treatment group of edges arises as one of these $3000!\approx 10^{21024}$ permutations. If so, its mean distance should be comparable to the mean distances appearing in those permutations. We may fairly easily estimate the distribution of those random mean distances by sampling a few thousand of all those permutations.

(It is noteworthy that this approach will work, with only minor modifications, with any distance or indeed any quantity whatsoever associated with every possible point pair. It will also work for any summary of the distances, not just the mean.)

To illustrate, here are two situations involving $n=100$ points and $28$ edges in a treatment group. In the top row the first points in each edge were randomly chosen from the $100$ points and then the second points of each edge were independently and randomly chosen from the $100-1$ points different from their first point. All together $39$ points are involved in these $28$ edges.

In the bottom row, eight of the $100$ points were chosen randomly. The $28$ edges consist of all possible pairs of them.

The histograms at the right show the sampling distributions for $10000$ random permutations of the configurations. The actual mean distances for the data are marked with vertical dashed red lines. Both means are consistent with the sampling distributions: neither lies far to the right or left.

The sampling distributions differ: although on average the mean distances are the same, the variation in mean distance is greater in the second case due to the graphical interdependencies among the edges. This is one reason no simple version of the Central Limit Theorem can be used: computing the standard deviation of this distribution is difficult.

Here are results comparable to the data described in the question: $n=3000$ points are approximately uniformly distributed within a square and $1500$ of their pairs are in the treatment group. The calculations took only a few seconds, demonstrating their practicability.

The pairs in the top row again were chosen randomly. In the bottom row, all the edges in the treatment group use only the $56$ points closest to the bottom left corner. Their mean distance is so much smaller than the sampling distribution that this can be taken as statistically significant.

Generally, the proportion of mean distances from both the simulation and the treatment group that are equal to or greater than the mean distance in the treatment group can be taken as the p-value of this nonparametric permutation test.

This is the R code used to create the illustrations.

n.vectors <- 3000
n.condition <- 1500
d <- 2              # Dimension of the space
n.sim <- 1e4        # Number of iterations
set.seed(17)
par(mfrow=c(2, 2))
#
# Construct a dataset like the actual one.
#
# m indexes the pairs of vectors with a "condition."
# x contains the coordinates of all vectors.
x <- matrix(runif(d*n.vectors), nrow=d)
x <- x[, order(x[1, ]+x[2, ])]
#
# Create two kinds of conditions and analyze each.
#
for (independent in c(TRUE, FALSE)) {
if (independent) {
i <- sample.int(n.vectors, n.condition)
j <- sample.int(n.vectors-1, n.condition)
j <- (i + j - 1) %% n.condition + 1
m <- cbind(i,j)
} else {
u <- floor(sqrt(2*n.condition))
v <- ceiling(2*n.condition/u)
m <- as.matrix(expand.grid(1:u, 1:v))
m <- m[m[,1] < m[,2], ]
}
#
# Plot the configuration.
#
plot(t(x), pch=19, cex=0.5, col="Gray", asp=1, bty="n",
main="The Data", xlab="X", ylab="Y",
sub=paste(length(unique(as.vector(m))), "points"))
invisible(apply(m, 1, function(i) lines(t(x[, i]), col="#80000040")))
points(t(x[, unique(as.vector(m))]), pch=16, col="Red", cex=0.6)
#
# Precompute all distances between all points.
#
distances <- sapply(1:n.vectors, function(i) sqrt(colSums((x-x[,i])^2)))
#
# Compute the mean distance in any set of pairs.
#
mean.distance <- function(m, distances)
mean(distances[m])
#
# Sample from the points using the same *pattern* in the "condition."
# m is a two-column array pairing indexes between 1 and n inclusive.
sample.graph <- function(m, n) {
n.permuted <- sample.int(n, n)
cbind(n.permuted[m[,1]], n.permuted[m[,2]])
}
#
# Simulate the sampling distribution of mean distances for randomly chosen
# subsets of a specified size.
#
system.time(
sim <- replicate(n.sim, mean.distance(sample.graph(m, n.vectors), distances))
stat <- mean.distance(m, distances)
p.value <- 2 * min(mean(c(sim, stat) <= stat), mean(c(sim, stat) >= stat))

hist(sim, freq=FALSE,
sub=paste("p-value:", signif(p.value, ceiling(log10(length(sim))/2)+1)),
main="Histogram of mean distances", xlab="Distance")
abline(v = stat, lwd=2, lty=3, col="Red")
}

• Thanks a lot! That's what I was looking for. But would you mind clarifying how the p-value should be computed? I don't understand the formulation "the proportion of mean distances from both the simulation and the treatment group that are equal to or greater than the mean distance in the treatment group". You're talking about proportion of two mean distances and one of them is "mean distances from [...] the treatment group that are equal or greater to the mean distance in the treatment group". I'm confused, it sounds like a tautology. Could you write a formula or R code to make it clearer? – michau Nov 24 '16 at 15:37
• In any case, it turns out that my case is similar to your second example, mean distances of permutations are around 22 with the standard deviation around 0.3, and the mean of the treatment group is 12. So it looks like a clear indication that the difference is statistically significant. The only thing I'm struggling with now is the estimation of the p-value. In fact, even with a fairly large sample of permutations (10000), all the means without exception are in a fairly narrow interval, let's say [21, 23]. Is this something I can use to estimate the p-value? – michau Nov 24 '16 at 15:41
• OK, I've read a bit about Monte Carlo permutation tests now. According to my understanding: if means of all the 10000 permutations that I've tried are higher than the treatment group mean, I can conclude that p < 0.0001. Is it as simple as that? – michau Nov 24 '16 at 16:46
• Yes, it is that simple! I added code at the end to compute and display a two-tailed p-value (which, arguably, is the appropriate one for your situation). For a one-tailed p-value, use either mean(c(sim, stat) <= stat) or mean(c(sim, stat) >= stat) as appropriate. – whuber Nov 25 '16 at 10:22
• Great! The situation with the one-tailed test is perfectly clear now, but I still don't understand the two-tailed test, particularly the multiplication by 2. If 10000 permutations gave me means in the range [21, 23], doesn't it mean that both 12 and 32 are outside the 99.99% confidence interval, which corresponds to p < 0.0001? Shouldn't I simply count mean distances that are as far as stat from the middle of the distribution, in either direction? Something like p.value <- mean(abs(c(sim, stat)-mean(sim)) >= abs(stat-mean(sim))). – michau Nov 26 '16 at 18:58