Box-Muller Algorithm

以前想过的一个很有意思的问题,如何从均匀分布生成正态分布.

Description

$x_1$ and $x_2$ are two independent $uniform(0,1)$ random variables, and let

Then

are independent $normal(0,1)$ random variabls.

Proof

首先,

代入$r,\theta$得到

这里可以看到$f(r,\theta)$的取值只和$r$有关,所以对于相同的$r=R$,$\theta$的取值的概率相同,所以可知

接下来我们求出$r$的pdf和cdf,即$p(r)$和$F(r)$,然后用$F^{-1}(1-x_1)$来得到$r$.

对$\theta$求积分

得到$r$的概率密度函数

然后可知$r$的累积分布函数

同时

因为$F^{-1}(1-U)$就可以把均匀分布变量转化为目标分布,得到

Polar form

原始的方法需要计算$sin(\theta)$和$cos(\theta)$, Polar form的改进可以直接取样出$sin(\theta)$和$cos(\theta)$.

方法: 在单位圆里均匀取样一个点$(x,y)$, 可得

很容易验证,$s$符合均匀分布,最终我们得到

如何在单位圆内均匀取样? Rejection sampling

do
  $x,y \sim U(0,1)$
while $x^2 + y^2 > 1$