Polar method

The Polar method by George Marsaglia and Thomas A. Bray is a method for generating normally distributed random numbers ( random number generator ).

history

This method goes back to the Box-Muller algorithm for generating normally distributed random variables . In this case, the Euclidean coordinates are used. With the polar method, these Euclidean coordinates are converted into polar coordinates . This saves the evaluation of trigonometric functions.

description

One assumes random points in the plane that are uniformly distributed in the unit circle. Two standard normally distributed random numbers are generated from their coordinates :

1. Generating two independent, uniformly distributed random numbers , in the interval ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle [-1,1]}$
2. Calculate . If or , go back to step 1. ${\displaystyle q=u^{2}+v^{2}}$ ${\displaystyle q=0}$ ${\displaystyle q\geq 1}$
3. Calculate . ${\displaystyle p={\sqrt {\frac {-2\cdot \ln q}{q}}}}$
4. ${\displaystyle x_{1}=u\cdot p}$and are now two independent, standard normally distributed random numbers. ${\displaystyle x_{2}=v\cdot p}$

The point must lie in the unit circle ( ), and it must be true that the logarithm of zero and division by zero are not defined in the real numbers . Otherwise two new numbers and must be generated. ${\displaystyle (u,v)}$ ${\displaystyle q<1}$ ${\displaystyle q>0}$ ${\displaystyle u}$ ${\displaystyle v}$

Any normally distributed random numbers can be generated from this by linear transformation: The generated values are -distributed, thus providing values ​​that are -distributed. ${\displaystyle x_{i}}$ ${\displaystyle {\mathcal {N}}(0,1)}$ ${\displaystyle a\cdot x_{i}+b}$ ${\displaystyle {\mathcal {N}}(b,a^{2})}$

implementation

Pseudocode

Prozedur ErzeugeNormalverteilteZufallszahlen (Referenzparameter x1, x2)
  Wiederhole
    u = 2 * Zufallszahl - 1  // "Zufallszahl" liefert in [0,1)
    v = 2 * Zufallszahl - 1  //   gleichverteilte Werte
    q = u * u + v * v
  Solange bis (0 < q) und (q < 1)
  p = Wurzel (-2 * ln(q) / q)
  x1 = u * p
  x2 = v * p  // Rückgabe durch die Referenzparameter x1, x2
Ende

C.

double random(); // liefert im Intervall [0,1) gleichverteilte Zufallszahlen

void polar(double *x1, double *x2)
{
   double u, v, q, p;

   do {
      u = 2.0 * random() - 1;
      v = 2.0 * random() - 1;
      q  = u * u + v * v;
   } while (q >= 1.0 || q == 0.0);

   p = sqrt(-2 * log(q) / q);
   *x1 = u * p;
   *x2 = v * p;
}

See also

• Generation of normally distributed random numbers

literature

• G. Marsaglia, TA Bray: A Convenient Method For Generating Normal Variables . In: SIAM Review , Vol. 6, No. 3, July 1964, pp. 260-264