Suppose we sample a set $S$ of $n$ points from a $d$-dimensional spherical (unit variance) Gaussian with $d \approx 100$. It is known that any point of the sample would be roughly at $\sqrt{d}$ distance away from the center with high probability. Let $c$ denote the center of the Gaussian.

Let us choose any point $p$ from the sample, and let $T$ denote the set of $t$ closest points of $p$ in $S$. We observe that $||c-\text{mean}(T)|| \ll \sqrt{d}$. What would be the reason for mean$(T)$ to be much closer to the center than any random point of the sample? Any help is appreciated.

Assume $n$ to be in millions and $t$ be of the order of hundreds.

  • $\begingroup$ (1) Does "whp" mean "with high probability"? (2) "$\ll$" is meaningless and often false. To make it meaningful you need to compare the left hand side to the right hand side relative to $n$ and $t$. $\endgroup$
    – whuber
    Sep 20, 2016 at 15:34
  • 1
    $\begingroup$ Edited the question to clarify. For (1), yes. For (2), assume n to be in millions and t to be in hundreds. $\endgroup$
    – anup
    Sep 21, 2016 at 4:04

2 Answers 2


This is a question about high-dimensional Euclidean geometry, related to the "curse of dimensionality". It comes down to this: almost all the surface area of a sphere in $d$-dimensional Euclidean space $E^d$ is concentrated around its equator. The nearest neighbors of any point will tend to be scattered in random directions around its equator, so their average will be near its center--which is the center of the sphere itself.

The rest of this post explains why this is, provides an estimate for how much the distance shrinks, and presents a simulation (in $100$ dimensions) to support the conclusions.

There's a nice statistical demonstration of this equatorial concentration lemma. Given that the squared radii of the points are concentrated around $d$ (a consequence of their $\chi^2(d)$ distribution), which places them close to a sphere of radius $\sqrt{d}$, we need only consider the angles made between the nearest neighbors with the original point. For each such angle $\theta$, use $(\cos(\theta)+1)/2$ to measure its size. This value decreases from $1$ with close neighbors, through $1/2$ at the equator, down to $0$ for diametrically opposite points. It has a Beta$((d-1)/2,(d-1)/2)$ distribution.

I don't want to presume too much knowledge of Beta distributions, because little is actually needed. Here is an elementary way to reason about this particular distribution. Its mean is $1/2$--on average all the remaining points are halfway between a given point and its opposite--and its variance is $1/(4d)$. Its spread, as measured by the standard deviation, therefore is $1/(2\sqrt{d})$. Chebyshev's Inequality states that for any $k\ge 1$, at most $1/k^2$ of the probability lies beyond $k/(2\sqrt{d})$ of the equator. That's all we need to know.

Fixing the number of points $n$ and the number of nearest neighbors $t$, choose $k$ so large that $t/n$ is substantially greater than $1/k$: a small multiple of $n/t$ will do. As $d$ grows, the value $k/(2\sqrt{d})$ shrinks down to zero. Therefore most of the $t$ nearest neighbors of any chosen point will be close to the equator.

With this geometric result in mind, the answer is now obvious. The nearest neighbors of any given point will be scattered randomly near the equator within limited distances of the equator relative to that point. The cylindrical symmetry of the situation around the point's axis indicates that on average those neighbors will be almost directly beneath the north pole. Thus we expect this average of the neighbors to be much nearer the origin than the original point itself, which is close to $\sqrt{d}$.

That's more or less a heuristic argument but we can obtain quantitative results, too. We may freely rotate the coordinate system so that the original point is "up," because a rotation changes neither the distances nor the probability distribution of the points. The height, in particular, has a standard Normal distribution. The average of the $t$ largest out of $n$ independent heights will be close to the average of their expectations and less than the expected maximum height. An approximation for that expected maximum is $\Phi^{-1}(1-1/(n+1))$ where $\Phi$ is the standard Normal distribution function. At the same time, each coordinate of the average is the average of $t$ standard Normal variables. The first $n-1$ of these coordinates are approximately independent of the last and their averages have Normal distributions with zero mean and variance of $1/t$. The sum of their squares consequently is approximately a multiple of a $\chi^2(d-1)$ distribution, with a mean of $(d-1)/t$. Therefore the squared distance of this average is expected to be near $$h(n,d)=(d-1)/t + \Phi^{-1}(1-1/(n+1))^2$$ and likely a little bit less. This is a reasonable estimate when $t$ is small compared to $n$; it becomes a gross overestimate as $t$ grows.

We may explore this situation via simulation, using (a) the $\chi^2(d)$ distribution of all squared distances as one reference and (b) this estimate $h(n,d)$ as another reference. Here, for instance, is a histogram of the lengths of the mean of $t=9$ nearest neighbors for $n=10^4$ points in $d=100$ dimensions. To standardize the comparison (which helps when varying $d$), all distances have been divided by $\sqrt{d}$, thereby bringing the points close to the unit sphere.


The blue curve is the standardized $\chi^2(100)$ density. The vertical dashed red line is the (over)estimate of the typical distance between the average of the nine nearest neighbors and the center of the sphere. The histogram displays the simulated data, which are based on $10$ independent sets of points and $50$ randomly selected points out of each of those sets.

That the histogram is situated close to, but a little less than, the vertical red line supports the preceding quantitative analysis. That both are substantially less than $1$ supports the statement in the question itself.

For those who would like to experiment, here is the R code to produce similar situations. Take care when increasing any of the inputs, because the calculations can take a long time.

n <- 1e4    # Number of points
m <- 50     # Subset size
k <- 9      # Number of nearest points
d <- 100    # Dimension
n.sim <- 10 # Number of trials

sim.raw <- replicate(n.sim, {
  x <- matrix(rnorm((n+1)*d), d)
  sapply (sample.int(n+1, m), function(i) {
    distance.2 <- colSums((x - x[, i])^2)
    q <- x[, order(distance.2)[1:k + 1], drop=FALSE]
    q.mean <- rowMeans(q)
sim <- sqrt(sim.raw / d)

h <- sqrt((qnorm(1/(n+1))^2 + (d-1)/k)/d) # Overestimate of the mean
hist(sim, xlim=range(c(sim, h, 0, 1 + 2*sqrt(d-1)/d)), freq=FALSE,
     xlab=paste("Length of standardized mean of", k, "nearest neighbors"),
     main=paste("n =", n, "points in d =", d, "dimensions"),
     sub=paste(n.sim, "trials using", m, "points per trial"), cex.sub=0.8)
abline(v=h, col="Red", lty=3, lwd=2)
abline(v=mean(sim), col="Gray", lwd=2)

curve(2 * x * dchisq(x^2*d, df=d) * d, add=TRUE, col="Blue")
  • $\begingroup$ Thanks a lot for your answer. May be I am lacking some basics, would you please elaborate (or references) why nearest neighbors will be scattered randomly near the equator. $\endgroup$
    – anup
    Sep 24, 2016 at 9:33
  • 1
    $\begingroup$ That's exactly what is demonstrated in the argument leading up to the reference to Chebyshev's inequality. I'll see whether I can clarify that. $\endgroup$
    – whuber
    Sep 24, 2016 at 14:42
  • $\begingroup$ Two clarifications: For each angle \theta, why do you say that estimated size to be (cos(\theta)+1)/2. Secondly, why approximation for expected maximum is \phi^(-1)(1-1/(n+1)). Thanks. $\endgroup$
    – anup
    Sep 25, 2016 at 12:42
  • 1
    $\begingroup$ $(\cos(\theta)+1)/2 = \sin^2(\pi/2-\theta/2)$ is proportional to the squared angle that $\theta$ makes with the equator. It therefore is an excellent measure of how far from the equator that angle is. A search of our site provides detailed information and derivations concerning your second question: see, for instance, stats.stackexchange.com/questions/9001. $\endgroup$
    – whuber
    Sep 26, 2016 at 13:42
  • 1

First of all, a comment on the question: Points in the sample $S$ won't be at $\sqrt{d}$ distance away from the center. Distance squared will follow a $\chi^2$ distribution with $d$ degrees of freedom and therefore with $d$ mean and $2d$ variance. Then, distance will be distributed around $\sqrt{d}$ but there is not a concentration of points in the $\sqrt{d}$ radius shell.

And for the question itself, I don't see how you observe that $||c-\text{mean}(T)|| << \sqrt{d}$, and in fact $||c-\text{mean}(T)||$ depends a lot on how has been $T$ selected. I'll comment two extreme cases:

  • If $T$ is much smaller than $S$: $T$ (the $t$ points closer to $p$) are likely to be very close to $p$ and therefore distribution of $\text{mean}(T)$ will be very close to the distribution of $p$, and $||c-\text{mean}(T)||^2$ will approximately follow a $\chi^2$ distribution with $d$ degrees of freedom and therefore with $d$ mean and $2d$ variance, just like distance of $c$ to $p$.
  • If $T$ is nearly as large than $S$: Then $T$ is approximately a random sample from the d-dimensional spherical (unit variance) Gaussian distribution. When finding $\text{mean}(T)$, for each dimension we are averaging $t$ points from a normal distribution, and in the whole we get a d-dimensional spherical Gaussian distribution with $1/t$ variance, and $t·||c-\text{mean}(T)||^2$ will follow a $\chi^2$ distribution with $d$ degrees of freedom. Mean of $||c-\text{mean}(T)||^2$ will be $d/t$ and variance $2d/t$. Then $||c-\text{mean}(T)||$ will be distributed around $\sqrt{d/t}$, and for larger $t$ it will be much smaller than $\sqrt{d}$.
  • $\begingroup$ You are right about the distance of any random point of the sample from the center. Of the two cases you have mentioned above, I am looking for Case 1, say n=|S| in millions and t in hundreds. Yes, it is not clear why mean(T) should be much closer to the center c, but that is what we observed. $\endgroup$
    – anup
    Sep 21, 2016 at 4:09
  • $\begingroup$ What do yo mean by "we observed"? Have you run a simulation? Have you done some maths? Without more details we can't give hints about why you observed that. $\endgroup$
    – Pere
    Sep 21, 2016 at 8:52
  • $\begingroup$ By the way: In more than one dimension, mean of distances of points in a sample should be larger than distance to mean of points, as shown by extreme cases, but if all points in the sample are close this effect should be small. $\endgroup$
    – Pere
    Sep 21, 2016 at 9:04
  • $\begingroup$ Yes, we ran simulations where we observed this event. $\endgroup$
    – anup
    Sep 21, 2016 at 15:40
  • $\begingroup$ Since the closest t points to p would be correlated, it is not clear how to compute the distribution of average of these points $\endgroup$
    – anup
    Sep 23, 2016 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.