Generating Normal Distributed Random Numbers

by M.A. (Thijs) van den Berg


This article describes the most common methods used in generating nomral distributed random numbers.


Contents

[edit] The simple sum approximation

The simpelest algorithm to generate (approximately) Normal distributed random numbers is to sum twelve uniform random numbers 0 < U_1,U_2,\ldots,U_{12} < 1 and substract 6.

N \sim \sum_{i=1}^{12}U_i - 6

This will give random numbers that are approximately normally distributed with mean zero and standard deviation (and variance) one.

[edit] The Box-Muller transform

The Box-Muller transform is used to transform uniform distributed random variables into Normal distributed random values. There are two version of the transform.

[edit] Rectangular form

The rectangular form uses two uniform distributed random between 0 and 1, 0 < U_1, U_2 \le 1 and transform them into two uncorrelated Normal distributed numbers.

\begin{align} N_1 &\sim \sqrt{-2 \ln U_1} \sin(2\pi U_2)\\ N_2 &\sim \sqrt{-2 \ln U_1} \cos(2\pi U_2) \end{align}

[edit] Polar form

The polar form is the preferred form, it's more stable and faster than the rectangular form. It used uniform distributed sampled from the unit circle and converts them into into two uncorrelated Normal distributed numbers. The uniform distributed sampled from the unit circle can be acquired by taking random number between -1 and 1, − 1 < U1,U2 < 1 untill you have two that lie inside a circe, i.e.

R=U_1^2 + U_2^2, R<1

The Normal random numbers are then calcualted using:

\begin{align} N_1 &\sim U_1 \sqrt{\frac{-2 \ln R}{R}}\\ N_2 &\sim U_2 \sqrt{\frac{-2 \ln R}{R}} \end{align}

[edit] The Inverse Normal Distribution

Another method for generating Normal distributed random numbers is to run uniform random numbers 0 < x < 1 through the inverse Normal distribution. This method is particularly useful when using high dimensional low discrepancy sequences like Sobol, Hastons, Faure. These generators generate specific random numbers that can't be used to feed into the Box-Muller transform without losing their properties.

Image:DistNormalInv.png

The equation below gives the Hastings approximation to the inverse Normal distribution N − 1(x). The approximation has a maximum error of 1.0 * 10^-5.

N^{-1}(x) = 1-n(x) (t (a_1 + t (a_2 + t a_3)))\,

with

\begin{align}n(x) &= \frac{1}{\sqrt{2 \pi}}e^{-\frac{x^2}{2}} \\ a_1 &= 0.4361836 \\ a_2 &= -0.1201676 \\ a_3 &= 0.9372980 \\ p &= 0.3326700 \\ t &= 1 / (1 + p x); \end{align}

[edit] High precision algorithm

A high precision algorithm with an absolute value less than 1.15*10^−9 in the entire region can be found on the following page (Peter J. Acklam): http://home.online.no/~pjacklam/notes/invnorm/

[edit] Acceptance-rejection method

The acceptance rejection method is a very simple algorithm that can be used to generate random numbers given any probability distribution function.


The idea is depicted below. Random numbers points (dots) are taken from a 2D area. In this case the x value is chosen to be random between -4 and 4 and y value random bestween 0 and 0.5. The area is chosen is such a way that the probability distribution function (blue curve) is completely inside the area. The area is typically a square area, because you can easily generate random points from a square area. However, any area that fully contains the probability distribution function will do.

For each random point it is checked to see if it lies above or below the probability distribution function. This is done by computing the height of the probability distribution function at the x value of the random point.

  1. If the point is below the probability distribution function (green points) we accept it, and we use the x value of the point as a normal distributed random number.
  2. If the point is above the probability distribution function (red points), we reject it and try the procedure again with a new point.

Looking at the plot, it is easily understood that the probability distribution of the x values of the green points will mimic the probability distribution function (blue line).

Image:NormalReject.png

[edit] Ziggurat algorithm

"The Ziggurat Method for Generating Random Variables"

[edit] Comments

Name (required):

Website:

Comment:


[edit] amit7ul said ...

is there a good reference for generating student-t distributed randoms for a specified degree of freedom

--amit7ul 11:45, 23 August 2007 (CEST)

[edit] sitmo said ...

If you can generate gamma distributed random variables G(a,b) then T=x/sqrt(g) will Student-t distributed, where x is a standard normal draw, and g is a gamma distributed G(n/2, 0.5) draw.

--sitmo 09:42, 12 September 2007 (CEST)

Retrieved from "http://sitmo.com/doc/Generating_Normal_Distributed_Random_Numbers"