Why are two "random" vectors in $\mathbb R^n$ approximately orthogonal for large $n$?

Question

I saw that two random independent vectors are approximately orthogonal in high dimensional space.

How can I prove this? And is there an intuitive explanation?

Thank you.

Answer 1

There are many ways to interpret this question depending on how you "randomly" choose your vectors. Here's one example. Take the set of vectors $v\in\{-1,1\}^N$, where the coordinates of $v$ are chosen independently to be $+1$ half the time and $-1$ half the time. Then an easy calculation shows that the expected value of $$\frac{|v_1\cdot v_2|^2}{|v_1|^2|v_2|^2} \quad\text{is equal to}\quad\frac{1}{N}.$$ In other words, the expected value of $\cos^2\theta$, where $\theta$ is the angle between two randomly chosen vectors in this set, is $\frac{1}{N}$, which shows that randomly chosen vectors are reasonably orthogonal to one another if $N$ is large. One can compute the higher moments $\cos^{2k}\theta$ to get further information. Other random distributions may be computed similarly, for example the set of vectors whose coordinates are independently distributed in the interval $[-1,1]$.

I don't really have a good intuitive explanation, because I have trouble visualizing $N$ dimensional space. (By "intuitive", I'm assuming you mean "geometrically intuitive.")

For those who have voted to close this question, please don't. It does require some clarification to answer carefully, but it is an important principle in, for example, lattice-based cryptography.

Answer 2

The results from a large number of repeated trials can be viewed as a random point in a high-dimensional space, so we can use our intuition about probability in the long run as a substitute for our inability to visualize geometry in high dimensions. The "trend towards the mean" after many repeated trials of the same experiment explains why you should expect such phenomena only in high dimensions. I will focus on the intuition, rather than a rigorous proof, since you asked about both and I think it's good to see why you should expect this type of result before reading a proof about it.

If you flip a fair coin a large number of times you would expect on average to have about as many heads as tails. Assigning "1" to an outcome of heads and "0" to an outcome of tails, for a sequence of $n$ independent coin flips $(x_1,\ldots,x_n)$ where $n$ is large you'd expect the average $(\sum x_i)/n$ to be very close to $1/2$. To recenter the data around $0$ instead of $1/2$, apply the affine transformation $y_i = 2x_i -1$. Then $y_i = 1$ or $-1$ and $(y_1,y_2,\ldots,y_n)$ is a random sequence from $\{\pm 1\}$ with average value $(\sum y_i)/n = 2(\sum x_i)/n - (\sum 1)/n = 2(\sum x_i)/n -1$ very close to $2(1/2) -1 = 0$ when $n$ is very large.

Everything I wrote above goes through if you replace the discrete $x_i$ in $\{0,1\}$ with uniformly chosen $x_i$ in $[0,1]$, so $y_i = 2x_i-1$ becomes a uniform random variable in $[-1,1]$. A vector $(y_1,\ldots,y_n)$ with coordinates chosen randomly (independently and uniformly) in $[-1,1]$ is, for large $n$ (not small $n$ like $2$ or $3$!) very likely to have the average of the coordinates nearly equal to $0$.

Now we make a connection to geometry. The average $(\sum y_i)/n$ can be viewed as the dot product of the vectors $\mathbf y = (y_1,\ldots,y_n)$ and $\mathbf v = (1/n,\ldots,1/n)$, so $\mathbf y \cdot \mathbf v$ is most likely small when $n$ is large. Intuitively you might think "small dot product means they are nearly orthogonal," but the dot product involves the length of the vectors, not only the angle between them, so a dot product might be small because one of the vectors is small. And indeed $\mathbf v$ has length $1/\sqrt{n}$, which tends to $0$ as $n \rightarrow \infty$. Maybe the angle between $\mathbf y$ and $\mathbf v$ doesn't matter? A little algebra will help us focus on the angle instead of the lengths.

Rewrite the dot product $\mathbf y\cdot \mathbf v$ as $(\mathbf y/\sqrt{n})\cdot \mathbf u$ where $\mathbf u = (1/\sqrt{n},\ldots,1/\sqrt{n})$ is a specific unit vector in $\mathbf R^n$. Since $||\mathbf y|| \leq \sqrt{n}$, and equality is certainly possible, the vector $\mathbf y/\sqrt{n}$ is a "random" vector in the unit ball of $\mathbf R^n$. Therefore our probabilistic intuition suggests that a random vector in the unit ball of $\mathbf R^n$ is very likely to have a small dot product with the specific unit vector $\mathbf u$. But geometrically what makes $\mathbf u$ so special? We can transform one unit vector to any other unit vector by a rotation (orthogonal transformation), and rotations do not change distances or dot products, so we are led to expect a random vector in the unit ball of $\mathbf R^n$ and a random unit vector in $\mathbf R^n$ to have a small dot product when $n$ is large. The unit ball and the unit sphere are different objects, but the following claim will let us put them on more of an equal footing in high dimensions.

Claim: most of the unit ball in $\mathbf R^n$ consists of vectors near the boundary when $n$ is large.

To explain the claim pick a small $\varepsilon > 0$ and divide the unit ball in $\mathbf R^n$ into $\{\mathbf w : ||\mathbf w|| \leq 1-\varepsilon\}$ and $\{\mathbf w : 1-\varepsilon < ||\mathbf w|| \leq 1\}$. The second set is all the vectors in the unit ball that are near the boundary and the first set has $n$-dimensional volume $(1-\varepsilon)^nb_n$, where $b_n$ is the volume of the $n$-dimensional unit ball. It turns out that even though the volume $2^n$ of the $n$-dimensional cube $[-1,1]^n$ explodes for large $n$ the unit-ball volume $b_n$ is bounded above as $n$ varies (I don't think this critical fact is intuitive; the value of $b_n$ is maximized at $n = 5$ or $6$ and actually tends to $0$ as $n$ gets large), so for fixed $\varepsilon > 0$ that first set has volume tending to $0$ as $n$ gets large because $(1-\varepsilon)^n \rightarrow 0$ as $n \rightarrow \infty$ no matter how ultra-tiny $\varepsilon$ is (you'd just better not make $\varepsilon$ depend on $n$). Thus, if you pick $\varepsilon$ and then make $n$ big enough, the bulk of the unit ball in $\mathbf R^n$ is in the second set. This completes the justification of the claim (including showing what it really means).

By the claim, in high dimensions a random vector in the unit ball is likely to be near the unit sphere, so we can say that picking a random vector in the unit ball is essentially the same as picking a random unit vector when we are in high dimensions (certainly not in two or three dimensions). We can finally interpret our original intuition that the average $(\sum y_i)/n$ is likely to be near $0$ when $n$ is large as saying that two random unit vectors in $\mathbf R^n$ are likely to have a small dot product, and for unit vectors (or just vectors bounded away from the origin), having a small dot product means the vectors are nearly orthogonal.

Answer 3

Pick two random unit vectors. After picking the first vector, switch to a coordinate system in which this is the first basis vector. The probability distribution for the second vector is assumed to be uniform among all directions, and so should assign an average magnitude of $\approx 1/\sqrt{n}$ to each component, making the dot product between the two vectors $\approx 1/\sqrt{n}$ as well. You have to split up the "total alloted length" of $1$ among increasingly many directions, only one of which counts toward non-orthogonality.

Answer 4

I think there is a stronger statement for large n. If you have n unit vectors (thought of as n points chosen uniformly at random on the sphere in R^n), and put them into the rows of an n x n matrix, the matrix will be nearly orthogonal. So you can choose n vectors at a time, not just 2!

You can test this by filling an n x n matrix with draws from a normal distribution with mean zero and standard deviation 1/sqrt(n). Each row will be approximately unit length, distributed uniformly at random near the sphere, and the whole matrix will be nearly orthogonal.

Answer 5

The key term here is the measure concentration phenomenon, explored in the work of Vitaly Milman and others. This refers to the fact that on a high-dimensional sphere most of the volume is concentrated near the equatorial hemisphere. If one assumes that one's probability distribution is uniform with respect to area, then this phenomenon is equivalent to the statement that a second vector chosen at random will be close to orthogonal to the original one. This is essentially a development of Yemon Choi's comment.

Answer 6

One way to come at this is to try to stretch your intuition even farther, toward the Johnson-Lindenstrauss lemma, which says that while we can only fit $n$ orthogonal vectors into $\mathbb{R}^n$, we can easily (randomly) fit exponentially many almost-orthogonal vectors. The precise statement of the lemma includes the result you mention as a special case, so it's not really fair to say it provides the intuition. Rather I mention it because if you can fit it into your toolbox for thinking about high dimensions it will make other things more intuitive.

Answer 7

I found an intuitive explanation that works for me here. It demonstrates that this effect already starts to happen in as few as three dimensions based on the intuition that the equator is the largest of all latitude lines.