The distribution of the angle between two random vectors in n-dimensional space

n维空间下两个随机向量的夹角分布 苏剑林 · 2019-11-13 · Mathematics probability analysis

Yesterday there was a discussion in the group about some counterintuitive phenomena of $n$-dimensional vectors, one of which was "in a general $n$-dimensional space, two random vectors are almost always perpendicular" — which clearly conflicts with our intuition built from 2D/3D space. To understand this result theoretically, we can look at the distribution of the angle $\theta$ between two random vectors and work out its mean and variance.

Probability density

First, let's derive the probability density function of $\theta$. Actually, there's not much derivation needed — it's a direct consequence of $n$-dimensional hyperspherical coordinates.

To find the distribution of the angle between two random vectors, it's clear that, by isotropy, we only need to consider unit vectors, and again by isotropy, we only need to fix one of the vectors and let the other vary randomly. Without loss of generality, let the random vector be

\begin{equation}\boldsymbol{x}=(x_1,x_2,\dots,x_n)\end{equation}

and let the fixed vector be

\begin{equation}\boldsymbol{y}=(1,0,\dots,0)\end{equation}

Transform $\boldsymbol{x}$ into hyperspherical coordinates (for background on $n$-dimensional spheres, see Wikipedia):

\begin{equation} \left\{\begin{aligned} x_{1}&=\cos(\varphi_{1})\\ x_{2}&=\sin(\varphi_{1})\cos(\varphi_{2})\\ x_{3}&=\sin(\varphi_{1})\sin(\varphi_{2})\cos(\varphi_{3})\\ &\,\,\vdots \\ x_{n-1}&=\sin(\varphi_{1})\cdots \sin(\varphi_{n-2})\cos(\varphi_{n-1})\\ x_{n}&=\sin(\varphi_{1})\cdots \sin(\varphi_{n-2})\sin(\varphi_{n-1}) \end{aligned}\right. \end{equation}

where $\varphi_{n−1}\in [0, 2\pi)$, and the remaining $\varphi$ range over $[0, \pi]$. At this point, the angle between $\boldsymbol{x}$ and $\boldsymbol{y}$ is:

\begin{equation}\arccos \langle \boldsymbol{x},\boldsymbol{y}\rangle = \arccos \cos(\varphi_{1}) = \varphi_{1} \end{equation}

That is, the angle between the two is exactly $\varphi_1$. So the probability that the angle between $\boldsymbol{x}$ and $\boldsymbol{y}$ does not exceed $\theta$ is:

\begin{equation}P_n(\varphi_1\leq\theta) = \frac{n\text{on hypersphere in dim}\varphi_1\text{no more than}\theta\text{integral of}}{n\text{full integral over hypersphere in dim}} \end{equation}

And the surface area element on the $n$-dimensional hypersphere is $\sin^{n-2}(\varphi_{1})\sin^{n-3}(\varphi_{2})\cdots \sin(\varphi_{n-2})\,d\varphi_{1}\,d\varphi_{2}\cdots d\varphi_{n-1}$ (which can be found on Wikipedia), so

\begin{equation}\begin{aligned} P_n(\varphi_1\leq\theta) =& \frac{\int_0^{2\pi}\cdots\int_0^{\pi}\int_0^{\theta}\sin^{n-2}(\varphi_{1})\sin^{n-3}(\varphi_{2})\cdots \sin(\varphi_{n-2})\,d\varphi_{1}\,d\varphi_{2}\cdots d\varphi_{n-1}}{\int_0^{2\pi}\cdots\int_0^{\pi}\int_0^{\pi}\sin^{n-2}(\varphi_{1})\sin^{n-3}(\varphi_{2})\cdots \sin(\varphi_{n-2})\,d\varphi_{1}\,d\varphi_{2}\cdots d\varphi_{n-1}}\\ =&\frac{(n-1)\text{surface area of unit hypersphere in dim}\times\int_0^{\theta}\sin^{n-2}\varphi_{1} d\varphi_1}{n\text{surface area of unit hypersphere in dim}}\\ =&\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)\sqrt{\pi}} \int_0^{\theta}\sin^{n-2}\varphi_1 d\varphi_1 \end{aligned} \end{equation}

This shows that the probability density function of $\theta$ is

\begin{equation} p_n(\theta) = \frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)\sqrt{\pi}}\sin^{n-2} \theta \label{eq:theta}\end{equation}

Sometimes we're interested in the distribution of $\eta=\cos\theta$, in which case we need to do a change of variables in the probability density:

\begin{equation}\begin{aligned} p_n(\eta)=&\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)\sqrt{\pi}}\sin^{n-2} (\arccos\eta)\left|\frac{d\theta}{d\eta}\right|\\ =&\frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)\sqrt{\pi}}(1-\eta^2)^{(n-3)/2}\\ \end{aligned}\label{eq:cos}\end{equation}

Distribution behavior

From $\eqref{eq:theta}$ and $\eqref{eq:cos}$ we can see that when $n=2$, the angle $\theta$ is uniformly distributed, while when $n=3$, the cosine of the angle $\cos\theta$ is uniformly distributed. These two results tell us that in the 2D and 3D spaces we can perceive directly, the angle is distributed fairly evenly. But what happens when $n$ becomes large, say $n=20,50$?

From the form of $p_n(\theta)\sim\sin^{n-2}\theta$, we can see that when $n\geq 3$, the maximum probability occurs at $\theta=\frac{\pi}{2}$ (i.e., 90 degrees), and moreover $\sin^{n-2}\theta$ is symmetric about $\theta=\frac{\pi}{2}$, so its mean is also $\frac{\pi}{2}$. But this still doesn't fully describe the distribution — we also need to look at the variance:

\begin{equation} Var_n(\theta) = \frac{\Gamma\left(\frac{n}{2}\right)}{\Gamma\left(\frac{n-1}{2}\right)\sqrt{\pi}}\int_0^{\pi}\left(\theta-\frac{\pi}{2}\right)^2\sin^{n-2} \theta d\theta\end{equation}

This integral has a closed-form solution, but it's quite unwieldy (readers who enjoy this kind of thing can work it out themselves with Mathematica), so let's just look at some numerical values instead:

$$\begin{array}{c|c} \hline n & \text{variance}\\ \hline 3 & 0.467401\\ 10 & 0.110661\\ 20 & 0.0525832\\ 50 & 0.0204053\\ 100 & 0.0101007\\ 200 & 0.00502508\\ 1000 & 0.001001\\ \hline \end{array}$$

We can see that as $n$ increases, the variance keeps shrinking, which means that in high-dimensional space, the angle between any two vectors is almost always concentrated near $\frac{\pi}{2}$. In other words, any two vectors in a high-dimensional space are almost always perpendicular.

Of course, this can also be seen visually:

Plot of p(θ)

For readers who want an approximate closed-form solution, one option is Laplace's method: approximate $p_n(\theta)$ with a Gaussian distribution by expanding $\ln \sin^{n-2}\theta$ around $\theta=\frac{\pi}{2}$:
\begin{equation}\ln \sin^{n-2}\theta=\frac{2-n}{2}\left(\theta - \frac{\pi}{2}\right)^2 + \mathcal{O}\left(\left(\theta - \frac{\pi}{2}\right)^4\right)\end{equation}
that is,
\begin{equation}\sin^{n-2}\theta\approx \exp\left[-\frac{n-2}{2}\left(\theta - \frac{\pi}{2}\right)^2\right]\end{equation}
From this approximate form, we can roughly say that $\theta$ follows a normal distribution with mean $\frac{\pi}{2}$ and variance $\frac{1}{n-2}$, i.e., when $n$ is large, the variance is approximately $\frac{1}{n-2}$ — which again shows that the larger $n$ is, the smaller the variance becomes.

Summary

This post derives the distribution of the angle in high-dimensional space, recorded here for future reference and for the benefit of any readers who might find it useful.