从产生单位圆内的随机点联想到的

本帖最后由都市侠影于 2012-7-23 12:30 编辑

Kuing版的这个帖子http://kkkkuingggg.5d6d.net/thread-405-1-1.html里涉及到要随机产生单位圆内的点，并要符合几何概率，也就是说，点落在任意面积相等区域上的概率都应当是相等的。他那里采用的是从圆外接正方形中随机产生点，若点不在圆内则重新生成点，直到落在圆内为止。我当时给了个建议，说用极坐标来生成，先在0到1上均匀生成r，然后随机生成角度，最后 $x=\cos\theta$,$y=\sin\theta$。这个方法经Kuing指出其实不符合几何概率，详细的认证可以参考这篇文章http://blog.csdn.net/codeboycjy/article/details/6225886，我当时就想改进这个方法，直觉告诉我通过改进是可以达到要求的。
原来的方法问题在于，点落在圆 $x^2+y^2<r^2$ 内的概率是 $r$,跟半径是成正比的，这样一来，落在圆 $x^2+y^2<(\frac{1}{2})^2$ 内的概率是 $\frac{1}{2}$,这个就不符合要求了，那么问题的根源在哪呢，在于随着半径 $r$ 的增大，圆 $x^2+y^2=r^2$ 的周长变长了，但按照原来的方法，半径取到 $r$ 的概率却是一成不变的，如果这个概率能随着 $r$ 增大而增大，那么问题有望解决。下面就按照这个思路来展开。
关键在于半径 $r$ 如何产生，现在把它看成一个连续型随机变量，定义它的分布函数为
\[
F(t)=P(r<t)=
\begin{cases}
0 & x \leqslant 0 \\
t^2 & 0<x\leqslant 1 \\
1 & x>1
\end{cases}
\]
这个 $t^2$ 是怎样想到的呢？可以这样，因为我希望这个随机变量 $r$ 取小于 $t$ 的概率，应当等于圆 $x^2+y^2=t^2$ 与单位圆的面积之比，也就是 $t^2$，这样就得到了它的分布函数，那么它的密度函数自然就是
\[
f(t)=
\begin{cases}
2t & 0<t<1 \\
0 & \textrm{else}
\end{cases}
\]
这样的分布凭直觉是符合要求的，按照这个分布，随着 $r$ 的增大，点落在圆周 $x^2+y^2=r^2$ 上的概率也会随着变大。可以简单的看一下它落在圆环 $r_1^2<x^2+y^2<r_2^2$ 上的概率：
\[
P=\int_{r_1}^{r_2}f(x)dx=r_2^2-r_1^2
\]
显然这个概率正是需要的概率。
当然这并不能说明，按照这个分布，点落在任意等面积的区域上的概率都是相等的，现在就来完成这一点的证明。
在单位圆任意取一个区域 $D$，假如它在极坐标系下可以表示为
\[
\rho_1(\theta)<\rho<\rho_2(\theta) \quad \alpha<\theta<\beta
\]
那么点落在这个区域上的概率就是
\begin{align}
&\int\!\!\!\int_Df(t)d\sigma \\
&=\frac{1}{2}\int_{\alpha}^{\beta}d\theta\int_{\rho_1(\theta)}^{\rho_2(\theta)}f(t)dt \\
&=\frac{1}{2}\int_{\alpha}^{\beta}(\rho_2^2(\theta)-\rho_1^2(\theta))d\theta
\end{align}
这个正好是这个区域的面积，这就说明上面的那个分布的确满足几何概率。
好了，分布有了，但是如何实现呢？现在的计算机都可以容易的实现区间 $[0,1]$ 上的均匀分布，关键如何用这个均匀分布去实现前面所需要的那个分布，也就是说，如何才能让一个过程产生一个数，这个过程必须使得产生的数小于任何数 $t(0<t<1)$ 的概率都是 $t^2$。
更让我感兴趣的问题是，如何实现一个指定分布函数的分布？
一个直观的想法就是利用 $[0,1]$ 上的均匀分布，假如随机变量 $s$ 服从这个均匀分布，然后我们的随机变量就作为一个 $s$ 的函数 $r=h(s)$，为了方便，假定 $h(s)$ 是一个单调增加的函数，那么
\[
F(t)=P(r<t)=P(h(s)<t)=P(s<h^{-1}(t))=h^{-1}(t)
\]
这就说明了，要想随机变量 $r$ 的分布函数是 $F(t)$，只要把转换函数 $h(s)$ 取为分布函数 $F(t)$ 的反函数就可以了，至于 $h(s)$ 单调增加，因为分布函数本来就是单调不减的，只要给他加个严格增加的限制就可以了。这样就实现了一个指定分布函数的分布。

本主题由 kuing 于 2012-7-26 00:08 移动