python - 该算法是否在单位圆盘上生成均匀分布(确定性 RNG)？

Question

考虑以下算法:

r = 2
while r >= 1:
    x = -1 + 2 * random.random()
    y = -1 + 2 * random.random()
    r = x * x + y * y

现在，如果我的研究是正确的，python 的随机模块使用系统时间作为初始种子(让我们认为这是均匀分布的)，然后使用 mersenne twister algorithm 生成确定的数字序列。每次调用random.random()将产生介于 0(含)和 1(不含)之间的数字。

当算法终止时，点 (x,y)应该在单位光盘上的某个地方。由于浮点运算的限制，我们当然无法得到单位圆盘内的每一个点，但是在我们能够得到的点中，这个算法会得到均匀分布吗？

或者，等效地，此算法会返回以相同概率获得的每个点吗？

我考虑将其发布到 math.se，但由于该问题与 python 和算法密切相关，我认为 StackOverflow 更合适。

现在我的直觉告诉我分布不均匀。考虑种子 s1对于最初生成的点不在单位圆盘内的点，算法将确定性地生成一个新点 (x,y) (让我们假设这一点在单位圆内)并终止。现在我假设有一个种子 s2最初生成的点等于点 (x,y)由 s1 生成.

显然，我可以生成 (x,y)通过使用至少 2 个不同的种子，其中一个实际上首先在单位圆外生成不同的点。现在由于单位圆盘不包含[-1,1) x [-1,1)的一半面积，我会得出结论，并非每个点都由相同数量的种子生成，这意味着对于均匀分布的种子，返回的点不是均匀选择的。

为了防止这变成一个XY question ，请考虑以上段落是我研究的一部分，而不是这个问题的中心点。实际问题是用斜体打印的问题。

Answer 1

will this algorithm return every point obtainable with the same probability?

从技术上讲不是，但是较长的 RNG 周期基本上抵消了这种影响，并且特定点的确切概率并不是我们从连续分布中采样时所关心的。拒绝抽样这种方式应该没问题。

您的分析是正确的，如果种子 s 导致拒绝并且使用 s' 的结果代替，那么两个种子都会产生相同的输出。然而，对于足够长的 RNG 周期，许多种子自然会对应于相同的输出，并且(假设基础 RNG 具有良好的统计特性)这种加倍效应将几乎均匀地分布在所有可能的输出中，因此即使是个人的分布输出点不会受到影响。 Python 的默认 RNG 是 Mersenne Twister，它的周期很大。

即使上述内容不成立，我们也不会在意。我们已经接受了一个基本的不均匀性，因为我们实际上什至无法表示，更不用说生成单位圆盘中的几乎所有点了。如果我们可以生成的一些单独的点比其他点获得更高的权重，那并不重要，只要它不引入任何重要的统计偏差即可。如果左边的点比右边的点有更高的权重，我们会关心。如果一个统计上无法区分的统一集合中的点比另一个统计上无法区分的统一集合中的点获得更高的权重，这没什么大不了的。

最后，如果种子 s 被拒绝，而种子 s' 被用在它的位置上，那么这两个种子会给出相同的输出，但我们实际上并没有看到那个输出两次，因为我们超越了两个种子。如果我们以这种方式生成一系列点，而没有 RNG 的其他干预使用，这基本上消除了您担心的效果。