如何在一个n维球中获得均匀分布的随机整数点？

Question

如何在d维球内生成均匀随机点？

在这个帖子中，@Thomas Lux提供了一个很好的解决方案，可以生成半径为r=1的n维球内的均匀随机点。但是现在我想生成笛卡尔坐标为整数的点。我不知道除了在立方体中生成随机点并扔掉范数大于1的点之外还有什么方法。

我不知道是否简单地使用randint或将np.floor()推入向量中就可以做到。

- user14554732

---

天真的randint解决方案应该可以工作，但是当D很大时，nD球体积比其边界框的体积慢得多，因此非常低效。np.floor可能不起作用，因为它应该会引入分布偏差（除非您进行一些非平凡的校正，否则不再完全随机）。据我所知，这是一个相当复杂的问题。除此之外，你是指笛卡尔坐标系吗？ - Jérôme Richard

问题是，如果我使用randint来获取向量，在归一化后它将不会是一个整数点。 - user14554732

你是说不能将 1 作为标准吗？ - Davis Herring

正如David所说，假设您不是指范数1（因为在这种情况下，n-球中没有整数点！），您只需要找出哪些整数点落在球体内，并将它们保存在某个列表中。然后，您可以从该列表中随机输出，以获得所需的结果。 - Simon Tartakovksy

@SimonTartakovksy 如前所述，当 D 很大时，这种朴素方法确实不太有效。请参阅 https://en.wikipedia.org/wiki/Volume_of_an_n-ball 了解更多信息。在二维空间中，圆盘占随机二维正方形空间的78%。在三维空间中，它是51%。但在15D中，它只有0.001%，非常小。这意味着100_000个整数中会有99_999个被过滤掉。事实上，所需测试点的数量随着 D 的增加呈指数级增长。当 D>40 时，这种方法甚至无法在合理的时间内（即至少几周）找到一个超球体中的点。 - Jérôme Richard

Answer 1

对于均匀的实数样本，简单地使用round()几乎可以达到目的。但是球边附近的整数点出现的概率会更低。因为在球内采样时，某个点上的超立方体邻居不足一半都被包含在内。

然而有一个简单的解决方法。在一个完全包含所有此类超立方体的球中生成实数样本，半径 r+sqrt(n)/2 应该足够，然后应用四舍五入，最后丢弃距离r之外的整数点。

当然，外球的大小可能比内球大得多，这取决于r和n，但丢弃率应该会更好。

- Karolis Juodelė

---

1. 你有证据证明这在统计上是有效的吗？
2. 主要问题在于随着 n 的增长，外球应该呈指数级增长。这意味着大多数尝试都会失败（请参见我上面的评论）。我想这应该比在超立方体中进行朴素探测好一些，如果球体的半径很大的话。事实上，在半径为 r 的 D-超球体中找到一个点的概率是 (r/(r+1))**D。这意味着只要 r 不小且 D 不是很大，这个解决方案就很好。例如，当 r=5 和 D=15 时，6% 的点将在内部超球体中。当 D=40 时，0.07%。

- Jérôme Richard

@JérômeRichard 1. 如果每个有效整数点周围的超立方体邻域不重叠，具有相等的体积并完全包含在外球中，则从外球均匀采样的样本肯定同等可能地命中其中任何一个。 2. 最终，r=100，n=10和r=10，n=100的情况可能需要不同的算法。不知道OP需要哪种情况。 - Karolis Juodelė

统一性看起来还不错，只要像0.5这样的值随机舍入到最近的整数之一即可。或者，可以添加一个epsilon来修复这个微小的偏差，将其舍入为零。看起来OP已经离开了...对于概率，我犯了一个错误。它是：(r/(r+D**0.5/2))**D。因此，先前的示例分别为0.7％和0.0000003％。D应该很小。当r > O(D**1.5)时，您的解决方案很好。当r相当小时，问题非常难以解决，而D很大（看起来像非线性整数优化）。无论如何，这是一个有趣的解决方案。 - Jérôme Richard

如果r很小而D很大，那么整数坐标几乎都是0，只有少数几组相似的点以多种方式排列。例如，如果r=3，则球中的所有整数点要么是3,0...，要么是2,2,1,0...，要么是2,1,1,1,1,1,0...，要么是1,1,1,1,1,1,1,1,1,0...，或者它们的任何子集，或者带有一些负号。这不是一个巨大的家族，很容易看出每个家族有多大，也很容易从中取样。 - Karolis Juodelė