13
$\begingroup$

I have uniform value in [0,1). I'd like to transform it into a standard normal distribution value, in a deterministic fashion.

What I'm confused about with the Box-Muller transform is that it takes two uniform values in [0, 1), and transform them into two normal random values.

However, I only have one uniform value. How do I apply Box-Muller over a single value?

$\endgroup$
2

5 Answers 5

10
$\begingroup$

The Box-Muller method is commonly used. It's simple to implement. And if you need several values, you can use it to produce normal samples two at a time. Otherwise, you could just discard one of the values and pretend you never created it.

George Marsaglia's Ziggurat method is more efficient than Box-Muller but more complicated.

$\endgroup$
7
$\begingroup$

Use the inverse transform method.

$\endgroup$
2
  • 1
    $\begingroup$ And if you need to compute this, the $F_X^{-1}$ that appears there can be simply expressed in terms of the inverse error function. $\endgroup$ Jun 17, 2010 at 22:00
  • 2
    $\begingroup$ That works, but the inverse CDF is expensive to evaluate. There are much more efficient methods. $\endgroup$ Jun 17, 2010 at 23:14
7
$\begingroup$

Given one uniform value in [0,1) you can use alternate digits to get two uniform values. Or alternate bits.

Some other methods to generate standard gaussians are here: http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution

$\endgroup$
6
$\begingroup$

Although your setup is in the interval $[0,1)$, I will ignore the left endpoint and work with $(0,1)$. Recall the cumulative distribution function for the normal distribution: $$ \Phi(t) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^t e^{-(1/2)x^2}dx. $$ This function is an increasing map from ${\mathbb R}$ onto $(0,1)$ and its value at $t$ gives the probability that a normal random variable has value less than or equal to $t$. Let $g \colon (0,1) \rightarrow {\mathbb R}$ be its inverse, i.e., $g(y)$ is the unique solution $t$ to $\Phi(t) = y$. That is, $$ \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{g(y)} e^{-(1/2)x^2}dx = y. $$ Note the input to $g$ is a number in $(0,1)$ and the output is a real number. That's the kind of setup you're looking for.

Claim: If $X$ is a uniform random variable on $(0,1)$ then $g(X)$ is a normally distributed random variable on the real line.

Proof: For $a < b$ in ${\mathbb R}$, we want to show the probability $a \leq g(X) \leq b$ is $$ \frac{1}{\sqrt{2\pi}}\int_{a}^b e^{-(1/2)x^2}dx = \Phi(b) - \Phi(a). $$ Since $g$ and $\Phi$ are inverses of each other, the condition $a \leq g(X) \leq b$ is the same as $\Phi(a) \leq X \leq \Phi(b)$, which is a condition in $(0,1)$ and your hypothesis about $X$ being uniform in $(0,1)$ is that the probability of that is $\Phi(b)- \Phi(a)$. Since $$ \Phi(b) - \Phi(a) = \frac{1}{\sqrt{2\pi}}\int_{a}^b e^{-(1/2)x^2}dx, $$ we've got a Gaussian distribution. (That you want $X$ to be uniform made this a lot easier to describe.)

Quite generally, if you want to model a probability distribution on the real line with density function $f(x)$ by sampling a uniform random variable $X$ on $(0,1)$, you can use the function $g(X)$, where $g$ is the inverse of the cumulative distribution function $F(t) = \int_{-\infty}^t f(x)dx$.

$\endgroup$
4
  • $\begingroup$ Gerry's answer suggests a possibly more practical method: take a large number of samples from a uniform distribution on $(0,1)$ and use the central limit theorem, which explains how a standard normal distribution is a limit of a normalized average of independent identically distributed random variables. $\endgroup$
    – KConrad
    Jun 17, 2010 at 23:04
  • $\begingroup$ KConrad, someone already gave this answer above (by linkning to a Wikipedia article) and someone else pointed out that it's computationally expensive. $\endgroup$ Jun 18, 2010 at 23:58
  • 2
    $\begingroup$ Michael, I did see that, but (a) I'm not a probabilist and that's my excuse for not knowing what "inverse transform method" meant when I first saw it (once I looked at it later I understood it immediately, of course) and (b) the answer which said this inverse transform method is not so efficient was posted after mine, chronologically. $\endgroup$
    – KConrad
    Jun 19, 2010 at 0:29
  • 1
    $\begingroup$ I'm not sure that in this case it is so expensive, as efficient methods and precalculated values are known for the inverse-error function. $\endgroup$
    – Amir Sagiv
    Jul 25, 2015 at 14:12
2
$\begingroup$

The best way to obtain the inversion from U[0, 1] to Normal distribution is by using an algorithm presented in a famous short paper of Moro (1995). Moro presented a hybrid algorithm: he uses the Beasley & Springer algorithm for the central part of the Normal distribution and another algorithm for the tails of the distribution.

He modeled the distribution tails using truncated Chebyschev series..... .................. http://marcoagd.usuarios.rdc.puc-rio.br/quasi_mc.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.