Mathematical Essays: Notes on the angle between vectors in high dimensional space

• On Mathematics ： Notes on the angles between vectors in high-dimensional space
  • 1. Problem description
  • 2. n Uniform vector in dimensional space
    • 1. 2 D and 3 Special cases in dimensional space
      • 1. 2 Uniform distribution vector in dimensional space
      • 3. 3 Uniform distribution vector in dimensional space
    • 2. n A uniform vector in a dimensional coordinate system
    • 3. Ingenious application of normal distribution
  • 3. n The angle between two vectors in dimensional space
  • 4. summary & reflection

1. Problem description

The story originated in long long ago When I saw sujianlin's blog, I mentioned a conclusion ：

• The probabilities of two random vectors in high dimensional space are orthogonal to each other .

I was concerned about this conclusion at that time , Today, I suddenly thought of this problem , Just want to take advantage of the holiday to verify this conclusion .

obviously , Sujianlin mentioned in his blog that the expression of this conclusion is quite casual , To better define our problem , Let's refine it ：

• about n Two random vectors on the unit sphere in the middle of dimension , The angle between them $\theta$ stay n When taking the larger value , Tend to be 90 degree .

It feels difficult to prove this conclusion , But it is relatively easy to demonstrate this result , Our first reaction is Monte Carlo simulation , Actually generate $N$ Group $n$ Uniform unit vectors in dimensional space , Then look at the angular distribution between them .

however , To do this , We first need to generate n Uniformly distributed unit vectors in dimensional space .

2. n Uniform vector in dimensional space

1. 2 D and 3 Special cases in dimensional space

First , Let's examine some simple cases , namely 2 Peace-keeping 3 The situation in dimensional space .

1. 2 Uniform distribution vector in dimensional space

The uniform distribution vector in two-dimensional space is actually the uniform distribution vector on the unit circle , therefore , We just need to give one $0$ To $\pi$ An angle evenly distributed between $\varphi$ We can get a uniformly distributed unit vector $\vec{v}=(sin\theta ,cos\theta )$.

3. 3 Uniform distribution vector in dimensional space

For the three-dimensional case , In fact, I believe that most readers can easily write solutions if they are familiar with coordinate system transformation .

Our polar coordinates are as follows ：
$$\{\begin{array}{rl}x& =r\cdot sin\theta \cdot sin\varphi \\ y& =r\cdot sin\theta \cdot cos\varphi \\ z& =r\cdot cos\theta \end{array}$$

And then we can get , The expression formula of unit volume element is ：
$$\begin{array}{rl}\rho & =dxdydz\\ & =r^{2}sin\theta drd\theta d\varphi \end{array}$$

You can see , For unit bin , The specific expression is $\rho =C\cdot sin\theta d\theta d\varphi =C^{\prime }\cdot dcos\theta \cdot d\varphi$. therefore , To generate a uniform distribution , We just need to follow $cos\theta$ The distribution of generates a $\theta$, Then generate a $0$ To $2\pi$ Evenly distributed above $\varphi$ that will do .

Give specific python The implementation is as follows ：

import numpy as np

def dummy():
    theta = np.arccos(np.random.uniform(-1, 1))
    phi = np.random.uniform() * 2 * np.pi

    x = np.sin(theta) * np.sin(phi)
    y = np.sin(theta) * np.cos(phi)
    z = np.cos(theta)

    return (x, y, z)

2. n A uniform vector in a dimensional coordinate system

Now? , Let's look at n Cases in dimensional space .

We imitate 3 In the case of dimensional space , Just give the polar coordinate expression of the volume element first , Then the expression of the space angle is examined .

give n The polar coordinate transformation in dimensional space is as follows ：

$$\{\begin{array}{rl}& x_1=r\cdot cos{\theta }_1\\ & x_2=r\cdot sin{\theta }_1\cdot cos{\theta }_2\\ & x_3=r\cdot sin{\theta }_1\cdot sin{\theta }_2\cdot cos{\theta }_3\\ & ...\\ & x_{n-1}=r\cdot sin{\theta }_1\cdot sin{\theta }_2\cdot ...\cdot sin{\theta }_{n-2}\cdot cos{\theta }_{n-1}\\ & x_n=r\cdot sin{\theta }_1\cdot sin{\theta }_2\cdot ...\cdot sin{\theta }_{n-2}\cdot sin{\theta }_{n-1}\end{array}$$

You can get n Volume elements in dimensional space ：
$$\begin{array}{rl}d{x}_{1}d{x}_2...d{x}_n& =\frac{\partial (x_1,x_2,...,x_n)}{\partial (r,{\theta }_1,{\theta }_2,...,{\theta }_{n-1}))}\cdot drd{\theta }_{1}d{\theta }_2...d{\theta }_{n-1}\\ & \\ & =det\left|\begin{array}{cccc}\frac{\partial x_1}{\partial r}& \frac{\partial x_1}{\partial {\theta }_1}& ...& \frac{\partial x_1}{\partial {\theta }_{n-1}}\\ \frac{\partial x_2}{\partial r}& \frac{\partial x_2}{\partial {\theta }_1}& ...& \frac{\partial x_2}{\partial {\theta }_{n-1}}\\ ...& & & \\ \frac{\partial x_n}{\partial r}& \frac{\partial x_n}{\partial {\theta }_1}& ...& \frac{\partial x_n}{\partial {\theta }_{n-1}}\end{array}\right|\cdot drd{\theta }_{1}d{\theta }_2...d{\theta }_{n-1}\\ & \\ & =r^{n-1}si{n}^{n-2}{\theta }_{1}si{n}^{n-3}{\theta }_2...si{n}^2{\theta }_{n-3}sin{\theta }_{n-2}\cdot drd{\theta }_{1}d{\theta }_2...d{\theta }_{n-1}\end{array}$$

thus , We just need to make any ${\theta }_i$ Satisfy the distribution condition $si{n}^{n-1-i}{\theta }_{i}d{\theta }_i$ It's evenly distributed , Then we can get a random vector with uniform spatial angle distribution in the whole space .

Of course , This is not an easy thing to do .

Of course , If you can make $x_i$ yes $(-\infty ,\infty )$ Uniform distribution in range , In fact, the randomly generated vector is also uniform in the space angle , But it is also obviously difficult to achieve .

3. Ingenious application of normal distribution

here , We give a black Technology , That is, although we cannot $(-\infty ,\infty )$ Generate a uniform random distribution in the range , But we can come second , If for a n Dimension vector , Its values in each dimension satisfy the normal distribution $N(0,1)$, So the randomly generated vector is in any n It is also uniformly distributed in the angle of dimensional space .

We examine it at any n The probability density in the volume element of dimensional space is as follows ：

$$\begin{array}{rl}\rho & ={\Pi }_{i=1}^n\frac{1}{\sqrt{2\pi }}{e}^{-\frac{x_i^2}{2}}\\ & =(\frac{1}{\sqrt{2\pi }}{)}^n\cdot e^{{\sum }_{i=1}^n{x}_i^2/2}\\ & =(\frac{1}{\sqrt{2\pi }}{)}^n\cdot e^{r^2/2}\end{array}$$

You can see , The probability density on this space volume element is only related to the radial distance r of , It has nothing to do with the space angle , therefore , Constructed in the above way n The dimension vector is in n The angle of dimensional space is uniformly distributed .

And we normalize it , You can get n Uniformly distributed unit vectors in dimensional space .

We verify the effectiveness of the above method in two-dimensional and three-dimensional space as follows ：

3. n The angle between two vectors in dimensional space

Sum up , We can n Random generation of unit vectors in dimensional space .

that , We can examine the angle and dimension between two random vectors through Monte Carlo generation n The changing relationship between .

The results are shown as follows ：

You can see ：

• For any dimension n, The angle between two random vectors $\theta$ The average value of is 90 degree ;
• With dimensions n An increase in , Angle $\theta$ The distribution of standard deviation decreases gradually , Finally converged to 0, That is, in high-dimensional space , The angle between the two vectors will be very close to 90 degree .

4. summary & reflection

Sum up , This conclusion mentioned by sujianlin in his blog has been proved , It is indeed a very interesting conclusion .