我需要在半径为R的圆内生成一个均匀随机点。

我意识到,只要在区间[0…2π),且在区间(0…R)我最终会有更多的点指向中心,因为对于两个给定的半径,小半径内的点会比大半径内的点彼此更接近。

我在这里找到了一篇关于这个的博客文章,但我不明白他的推理。我认为这是正确的,但我真的很想知道他从哪里得到(2/R2)×r以及他如何得到最终解。


更新:在发布这个问题7年之后,关于平方根算法背后的数学问题,我仍然没有得到一个令人满意的答案。所以我花了一天时间自己写了一个答案。链接到我的答案。


当前回答

这样想。如果你有一个矩形,其中一个轴是半径,一个是角,你取这个矩形内半径为0的点。它们都离原点很近(在圆上很近)然而,半径R附近的点,它们都落在圆的边缘附近(也就是说,彼此相距很远)。

这可能会让你知道为什么你会有这种行为。

在这个链接上导出的因子告诉你,矩形中有多少对应的区域需要调整,以便在映射到圆后不依赖于半径。

编辑:所以他在你分享的链接中写道,“通过计算累积分布的倒数,这很容易做到,我们得到r:”。

这里的基本前提是,通过将均匀分布映射为期望概率密度函数的累积分布函数的逆函数,可以从均匀分布创建一个具有期望分布的变量。为什么?现在把它当做理所当然,但这是事实。

这是我对数学的一些直观解释。密度函数f(r)关于r必须与r本身成比例。理解这个事实是任何微积分基础书的一部分。请参阅有关极区元素的部分。其他一些海报也提到了这一点。

我们记作f(r) = C*r;

这就是大部分的工作。现在,由于f(r)应该是一个概率密度,你可以很容易地看到,通过对f(r)在区间(0,r)上积分,你可以得到C = 2/ r ^2(这是给读者的练习)。

因此,f(r) = 2*r/ r ^2

好,这就是如何得到链接中的公式。

然后,最后一部分是从(0,1)中的均匀随机变量u你必须从这个期望密度f(r)映射到累积分布函数的逆函数。要理解为什么会这样,你可能需要找到像Papoulis这样的高级概率文本(或者自己推导)。

对f(r)积分得到f(r) = r^2/ r^2

为了求出它的反函数你设u = r^2/ r^2然后解出r,得到r = r *√(u)

直观上讲,u = 0映射到r = 0。同样,u = 1应该映射到r = r。同样,它通过平方根函数,这是有意义的,与链接匹配。

其他回答

这取决于你对"均匀随机"的定义。这是一个微妙的点,你可以在这里的wiki页面上阅读更多关于它的内容:http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29,在这里同样的问题,对“均匀随机”给出不同的解释会给出不同的答案!

根据你如何选择这些点,分布可能会有所不同,即使它们在某种意义上是均匀随机的。

It seems like the blog entry is trying to make it uniformly random in the following sense: If you take a sub-circle of the circle, with the same center, then the probability that the point falls in that region is proportional to the area of the region. That, I believe, is attempting to follow the now standard interpretation of 'uniformly random' for 2D regions with areas defined on them: probability of a point falling in any region (with area well defined) is proportional to the area of that region.

让我们像阿基米德那样处理这个问题。

我们如何在三角形ABC中均匀地生成一个点,其中|AB|=|BC|?让我们把它扩展到平行四边形ABCD。在ABCD中很容易均匀地生成点。我们均匀地选择AB上的X点和BC上的Y点并选择Z使XBYZ是一个平行四边形。为了在原始三角形中得到一个均匀选择的点,我们只需将ADC中出现的任何点沿AC折叠回ABC。

现在考虑一个圆。在极限情况下,我们可以把它想象成无穷多个等腰三角形ABC, B在原点,A和C在周长上,彼此逐渐接近。我们可以从这些三角形中选择一个角。所以我们现在需要通过在ABC条上选择一点来生成到中心的距离。同样,延伸到ABCD, D现在是圆中心半径的两倍。

使用上述方法可以很容易地在ABCD中选择一个随机点。在AB上随机选一个点,在BC上随机选一个点。Ie。在[0,R]上取一对随机数字x和y,给出离中心的距离。三角形是一条细条AB和BC本质上是平行的。所以Z点到原点的距离是x+y。如果x+y >r我们向下折叠。

这是R=1的完整算法。我希望你同意这很简单。它使用三角函数,但您可以保证它需要多长时间,以及需要多少次random()调用,这与拒绝抽样不同。

t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]

这里是Mathematica。

f[] := Block[{u, t, r},
  u = Random[] + Random[];
  t = Random[] 2 Pi;
  r = If[u > 1, 2 - u, u];
  {r Cos[t], r Sin[t]}
]

ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]

设ρ(半径)和φ(方位角)是两个随机变量,对应于圆内任意一点的极坐标。如果这些点是均匀分布的,那么ρ和φ的分布函数是什么?

对于任意r: 0 < r < r,半径坐标ρ小于r的概率为

P[ρ < r] = P[点在半径r的圆内]= S1 / S0 =(r/ r)2

其中S1和S0分别是半径为r和r的圆的面积。 因此,CDF可表示为:

          0          if r<=0
  CDF =   (r/R)**2   if 0 < r <= R
          1          if r > R

和PDF格式:

PDF = d/dr(CDF) = 2 * (r/R**2) (0 < r <= R).

请注意,对于R=1随机变量根号(X),其中X在[0,1]上是一致的,有这个确切的CDF(因为P[根号(X) < y] = P[X < y**2] = y**2对于0 < y <= 1)。

φ在0 ~ 2*π范围内分布明显均匀。现在你可以创建随机极坐标,并使用三角方程将其转换为笛卡尔坐标:

x = ρ * cos(φ)
y = ρ * sin(φ)

忍不住要发布R=1的python代码。

from matplotlib import pyplot as plt
import numpy as np

rho = np.sqrt(np.random.uniform(0, 1, 5000))
phi = np.random.uniform(0, 2*np.pi, 5000)

x = rho * np.cos(phi)
y = rho * np.sin(phi)

plt.scatter(x, y, s = 4)

你会得到

圆中的面积元是dA=rdr*dphi。这个额外的因子r破坏了你随机选择r和的想法。虽然phi分布平坦,但r不是,而是在1/r内平坦(也就是说,你更有可能击中边界而不是“靶心”)。

为了生成在圆上均匀分布的点从平面分布中选取r从1/r分布中选取。

或者使用Mehrdad提出的蒙特卡罗方法。

EDIT

要在1/r中选择一个随机的r,你可以从区间[1/ r,无穷]中选择一个随机的x,并计算r=1/x。R以1/ R为单位平坦分布。

为了计算一个随机的,从区间[0,1]中选择一个随机的x,并计算=2*pi*x。

首先我们生成一个cdf[x]

一点到圆心的距离小于x的概率。假设圆的半径为R。

显然,如果x = 0,那么cdf[0] = 0

显然,如果x是R,则cdf[R] = 1

显然,如果x = r,则cdf[r] = (r^2)/(r^2)

这是因为圆上的每个“小区域”都有相同的被选中的概率,所以概率与问题区域成比例。距离圆心x的面积是r^2

所以cdf[x] = x^2/R^2因为两者相互抵消了

我们有cdf[x]=x^2/R^2其中x从0到R

我们解出x

R^2 cdf[x] = x^2

x = R Sqrt[ cdf[x] ]

现在我们可以用一个从0到1的随机数来替换cdf

x = R Sqrt[ RandomReal[{0,1}] ]

最后

r = R Sqrt[  RandomReal[{0,1}] ];
theta = 360 deg * RandomReal[{0,1}];
{r,theta}

我们得到极坐标 {0.601168 R, 311.915°}