概率组合算法课时-圆内均匀取点一次成功朴素算法

圆内均匀取点一次成功朴素算法中讲到随机点的面积与圆的面积成正比,从而取随机数的平方根赋值给r,使得随机点的面积为均匀分布.问题是:随机点的面积为均匀分布不代表随机点的位置在圆内也是随机分布
 
根据PPT中的代码实现,我对此算法的理解是: 在一个以原点为圆心,R=50的圆中(因为r=sqrt(random(2500)所以max(r*r)<=2500=R*R)),随机点均匀分布在以原点为圆心,以r为半径的圆的边上,又因为theta与r相互独立,所以x和y所表示的点在圆内是均匀分布的.
 
可是代码中对x和y的赋值语句会导致x*x+y*y=r*r=random(2500) 那么跟第一种直觉求法有什么不同呢(r=random(50))? 难道只是因为一个是r而另一个是r*r?
 
更新: 看了auroralian的回答,感觉好像真的是因为r*r为均匀分布才可以,数学上能求证么?

auroralinan

赞同来自: Alfred

我来一个不严密的。 theta可以看作点在角速度上是均匀分布的。 random theta and r的情况下,落在半径为r的圆内的点的数量为N~r,即N与r成正比,该圆的面积为S~r^2=pi(派)*r*r,那么该圆内点的密度为d=N~r/S~r^2。可以看出,d是与1/r成正比的,也就是r越小,密度越大。 random theta and r^2的情况下,点的数量为N~r^2,面积为S~r^2,密度d=N~r^2/S~r^2,即密度d是常数的,所以在圆内处处相等。 手机码字没法写数学公式,希望你能看懂。

邹博 - 计算机科学博士,深谙机器学习算法原理

赞同来自: Alfred

已经在这个帖子下回复了,请移步到这里:http://xxwenda.com/question/2142

要回复问题请先登录注册