Answers · The mathematics underneath
Why do distances between random points become almost equal in high dimensions?
In shortEach coordinate adds a small independent amount to the squared distance, and many such amounts average out, so typical distances grow while their spread does not keep up.
Distance is built by adding one small contribution per coordinate, and a sum of many independent contributions lands close to its average. So the typical distance between two unrelated points does grow as coordinates are added, but the variation around that typical value does not keep up with it, and by a few hundred coordinates almost every unrelated pair is very nearly the same distance away. Nearest neighbour search still returns something; what it returns is only a few per cent closer than a point picked at random.
Take coordinates drawn independently and uniformly from , so that each has mean and variance . One coordinate of the squared distance between two such points is , and its average is
Squared distance is the sum of of these, one per coordinate, and the terms are independent, so the means add and the variances add. The variance of a single term needs , which for the difference of two uniform coordinates is ; subtracting the square of the mean, , leaves , a little over .
Dividing the standard deviation by the mean gives the spread that actually matters, the one a comparison between distances depends on. In squared distance it is , which is . Distance is the square root of squared distance, and taking a square root halves a relative spread, so distances themselves vary by about .
Set against that, the absolute size of the fluctuations barely moves. The typical distance grows like ; the standard deviation of the distance stays near whatever is. The same wiggle is a shrinking fraction of a growing number, which is why the concentration is a statement about ratios and not about the space becoming smaller.
| coordinates | typical distance | standard deviation of the distance | spread as a fraction |
|---|---|---|---|
| 3 | 1.41 | 0.48 | 34% |
| 30 | 4.47 | 0.48 | 11% |
| 300 | 14.14 | 0.48 | 3.4% |
| 3000 | 44.72 | 0.48 | 1.1% |
Why the natural guess fails
Adding coordinates does push points apart, so the intuition is right about the average and wrong about what a search uses. Every pair gets pushed by roughly the same amount, and a pair only stands out through the imbalance in its contributions. That imbalance is itself a sum of independent terms, so it grows like , while the distance it perturbs grows like ; the ratio falls away. More coordinates therefore make points farther apart and less distinguishable at the same time, and it is the second that bites. The nearest neighbour of a query in three hundred coordinates sits within a few per cent of a randomly chosen point, so a ranking built on distance is reading a very thin signal.
Directions concentrate too
The same arithmetic applies to angles. The cosine of two random directions is a normalised sum of products, and each product has mean zero, so the sum sits near zero. With coordinates uniform on each product has variance , so the sum of of them has standard deviation , while the normalising lengths multiply to about .
At three hundred coordinates that is , an angle of degrees, or a little over three degrees off perpendicular. Two random directions in such a space are very nearly at right angles, which is the geometric restatement of the distance fact: the squared distance between unit vectors is , and a cosine pinned near zero pins the distance near . The good news in the same statement is capacity. Because near-perpendicular directions are cheap, a few hundred coordinates hold far more than a few hundred nearly independent directions, which is what lets a compact vector stand for a distinct notion.
Where the count that matters is not the coordinate count
All of this is stated in the number of independent contributions, not the number of stored coordinates. Coordinates that are strongly correlated, or heavy tailed, or that share a large common component, reduce the effective count and the concentration weakens. Real learned vectors are the standard example: they occupy a narrow cone rather than spreading over the sphere, so two unrelated items already score around rather than near zero, and the gap between related and unrelated narrows to about . The ordering still holds and retrieval still works, but a threshold of means nothing outside the collection it was calibrated on, and a method tuned on low-dimensional data can quietly misbehave here.
Worth keeping
- Typical distance grows like the square root of the number of coordinates, while the spread of distances around that typical value stays roughly constant, so relative variation falls like one over the square root of the number of coordinates.
- Two random directions in a high-dimensional space have a typical cosine of about one over the square root of the number of coordinates, so an unrelated pair scores near zero and sits within a few degrees of perpendicular.
- A distance or similarity threshold means nothing outside the collection it was tuned on, because the ordering of results carries the signal while the absolute numbers do not.
Where this goes next
This question is one step of Vectors, Distance and Similarity, a course that works through its subject from the beginning. The page that teaches this part of it is Where Intuition Stops Working, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- What does a negative dot product tell you about two vectors?A negative dot product means the angle between the vectors is greater than a right angle, so they point broadly apart rather than together.
- Why does cosine similarity ignore how long the vectors are?Cosine similarity compares direction only because dividing by both vector lengths cancels their size exactly, leaving the angle between them.
- Why does Manhattan distance give a different answer from straight-line distance?They measure different things: one is the straight gap, the other is the total along a grid, so they disagree whenever the points differ in more than one coordinate.
- What's the difference between a vector as a point and a vector as a direction?A vector as a point is a location, while a vector as a direction is an arrow from the origin whose length and orientation matter; the same numbers can be read either way.
- What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
- How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.