该算法是否在单位圆盘上生成均匀分布（确定性RNG）？

Question

考虑以下算法：

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

现在如果我的研究是正确的，python的random模块使用系统时间作为初始种子（让我们把它看作是均匀分布的），然后使用mersenne twister algorithm生成一个确定的数字序列，其中对{}的每次调用都将产生一个介于0（包括）和1（排除）之间的数字。在

当算法终止时，点(x,y)应该在单位圆盘上的某个地方。由于浮点算法的局限性，我们当然不能得到单位圆盘内的每一个点，但是在我们可以得到的所有点中，这个算法会导致均匀分布吗？

或者，等价地，这个算法是否会以相同的概率返回每个可以获得的点？

我考虑过把这个贴到数学.se，但由于这个问题与python和算法密切相关，所以我假设StackOverflow更合适。在

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

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

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

Answer 1

你的问题的答案是否是。该算法将在单位圆内提供均匀分布。原因是您的一些样本将超出圆圈。为了获得数学上正确的可预测均匀分布，必须使用极坐标，对于此类坐标，代码示例应执行以下操作：

def get_random_point_in_unit_circle():
    theta = random.random() * ( 2 * math.pi )
    r = math.sqrt(random.random())
    x = r * math.cos( theta )
    y = r * math.sin( theta )
    return (x, y)

编辑：

所以我的回答并不完全正确，谢谢你指出这一点。在概率方面，你的函数提供均匀分布，因为在区域内获得样本的概率是恒定的。拒绝解决方案的缺点是不可预测性。在

Answer 2

上面有几个离子。在

浮点数只是实数的近似值。在

Python random甚至没有给出一个正确取整的随机实数；它给出了0，1/2^53，2/2^53，…（2^53-1）/2^53上的均匀分布。在

由于MT状态不能为零，所以源是近似一致的。在

即使源在每个特定的样本中都是均匀随机的，但有足够多的后续样本是不独立的，因为伪随机生成器就是这样工作的。在

由于种子是有限的，因此不可能生成具有多个结果且不划分种子空间大小的均匀分布。几乎可以肯定的是，你的发行情况就是这样。在

Answer 3

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

从技术上讲没有，但是长的RNG周期基本上抵消了这种影响，而且在从连续分布中取样时，我们并不关心特定点的确切概率。以这种方式进行拒收取样是可以的。在

你的分析是正确的，因为如果seed s导致拒绝，而使用来自{}的结果，那么两个种子产生相同的输出。然而，在足够长的RNG周期内，许多种子自然会对应相同的输出，并且（假设基础RNG具有良好的统计特性），这种倍增效应将几乎均匀地分布在所有可能的输出中，因此即使是单个输出点上的分布也不会受到损害。Python的默认RNG是mersennetwister，它的周期非常长。在

即使上面说的不成立，我们也不在乎。我们已经接受了一个基本的不一致性，事实上我们甚至不能表示，更不用说生成单位圆盘中的几乎所有点。如果我们可以生成的一些独立点的权重比其他点高，那么这并不重要，只要它不引入任何重要的统计偏差。如果左边的点比右边的重，我们会在意的。如果在一个统计上与均匀集不可区分的点比另一个在统计上与均匀集不可区分的点的权重更高，这并不是什么大问题。在

最后，如果seed s被拒绝，而seeds'被用来代替它，那么这两个种子将给出相同的输出，但实际上我们不会看到该输出两次，因为我们已经超过了这两个种子。如果我们以这种方式生成一系列的点，而不使用RNG的其他干预，这基本上消除了您担心的效果。在