引言
高维世界并不会在日常生活中接触到，因此用常识去推断和想象高维世界，往往会发生偏差。反过来说，高维世界的很多事实会令人感到惊讶。这种戏剧性的对比，就如同相对论之于低速世界，量子物理之于宏观世界一样。那些钟慢尺缩，薛定谔的猫，其奇异之处都是来自人类的不熟悉。因为人类无法从日常的经验中，建立起这些极限的认识。本质上，人类无法描绘出常识所无法触及的世界，而这些领域里的事实，都只是靠数学的力量，一点点的建立和摸索起来的。这一点上，高维世界，又和量子世界与高速世界不尽相同。后两者的反直觉是来自物理和自然规律，而前者的反直觉则是纯粹来自于数学的推论。这种反直觉，很多时候会造成低维处理问题的办法失效，这也被称为维度的诅咒。
高维空间的一些奇特事实
本节，我们结合一些数值上的实验，来观察一下高维空间中的反直觉的结论。在这之前，我们首先要可以在高维空间进行随机取点，用来数值上的分析。我们将采用两种方案取点，第一种是高维球体的表面1，第二种是高维 hypercube 的内部。事实上，我们也可以取高维球体的内部，但实际上这样做的所有结果都会极其接近球面取点的结果。这就带来了，第一个奇特的事实。
事实1: 高维球的体积几乎都分布在球的表面附近。
这一事实很好得出，只需计算接近球面的球壳体积占整个球体体积的比例即可，可以发现该比例在 \(d\rightarrow\infty\) 时，趋向于1。对于厚度为 \(\delta\) 的球壳，其体积占整个球体的体积比例为 \(1-(1-\delta/R)^d\)。比如对于 1000 维的，半径 1m 的西瓜，如果其皮厚 1cm 的话，那么皮占整个西瓜的体积高达 \(99.9957\%\)。所以应该庆幸生活在低维世界，否则皮再薄，馅也不会大。从取样上来看，也就是说，在高维球面上均匀取样和在高维球体内均匀取样，区别很小。
类似的事实还有：
事实2: 高维立方体的内切球与立方体体积的比例趋向于零。
该事实同样简单，将两者的体积公式一除即可。但这一事实，违背了我们在低维世界的直觉，比如二维时，正方形内切圆的面积是正方形面积的 \(\pi/4=0.785\)，这是一个不小的数字。甚至我们在二维均匀取样单位圆内的点时，还可以用 reject 的方法。即，随机生成 x，y 均在 -1 到 1之间，最后只保留 \(x^2+y^2\leq 1\) 的点。显然这种取样方法，面临维数灾难，在高维并不适用，因为那时的 reject ratio 几乎是百分之百。换句话说，从高维单位立方体中随机取一个点，几乎不可能在单位球内。
我们也不加证明的指出：
事实3: 高维球面上的点，几乎总是处在某个球面赤道的极小邻域内。
这里赤道的含义，是指的和某个坐标轴垂直的“超平面”。事实3更数学化的表达是，选取某个坐标轴 x，记 \(S(a,b)\)，为 \(a<x<b\) 截出的球部分的表面积。可以证明 \(S(\delta R, R)\rightarrow 0\)，而无论 \(\delta\) 有多小。换句话说，球的表面积几乎都是在 \(x=0\) 附近的点贡献的。
取样方案
现在我们讨论一下，为了做数值实验，需要的高维取样方案。对于高维立方体很容易，只需在各个维度都按照 Uniform 分布取值即可。对于球面，则有些 subtle，事实上，需要在各个维度都按照正态分布取值，得到的点在归一化到单位球面即可。而对于球体内的随机取样，则需要在球面取样点的基础上，乘以 \(c^{1/d}\) 重新 scale 一下，其中 c 是均匀分布。这样做的正确性，可以参考本文最后的证明讨论部分。
取样部分本身，还有个很有趣的事实：
事实4: 对于 n+1 维球面上的均匀分布，去掉两个坐标分量之后，自然就是 n 维球体内部的均匀分布2。
该事实的证明见最后一节。
事实5: 无论是立方体（以原点为中心）里的两向量，还是球面（以原点为球心）的两向量，几乎总是正交的。
证明这点的 mathematica 如下
Histogram[
Table[r = Table[RandomVariate[NormalDistribution[]], {i, 1, 20000}];
r = r/Norm[r];
r2 = Table[RandomVariate[NormalDistribution[]], {i, 1, 20000}];
r2 = r2/Norm[r2]; ArcCos[r.r2]/Pi*2*90, {i, 1, 2000}], 50]
其对应的 histogram 为下图，可以看出，随机选取两个向量，则其夹角几乎总是接近 90 度。
关于高维两向量几乎总是正交，可以单纯从代数角度理解。考虑两个长序列，每个数都一半可能为正，那么这两个长序列对应项相乘，每项还是正负各一半的概率。那么把这些项都加起来，很自然的会趋向于0。
事实6: 高维单位球面上任意两点距离几乎总是相等。
这一事实，已经反直觉到了惊天地泣鬼神的程度，怎么可能球面上随便找两个点，距离总是一个常数？但事实如此，验证代码如下。
Histogram[
Table[r = Table[RandomVariate[NormalDistribution[]], {i, 1, 20000}];
r = r/Norm[r];
r2 = Table[RandomVariate[NormalDistribution[]], {i, 1, 20000}];
r2 = r2/Norm[r2]; Norm[r - r2], {i, 1, 2000}], 50]
其对应的 histogram 为下图。可以看出，单位球面上随机取点，两点间的距离几乎总是 \(\sqrt{2}\)，这绝对是无法从低维几何理解的。这也是诸如 kNN 这种靠欧式距离判断近邻的算法，会遭遇高维灾难的原因。
事实7: 对于性质足够好的，以球面上点的坐标为自变量的函数，其函数值在球面上几乎处处相等。
这里不去讨论对函数的具体要求和性质足够好的严格定义。需要指出的是这一事实，几乎就是大数定理的几何版本，也是热力学能够成立的基础。正是在微正则系综的每个允许相点上（高维球面的变形），相关函数的值涨落不大，我们才有了宏观的压强，温度等概念。
Porter-Thomas 分布
对于在 n 维球面上（n+1 维坐标）的随机点，其任意坐标分量的大小 x 满足分布(证明见本文最后一节)
\[P(x)\propto (1-x^2)^{\frac{n}{2}-1}.\]这个分布看起来没什么意思，不过神奇的是，如果考虑两个坐标分量平方和的分布，可以证明（同见后），对于 \(r=x_1^2+x_2^2\)，当维度 n 很大时有
\[P(r)\propto e^{-np/2}.\]这一分布也被称为 PT 分布。有趣的是当不是两个坐标的平方和，而是更多坐标的平方和时，其分布并不再是指数 decay。因此某种意义上，两个坐标的平方和的分布具有一定的特殊地位。我们马上就会看到，这一分布在量子力学中有自然的解释。
量子态的测量结果分布
考虑一个可以遍历希尔伯特空间的量子态 (m bits)，换句话说就是一个 quantum chaotic 的量子态。如果对该态进行测量，那么塌缩到各个测量基 (\(2^m\)) 的概率分布是什么样的？其答案正是 PT 分布。验证随机量子线路输出的态测量结果是 PT 分布，也成为了确定该态可以遍历整个希尔伯特空间，和进一步确立 quantum supremacy 的标准提议3。
我们现在来看其与高维球上取样这一数学问题的联系。对于具有 m 个 qubit，完备基为 \(2^m\) 个的量子态，指定其波函数需要 \(2*2^m\) 个参数，这是因为 amplitude 是复数。同时由于波函数归一化的要求，所谓随机遍历 Hilbert 空间的态，也即对应了 \(2^{m+1}\) 维空间的 \(2^{m+1}-1\) 维球面上的点的取样。而对应每个测量基的测量概率，则为该基上 amplitude 的模方，由于 amplitude 是由一实一虚两个自由度构成，其对应的测量到的概率恰好为 \(x_i^2+{x_{i+1}^2}\) 的概率，这一问题完全映射回了球面上两坐标平方和的分布问题。这时的 PT 分布恰好为
\[P\propto e^{-2^{m+1}/2p}=e^{-np}.\]其中， \(n=2^m\) 为测量基的个数。这一纯几何观点的数学结果，和量子力学给出的 quantum chaotic 态测量结果的分布完全对应。反过来，这也一定程度上昭示了量子理论的终极性和完备性。因为只有在量子理论的 setup 里，我们才会正好得到唯一可以出现指数分布的情况。
一些稍微严格的计算和证明
本节对前面述及的不平凡的事实，进行简单的梳理，并且给出相应的计算和证明。这里的讨论也只是相对严格而已，很多部分并不是完全数学意义上的严格。这部分的理解，可能需要比较充分的微积分和统计知识。
高维球面采样算法
n 维球面上随机取点，等价于取统计独立的 \(x_1,…x_{n+1}\sim N(0,1)\)，再做归一化。
证明：做归一化前，落在某个点的概率密度为 \(f\propto e^{-x_1^2-…-x_{n+1}^2}=e^{-r^2}\)。可以发现这一概率密度只和该点到原点的距离有关，而在各角度方向是均匀的。因此当尝试将所有的取样点到原点的距离归一化之后，自然得就在单位球面上均匀分布。
高维球体采样算法
n 维单位球体上随机取点，等价于如上所述随机取出单位球面上的点后，乘以另一个随机变量 \(c^{1/n}\)，其中 \(c\sim U(0,1)\)。
证明： 在球体中均匀分布的点半径为 r 附近的概率密度，应和 r 处球壳的体积占球体积的比例相协调。球壳体积为 \((r+dr)^n-r^n=nr^{n-1} dr\)。而 \(c^{1/n}\) 的概率分布为
\[P(u)=\frac{1}{(1/n c^{1/n-1})}\vert_{c=u^n}\propto n u^{n-1}.\]此概率分布恰好和球壳体积的比例相匹配。
球面上点的坐标分量分布
n 维球面上点的任意坐标分量的分布为
\[f(x)\propto(1-x^2)^{\frac{n}{2}-1}.\label{cd}\]也即 \(X_1/\sqrt{X_1^2+X_2^2+…X_{n+1}^2}\) 的分布为上式。其中 \(X_i\sim N(0,1)\) 相互独立。
证明：其对应的 mathematica 推导为（忽略积分的各种常数）。其中 \(r=\sqrt{X_1^2+X_2^2+…X_{n+1}^2}\)，x 为目标分布的取值。求导部分是换元出现的 Jacobian。
Assuming[n > 2 && x > 0 && x < 1,
Integrate[
D[x r/Sqrt[1 - x^2], {x}]*r^(n - 1) Exp[-r^2/(1 - x^2)], {r, 0, Infinity}]]
(* 1/2 (1 - x^2)^(-1 + n/2) Gamma[(1 + n)/2] *)
球面上点的坐标分量的平方和分布
设 \(x_{i}\) 服从上述的坐标的分布 \(\eqref{cd}\)，则 \(\sum_{i=1}^k x_i^2\) 的分布，在 \(k=2, n\rightarrow \infty\) 时，服从指数衰减的分布，也即
\[y=x_1^2+x_2^2\sim e^{-ny/2}.\]而当 \(k\neq 2\) 时，分布并非指数分布。
证明：计算对应的概率密度函数积分为 （其中 r 即为目标随机变量 y 的值）
\[I(r,n)=\int_{0}^{2\pi} d\theta\; r (（1-r^2 \sin^2\theta）（1-r^2 \cos^2\theta）)^{n/2-1}=\\2\int_{0}^{\pi} d\theta\; (（1-r \sin^2\theta）（1-r \cos^2\theta）)^{n/2-1}.\]Hopefully, 若我们有
\[\lim_{n\rightarrow \infty} I(r,n) \propto e^{-\frac{n}{2}r},\]则命题得证。下面我们就计算该积分，首先根据替换
\[\lambda^{n/2-1}=\frac{\int_0^\infty x^{-n/2}e^{-\lambda x}dx}{\Gamma(1-n/2)}.\]我们令 \(\lambda = (1-r-r^2/2\sin^2(2\theta))\)，则我们有
\[I(r,n)\propto\int_0^\infty dx x^{-n/2} \int_0^\pi d\theta\;e^{-x(1-r-r^2/2\sin^2(2\theta))}.\]通过 mathematica 计算可得：
\[I(r,n)\propto\pi 2^{3-n} (2-r)^{n-2} \, _2F_1\left(\frac{2-n}{4},1-\frac{n}{4};1;\frac{r^4}{(r-2)^4}\right).\]当 \(n\rightarrow\infty\) 时，可用 mathematica 检验其指数衰减的行为：
FindFit[Table[{x,
Log[2^(3 - n) \[Pi] (2 - r)^(-2 + n)
Hypergeometric2F1[(2 - n)/4, 1 - n/4, 1,
r^4/(-2 + r)^4] /. {n -> 10000, r -> x/10000}]},
{x, 0, 5, 0.2}], a x + b, {a, b}, x]
(* {a -> -0.499962, b -> 1.83793} *)
可以看到其斜率非常接近 \(-0.5\)，符合理论预期。
而对于 k 取非2的值时，可以数值上验证，大于等于三个坐标的平方和，分布概率并不满足指数衰减，甚至其概率密度最大值也不在 0 处。
chi-square 商的分布
设 \(X=\sum_{i=1}^n x_i^2\), \(Y=\sum_{i=n+1}^{n+2}x_i^2\)，且 \(x_i\sim N(0,1)\) 并相互独立。则 \(\frac{X}{X+Y}\) 服从的分布为 \(\beta (\frac{n}{2},1)\)。
\[f(x)\propto x^{\frac{n}{2}-1}.\]证明：其积分推导对应的 mathematica 如下，同样忽略一切常数的细节。其中 \(x=x_{n+1}\)，\(r=\sqrt{\sum_{i=1}^n x_i^2}\)，t 为目标分布的取值。
Assuming[n > 2 && t > 0 && t < 1,
Integrate[
Simplify[D[Sqrt[r^2 (1 - t)/t - x^2], t]] r^(n - 1) Exp[-r^2/t],
{x, 0, Sqrt[r^2 (-1 + 1/t)]}, {r, 0, Infinity}]]
(* -(1/8) \[Pi] t^(-1 + n/2) Gamma[1 + n/2] *)
从 beta 分布到均匀分布
\(X,Y\) 意义同上，则有
\[(\frac{X}{X+Y})^{\frac{n}{2}}\sim U[0,1].\]证明：设 \(u=u(t)=t^{n/2}\)，则分布密度
\[f(u)=f(t)\frac{dt}{du}=\frac{f(t)}{(du/dt)}\vert_{t=u^{-1}(u)}=\frac{t^{n/2-1}}{n/2 ~t^{n/2-1}}\propto 1.\]若已知 c 服从均匀分布，则我们有 \(c^{1/n}\sim \sqrt{\frac{X}{X+Y}}\).
高维球体取样的另一种方案
坐标丢弃方案正确性证明。
随机取样 n+1 维球面 (n+2 个坐标)，任意舍弃两个坐标，剩余的 n 个坐标恰好等价于随机在 n 维球体内部取样。
证明：球面时的分布为 \((x_1,…x_{n+2})/r\), \(r=\sqrt{\sum_{i=1}^{n+2}x_i^2}=X+Y\)。不失一般性，去掉最后两个坐标，分布变为
\[(x_1,...x_n)/r^{\star}(r^{\star}/r)=c^{1/n}(x_1,...x_n)/r^{\star}.\]其中 \(r^\star=\sqrt{\sum_{i=1}^n x_i^2}=X\)，\(c\sim U(0,1)\)。由此可以看出丢掉两个坐标后，剩余的坐标恰好符合球体的均匀分布。