algorithm - 如何在 d 维球/球体内生成均匀的随机点？

Question

我环顾四周，所有用于在单位球内/上生成均匀随机点的解决方案都是为 2 维或 3 维设计的。

什么是(易处理的)在任意维度内部生成均匀随机点的方法？特别是，不仅仅是在表面上球的。

作为序言，在立方体中生成随机点并丢弃范数大于 1 的点在高维中不可行。单位球的体积与高维单位立方体的体积之比变为 0。即使在 10 维中，单位立方体中也只有大约 0.25% 的随机点也在单位球内。

Answer 1

在 d 维球中生成均匀分布的随机点的最佳方法似乎是考虑极坐标(方向而不是位置)。 下面提供了代码。

1. 在均匀分布的单位球上随机选取一个点。
2. 选择一个随机半径，其中半径的可能性对应于具有 d 维度的半径的球的表面积。

此选择过程将 (1) 使所有方向的可能性相同，并且 (2) 使单位球内球表面上的所有点的可能性相同。这将在球的整个内部生成我们想要的均匀随机分布。

随机选择一个方向(在单位球上)

为了实现 (1)，我们可以从归一化到单位长度的高斯分布的 d 独立抽取中随机生成一个向量。 This works因为高斯分布有一个指数为 x^2 的概率分布函数 (PDF)。这意味着联合分布(对于独立随机变量，这是它们的 PDF 的乘积)将在指数中具有 (x_1^2 + x_2^2 + ... + x_d^2)。请注意，这类似于 d 维球体的定义，这意味着来自高斯分布的 d 独立样本的联合分布对于旋转是不变的(矢量在球体上是均匀的)。

这是在 2D 中生成的 200 个随机点的样子。

---

选择一个随机半径(以适当的概率)

为了实现 (2)，我们可以使用累积分布函数 (CDF) 的倒数生成半径，该函数对应于 d 维度的球的表面积，半径为 r。我们知道 surface area of an n-ball与 r^d 成正比，这意味着我们可以在 [0,1] 范围内将其用作 CDF。现在通过将 [0,1] 范围内的随机数映射到逆 r^(1/d) 来生成随机样本。

这是 x^2(二维)的 CDF 的视觉效果，[0,1] 中随机生成的数字将映射到相应的 x坐标在这条曲线上。 (例如 .1 ➞ .317)

---

上面的代码

最后，这是一些计算上述所有内容的 Python 代码(假设您安装了 NumPy)。

# Generate "num_points" random points in "dimension" that have uniform
# probability over the unit ball scaled by "radius" (length of points
# are in range [0, "radius"]).
def random_ball(num_points, dimension, radius=1):
    from numpy import random, linalg
    # First generate random directions by normalizing the length of a
    # vector of random-normal values (these distribute evenly on ball).
    random_directions = random.normal(size=(dimension,num_points))
    random_directions /= linalg.norm(random_directions, axis=0)
    # Second generate a random radius with probability proportional to
    # the surface area of a ball with a given radius.
    random_radii = random.random(num_points) ** (1/dimension)
    # Return the list of random (direction & length) points.
    return radius * (random_directions * random_radii).T

为了后代，这里是使用上述代码生成的 5000 个随机点的视觉效果。