My watch list  

Marsaglia polar method

In computer science – in particular, in applications of the Monte Carlo method – the Marsaglia polar method is a method for generating a pair of independent standard normal random variables by choosing random points (xy) in the square −1 < x < 1, −1 < y < 1 until

s=x^2+y^2 < 1, \,

and then returning the required pair of normal random variables as

x\sqrt{-2\ln(s)/s}\,,\ \ y\sqrt{-2\ln(s)/s}.

Theoretical basis

The underlying theory may be summarized as follows.

If u is uniformly distributed in the interval 0 ≤ u < 1, then the point (cos(2πu), sin(2πu)) is uniformly distributed on the unit circumference x2 + y2 = 1, and multiplying that point by an independent random variable ρ whose distribution is

\Pr(\rho<a)=\int_0^a re^{-r^2/2}\,dr

will produce a point

\left(\rho\cos(2\pi u),\rho\sin(2\pi u)\right)

whose coordinates are jointly distributed as two independent standard normal random variables.


This idea dates back to Laplace, whom Gauss credits with finding

I=\int_{-\infty}^\infty e^{-x^2/2}\,dx

by taking the square root of

I^2 = \int_{-\infty}^\infty\int_{-\infty}^\infty e^{-(x^2+y^2)/2}\,dx\,dy      =\int_0^{2\pi}\int_0^\infty re^{-r^2/2} \, d\theta \, dr.

The transformation to polar coordinates makes evident that θ is uniformly distributed (constant density) from 0 to 2π, and that the radial distance r has density


(Note that r2 has the appropriate chi square distribution.)

This method of producing a pair of independent standard normal variates by radially projecting a random point on the unit circumference to a distance given by the square root of a chi-square-2 variate is called the polar method for generating a pair of normal random variables,

Practical considerations

A direct application of this idea,

x=\sqrt{-2\ln(u_1)}\cos(2\pi u_2),\ y=\sqrt{-2\ln(u_1)}\sin(2\pi u_2)

is called the Box Muller transform, in which the chi variate is generated as


but that transform requires logarithm, square root, sine and cosine functions.

The Marsaglia polar method, in which a random point (xy) inside the unit circle is projected onto the unit circumference by setting s = x2 + y2 and forming the point


is a faster procedure.

That random point on the circumference is then radially projected the required random distance by means of


using the same s because that s is independent of the random point on the circumference and is itself uniformly distributed from 0 to 1.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Marsaglia_polar_method". A list of authors is available in Wikipedia.
Your browser is not current. Microsoft Internet Explorer 6.0 does not support some functions on Chemie.DE