User:Halibobo123/Box–Muller transform

Box-Muller变换的可视化 — 单位方阵中的彩色点(u1,u2)（画作圆圈）被映射到高斯平面坐标系(z0,z1)（画作十字）中 。边上的图是z0和z1的概率发布函数。z0和z1是无界的；由于图示点的选择，他们落在[-2.5,2.5]间。在 SVG文件中, 你可以悬停鼠标在一个点上去突出它以及其相应变换后的点。

Box–Muller变换是乔治·爱德华·佩勒姆·巴克斯(George Edward Pelham Box)和莫文·埃德加·穆勒(Mervin Edgar Muller) 提出的一种方法，用于在给定均匀分布随机数源的情况下生成一对服从独立标准正态分布（期望为0，单位方差）的随机数。这种方法实际上是由雷蒙德-佩利(Raymond E. A. C. Paley)和诺伯特-维纳(Norbert Wiener)于1934第一次明确提及。

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

Box-Muller 变换是作为一种计算效率更高的逆变换采样的替代方法而开发的。ziggurat 算法为标量处理器（如老式 CPU）提供了一种更高效的方法，而 Box-Muller 变换则更适用于具有矢量单元的处理器（如 GPU 或现代 CPU）。

基本形式

假设 U₁ 和 U₂ 是从单位区间[0,1]上的均匀分布中抽出的独立样本。

使

$Z_{0}=R\cos(\Theta )={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})\,$

和

$Z_{1}=R\sin(\Theta )={\sqrt {-2\ln U_{1}}}\sin(2\pi U_{2}).\,$

那么Z₀和Z₁是相互独立的服从标准正态分布的随机变量。

这一推导基于二维直角坐标系的一个特性，即 X 和 Y 坐标由两个独立的正态分布随机变量描述，相应极坐标中R²和Θ（如上图所示）的随机变量也是独立的，可表示为

$R^{2}=-2\cdot \ln U_{1}\,$

和

$\Theta =2\pi U_{2}.\,$

由于R²是标准二元正态变量（X，Y）的正态平方，因此它具有两个自由度的卡方分布。在两个自由度的特殊情况下，卡方分布与指数分布重合，上述R²的方程是生成所需的指数变量的简单方法。

极坐标形式

Two uniformly distributed values, u and v are used to produce the value s = R², which is likewise uniformly distributed. The definitions of the sine and cosine are then applied to the basic form of the Box–Muller transform to avoid using trigonometric functions.

极坐标形式最早由 J. Bell提出，后经 R. Knop修改。虽然极坐标方法有几个不同的版本，但 R. Knop 的版本在此介绍，因为它使用最广泛，部分原因是它被收录在Numerical Recipes 中。D. Knuth 在The Art of Computer Programming一书中以 "算法P "描述了一种略有不同的形式。

给定独立且均匀分布在封闭区间 [-1, +1] 内的 u 和 v，设 s = R² = u² + v²。如果 s = 0 或 s ≥ 1，则舍弃 u 和 v，尝试另一对 (u, v）。因为 u 和 v 是均匀分布的，而且只接受了单位圆内的点，所以 s 的值也将均匀分布在开放区间（0，1）内。通过计算 s 在区间（0，1）内的累积分布函数得到后者。这就是一个半径为$\scriptstyle {{\sqrt {s}} \over \pi }$的圆。由此我们可以发现概率密度函数在区间 (0, 1) 上的常值为 1。同样，$\scriptstyle {\Theta \over 2\pi }$均匀分布在区间 [0, 1]，且与 s 相独立。

We now identify the value of s with that of U₁ and $\scriptstyle \theta /(2\pi )$ with that of U₂ in the basic form. As shown in the figure, the values of $\scriptstyle \cos \theta =\cos 2\pi U_{2}$ and $\scriptstyle \sin \theta =\sin 2\pi U_{2}$ in the basic form can be replaced with the ratios $\scriptstyle \cos \theta =u/R=u/{\sqrt {s}}$ and $\scriptstyle \sin \theta =v/R=v/{\sqrt {s}}$, respectively. The advantage is that calculating the trigonometric functions directly can be avoided. This is helpful when trigonometric functions are more expensive to compute than the single division that replaces each one.

Just as the basic form produces two standard normal deviates, so does this alternate calculation.

$z_{0}={\sqrt {-2\ln U_{1}}}\cos(2\pi U_{2})={\sqrt {-2\ln s}}\left({\frac {u}{\sqrt {s}}}\right)=u\cdot {\sqrt {\frac {-2\ln s}{s}}}$

和

$z_{1}={\sqrt {-2\ln U_{1}}}\sin(2\pi U_{2})={\sqrt {-2\ln s}}\left({\frac {v}{\sqrt {s}}}\right)=v\cdot {\sqrt {\frac {-2\ln s}{s}}}.$

两种形式的对比

The polar method differs from the basic method in that it is a type of rejection sampling. It discards some generated random numbers, but can be faster than the basic method because it is simpler to compute (provided that the random number generator is relatively fast) and is more numerically robust. Avoiding the use of expensive trigonometric functions improves speed over the basic form. It discards 1 − π/4 ≈ 21.46% of the total input uniformly distributed random number pairs generated, i.e. discards 4/π − 1 ≈ 27.32% uniformly distributed random number pairs per Gaussian random number pair generated, requiring 4/π ≈ 1.2732 input random numbers per output random number.

The basic form requires two multiplications, 1/2 logarithm, 1/2 square root, and one trigonometric function for each normal variate. On some processors, the cosine and sine of the same argument can be calculated in parallel using a single instruction. Notably for Intel-based machines, one can use the fsincos assembler instruction or the expi instruction (usually available from C as an intrinsic function), to calculate complex

参考文献

• Howes, Lee; Thomas, David (2008). GPU Gems 3 - Efficient Random Number Generation and Application Using CUDA. Pearson Education, Inc. ISBN 978-0-321-51526-1.

External links

[[Category:带有C++代码示例的条目]] [[Category:變換]]