比较dekker算法和peterson算法（流行算法BoxMuller变换法）

一、定义

Box–Muller 变换是一种快速产生符合标准正态分布随机数对的一种方法。基本思想是先得到服从均匀分布的随机数，再将服从均匀分布的随机数转变为服从标准正态分布（零期望，单位方差）的独立的随机数对。

它是由 George E. P. Box 与 Mervin E. Muller 在1958年提出，是最早运用与产生高斯白噪声的著名算法之一，它的基本原理是计算出高斯随机数的相位和幅度，进而产生高斯随机数对的算法。实际上，该方法最早是在1934年由Raymond E. A. C. Paley和Norbert Wiener明确提及的。

George E. P. Box是一位统计学大师，统计学中的很多名词术语都以他的名字命名。Box 之于统计学的家学渊源相当深厚，他的导师是统计学开山鼻祖皮尔逊的儿子-英国统计学家Egon Pearson；同时，Box还是统计学的另外一位巨擘级奠基人费希尔的女婿。统计学中的名言“All models are wrong, but some are useful”（所有模型都是错的，但其中一些是有用的）也出自Box之口。

Box-Muller变换通常以标准和极坐标两种形式表示。 Box和Muller给出的基本形式是从区间[0，1]上的均匀分布中获取两个样本，并将它们映射为两个标准的正态分布样本。极坐标形式从不同的区间[-1， 1]中获取两个样本，并将它们映射到两个正态分布的样本，而无需使用正弦或余弦函数。

二、优点

目前，产生正态分布随机数的主流方法有：

• 用中心极限定理生成正态分布
• 逆变换法
• Ziggurat 算法
• Box-Muller变换

Box-Muller变换是作为逆变换采样方法的一种计算效率更高的替代方法而开发的。Ziggurat算法为标量处理器（例如，旧的CPU）提供了一种更有效的方法，而Box-Muller变换对于具有矢量单位的处理器（例如，GPU或现代CPU）更胜一筹。

三、两种形式1、标准形式的 Box–Muller 变换（1）公式

假设变变量 U1 和变量 U2 是（0，1]均匀分布的随机数，

且 U1 和 U2 彼此独立，令：

则 Z0 和 Z1 就是服从 N（0，1）的标准正态分布随机数，并且 Z0 和 Z1 相互独立。

（2）标准形式的python代码演示

def box_muller_trans(): x1 = 0 x2 = 0 w = 0 x1 = np.random.rand() x2 = np.random.rand() y1 = np.cos(2.0*np.pi*x1) * np.sqrt(-2.0*np.log(x1)) y2 = np.sin(2.0*np.pi*x2) * np.sqrt(-2.0*np.log(x2)) return y1,y2

2、 极坐标形式的 Box–Muller 变换（1）公式

假设变量 u 和变量 v 是在[-1，1]上的均匀分布随机量，

u 和 v 相互独立，令：

故而，随机数 z0 和 z1 计算后得出如下结果：

z0 和 z1 是服从分布 N（0，1）的随机数，并且 z0 和 z1 相互 独立。

（2）极坐标形式的python代码演示

def box_muller_trans(): x1 = 0 x2 = 0 w = 0 while (w <= 0)|(w>=1.0): x1 = 2.0*np.random.rand()-1 x2 = 2.0*np.random.rand()-1 w = x1*x1 x2*x2 w = np.sqrt(-2.0*np.log(w)/w) y1 = x1*w y2 = x2*w return y1,y2

3、演示结果

4、小结

也可利用Matlab工具进行算法验证。在实际工程应用中，如果直接采用标准形式的Box-Muller算法的时候，需要计算正弦（sin）和余弦（cos）函数，这种计算耗时较多，效率比较低。Box-Muller 的极坐标形式更加常用，它避开了三角函数的计算，可以在很短的时间内产生大量的符合正态分布的随机数，能够满足了工程计算中对计算速度的要求。

更多的统计分布如何通过均匀分布的变换生成出来，大家可以参考 Sheldon M. Ross 的《统计模拟》。

四、Box-Muller变换的证明1、标准形式推导

2、标准形式证明

设U1,U2相互独立，均服从分布U(0,1)

则X、Y相互独立且均服从标准正态分布。

证明：U1,U2~U(0,1) 所以

因为θ=2πU2, 根据一元随机变量函数分布（见附录）， 有：

因为

同样，根据一元随机变量函数分布，有：

因为U1、U2互相独立，而 θ只取决于U2，R只取决于U1，所以θ 、R互相独立。而独立随机变量联合分布等于边缘分布之积。所以

因为X = Rcosθ, y=Rsinθ, 根据二元随机变量函数分布，有：

其中

所以

所以

同理可得：

可见X和Y均服从标准正态分布。又因可验证

所以X,Y互相独立。

证毕。

3、极坐标形式的推导与证明

设u,v相互独立，均服从分布U(-1,1)，且有

则X、Y相互独立且均服从标准正态分布。

根据Box-Muller变换的标准形式

作变换

可得：

现在证明(*)变换满足: U1,U2相互独立，均服从分布U(0,1)。

证明：

图4-1

如图4-1所示。首先确认U1,U2的取值范围均为(0,1)。因为(u,v)均匀分布在单位圆内，而

故U1取值范围为(0,1)。θ=2πU2,因为θ的取值范围是(0,2π), 故U2的取值范围是(0,1)。

因为(u,v)均匀分布在单位圆内，故

根据二元随机变量函数分布(见附录)，有

现在求J

所以

所以

所以

同理:

故U1，U2均服从U(0,1)。

又

故U1,U2相互独立。

证毕。

五、附录1、一元随机变量函数的分布

如果

y为单调函数，则

证明：因为

P{Y ≤y(x)} = P{X ≤x},

P{Y ≤y(x dx)} = P{X ≤x dx}

两式相减得

P{y(x) ≤Y ≤y(x dx)} = P{x ≤X ≤x dx}

又

dy之所以加绝对值，是因为dy有可能为负（当y为减函数时，区间[y(x),y(x dx)]为负区间，dy为负）。

得

所以

2、二元随机变量函数的分布

设X,Y均为二元随机变量，即X=(X1,X2), Y=(Y1, Y2)

向量y=(y1, y2), 如果

则：

证明：

对于X取值区域上的面元dS，将经过函数y映射为Y的取值区域上的面元记为y(dS)，有：

P{X∈dS} = P{Y∈y(dS)}

又

其中Area(y(dS))加绝对值，是因为Area(y(dS))可能为负（J<0时）。

又因为面积元之比等于雅可比行列式，即

Area(y(dS))=J * Area(dS)

所以

,