}

团队最近在技术选型时对比了多个方案，这里分享一下我们的调研结果和最终决策依据。

style="display:

xmlns="http://www.w3.org/2000/svg">

d="M5,0

style="-webkit-tap-highlight-color:

rgba(0,

高维数据变得非常重要。

然而，高维空间与我们熟悉的二维和三维空间有很大不同。

在d维空间中随机生成n个点，每个坐标都是均值为零、方差为1的高斯分布。

当d足够大时，所有点对之间的距离以高概率基本上相同。

此外，d维单位球（即所有满足|x|≤1的点x的集合）的体积随着维度的增加而趋近于零。

高维单位球的体积集中在它的表面附近，也集中在它的赤道附近。

这些性质具有重要的影响，我们将对此进行考虑。

如果在d维空间中使用高斯分布生成随机点的坐标，当d很大时，所有点对之间的距离将基本上相同。

原因是两点y和z之间距离的平方：

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/8954835570f0400e8293edec96b03b25.png#pic_center">

这是d个独立随机变量的总和。

如果对一个具有有界方差的随机变量x进行n次独立抽样并取平均值，结果将接近x的期望值。

在上述求和中，有d个样本，每个样本是两点y和z在某一坐标上的平方距离。

这里我们给出一个称为大数定律的一般性界。

具体来说，大数定律指出:

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/530c5c5d2ddf4d95b99c4f91c3fb6184.png#pic_center">

随机变量的方差越大，误差超过某个值的概率就越大。

因此，x的方差位于分子。

样本数量n位于分母，因为平均的数值越多，差异超过某个值的概率就越小。

同样，该值越大，差异超过某个值的概率就越小，因此该值位于分母。

请注意，平方运算使该分数成为一个无量纲量。

我们使用两个不等式来证明大数定律。

第一个是马尔可夫不等式，它指出非负随机变量超过a的概率受该变量的期望值除以a的限制。

三、证明大数定律

id="31__14">3.1

src="https://i-blog.csdnimg.cn/direct/f5034a17f07c4aeaa5f325457894a8bb.png#pic_center">
证明：对于一个连续的非负随机变量x，其概率密度为p，

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/c9152a1b16624111b1a57295c59f48e9.png#pic_center">
因此，

class="katex">

class="katex-mathml">Prob(x≥a)≤E(x)/aProb(x

E(x)/a

mathnormal">a。

对于离散型随机变量，同样的证明适用于求和而非积分的情况。

推论

2.2

class="katex-mathml">Prob(x≥bE(x))≤1/bProb

bE(x)

mathnormal">b

马尔可夫不等式仅利用分布的均值信息来界分布的尾部。

通过同时使用随机变量的方差，可以获得更紧的界。

优化建议：

如果你的项目访问量较大，建议增加缓存机制。

我们团队在优化后，接口响应时间从800ms降到了50ms，

效果非常明显。

具体的缓存策略可以根据业务场景调整。

id="32__25">3.2

src="https://i-blog.csdnimg.cn/direct/e70d1cb902144bf882a85a4df027e3c2.png#pic_center">
证明：

class="katex">

class="katex-mathml">Prob(∣x−E(x)∣≥c)=Prob(∣x−E(x)∣2≥c2)Prob(|x−E(x)|

Prob(|x−E(x)|²

mtight">2

class="mspace"

mtight">2

class="mclose">)

class="katex-mathml">y=∣x−E(x)∣2y

class="base">

mtight">2。

注意到

class="katex-mathml">E(y)=Var(x)E(y)

Var(x)

class="mclose">)，因此可以应用马尔可夫不等式得出：

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/18484a2aeb574b1bb4ba0ffe843465b0.png#pic_center">
大数定律源于切比雪夫不等式以及关于独立随机变量的事实。

回想一下：

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/0fd6d2dcd42f4c3da744dcad89b7a6c3.png#pic_center">

此外，如果x和y相互独立，那么

class="katex-mathml">E(xy)=E(x)E(y)E(xy)

E(x)E(y)

class="mclose">)。

这些事实意味着，如果x和y相互独立，那么

class="katex">

class="katex-mathml">Var(x+y)=Var(x)+Var(y)Var(x

Var(x)

class="mclose">)，具体推导如下：

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/521307ee1aa94b108298595e8c64a74e.png#pic_center">

我们利用独立性将E(2xy)替换为2E(x)E(y)。

id="33__36">3.3

定理2.4（大数定律）设x₁,x₂,…,xₙ是随机变量x的n个独立样本。

则

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/65a86e320628419c8fd182ef6b0b4fdc.png#pic_center">

证明：根据切比雪夫不等式

src="https://i-blog.csdnimg.cn/direct/7862e79ca3bf488ca84bcd982383c364.png#pic_center">
大数定律具有很强的普遍性，适用于任何方差有限的随机变量x。

稍后我们将研究球面高斯分布以及0-1取值随机变量之和的更紧致的集中界。

作为大数定律的一个应用，设z是一个d维随机点，其坐标均从均值为零、方差为1/(2π)的高斯分布中选取。

我们将方差设为1/(2π)，使得该高斯概率密度在原点处等于1，并且在整个单位球内都由一个常数下界。

根据大数定律，z到原点的距离的平方以高概率为Θ(d)。

特别地，这样的随机点z落在单位球内的概率微乎其微。

这意味着概率密度在单位球上的积分也必须微乎其微。

另一方面，单位球内的概率密度有一个常数下界。

因此，我们可以得出结论：单位球的体积必须微乎其微。

同样，如果我们从一个d维高斯分布中选取两个点y和z，该分布的每个方向方差均为1，那么|y|²≈d，|z|²≈d，且|y−z|²≈2d（因为对所有i，E(yi−zi)²=E(yi²)+E(zi²)−2E(yizi)=2）。

因此，根据勾股定理，这些随机的d维向量y和z必须近似正交。

这意味着，如果我们把这些随机点缩放为单位长度，并将y称为北极点，那么单位球的大部分表面积必须位于赤道附近。

我们将在后续章节中对这些及相关论证进行形式化处理。

我们现在陈述一个关于独立随机变量之和的概率尾界的一般定理。

伯努利分布、平方高斯分布和幂律分布随机变量之和的尾界都可以由此推导得出。

下表总结了一些结果。

定理

class="katex-mathml">x=x1+x2+⋅⋅⋅+xnx

···

mtight">1

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">2

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">n

class="vlist-s">​

class="vlist"

class="">，其中

class="katex-mathml">x1,x2,...,xnx₁,

x₂,

mtight">1

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">2

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">n

class="vlist-s">​

class="vlist"

class="">

class="katex-mathml">σ2σ²

class="base">

mtight">2。

令

class="katex-mathml">0≤a≤(2nσ2)0

class="base">

class="mord">2

class=""

c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,-10,-9.5,-14

c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54

c44.2,-33.3,65.8,-50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10

s173,378,173,378c0.7,0,35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429

c69,-144,104.5,-217.7,106.5,-221

H400000v40H845.2724

s-225.272,467,-225.272,467s-235,486,-235,486c-2.7,4.7,-9,7,-19,7

c-6,0,-10,-1,-12,-3s-194,-422,-194,-422s-65,47,-65,47z

M834

80h400000v40h-400000z">

class="vlist-s">​

class="vlist"

class="">

class="mord

mtight">2

class="mclose">)。

假设对于

class="katex-mathml">s=3,4,...,(a2/(4nσ2))s

...,

mtight">2

class="mord

mtight">2

class="mclose">))，有

class="katex-mathml">∣E[xis]∣≤σ2/s!|E[xᵢˢ]|

σ²/s!

mtight">i

class=""

mtight">s

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">2

class="mord

class="mclose">!。

则，

alt="在这里插入图片描述"

src="https://i-blog.csdnimg.cn/direct/23ee0ea3a899413fbd4a08d32f5a7120.png#pic_center">

定理12.5的初等证明见附录。

为了获得简要的直观理解，考虑将马尔可夫不等式应用于随机变量

class="katex">

class="katex-mathml">xrx^r

class="base">

0.0278em">r，其中r是一个较大的偶数。

由于r是偶数，

class="katex">

class="katex-mathml">xrx^r

class="base">

0.0278em">r是非负的，因此

class="katex">

class="katex-mathml">Prob(∣x∣≥a)=Prob(xr≥ar)≤E(xr)/arProb(|x|

Prob(x^{r}

0.0278em">r

class="mspace"

0.0278em">r

class="mspace"

0.0278em">r

class="mord">

0.0278em">r。

如果

class="katex">

class="katex-mathml">E(xr)E(x^r)

class="base">

0.0278em">r

class="mclose">)不太大，我们就能得到一个较好的界。

为了计算

class="katex">

class="katex-mathml">E(xr)E(x^r)

class="base">

0.0278em">r

class="mclose">)，将E(x)写成

class="katex">

class="katex-mathml">E(x1+...+xn)rE(x₁

...

mtight">1

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">n

class="vlist-s">​

class="vlist"

class="">

class="mclose">

0.0278em">r，并将多项式展开为其各项。

利用独立性这一事实：

class="katex">

class="katex-mathml">E(xirxjr)=E(xir)E(xjr)E(xᵢʳᵢ

xⱼʳⱼ)

mtight">i

class=""

0.0278em">r

class="vlist-s">​

class="vlist"

class="">

class="mord">

0.0572em">j

class=""

0.0278em">r

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">i

class=""

0.0278em">r

class="vlist-s">​

class="vlist"

class="">

class="mord

0.0572em">j

class=""

0.0278em">r

class="vlist-s">​

class="vlist"

class="">

class="mclose">)，从而得到一组更简单的期望，这些期望可以利用我们的假设

class="katex">

class="katex-mathml">∣E(xsi)∣≤σ2s!|E(xₛᵢ)|

σ²s!

mtight">i

class="vlist-s">​

class="vlist"

class="">

class="mspace"

mtight">2

class="mord

class="mclose">!来进行界估计。

完整的证明见附录。