Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Does anyone know of an approximation for the logarithm of the standard normal CDF for x<0?

I need to implement an algorithm that very quickly calculates it. The straightforward way, of course, is to first calculate the CDF (for which I can find suitably simple approximations on Wikipedia), and then to take the logarithm of that. Obviously I'd like to avoid the time-cost of having to calculate two special functions, not to mention that the tiny intermediate value (in the tail) rules out using fixed-point arithmetic which is much faster than floating-point arithmetic.

I know there are hundreds of approximations for all kinds of statistical functions, but the fact that this is the logarithm of one makes it harder to find one. I'd be very grateful if anyone could point me to one, or to a source where I might find one.

share|improve this question
    
How far below $0$ could $x$ go? Different useful approximations kick in below around $-4$ to $-5$ and yet other ones are needed for very negative values. For instance, if $x\lt -38$ or so, the CDF will underflow IEEE double precision floats (but of course its log will not be problematic). How accurate does your approximation need to be? –  whuber Jul 6 at 23:15
    
@whuber x won't go below -5. Would be great if the log_2 could be within 0.2 + 10% or so of its true value, but this isn't critical. I'd probably go with whatever I can get. –  Museful Jul 6 at 23:45
1  
That's rather critical information in your comment there. It's probably better to also add it to your post. –  Glen_b Jul 7 at 0:19
    
Related: stats.stackexchange.com/q/7200/2970. The Cody and/or Lee references may provide suitable approaches. –  cardinal Jul 7 at 3:19
    
@Cardinal That's right: the Mills ratio yields excellent approximations to the logarithm for extremely negative $x$. By empirically adjusting its coefficients one can achieve accuracy of $\pm 0.0003$ (in the natural logs) for $x\in [-7,-3]$. By taking the next term in the continued fraction and again adjusting the coefficients, errors can be limited to $\pm 0.000005$ for $x\lt -7$: that approximation is $\log(R(x))\approx-\log \left(x+\frac{1}{x+\frac{1.9}{x}}\right)$. But the more terms of the continued fraction you take, the larger $|x|$ must be for it to be a good approximation. –  whuber Jul 7 at 15:10

2 Answers 2

up vote 4 down vote accepted

Even a simple least squares cubic fit to $\log(\Phi(x))$ values for $x$ between -5 and 0 seems to be fairly adequate.

Just to get a quick sense of it I generated $x$ values every 0.01 between -5 and 0, and tried least squares cubic and quintic (5th degree) polynomial fits to $\log_2(\Phi(x))$. I presume you can do that as easily as I did, so I won't labor the point.

The maximum absolute error in $\log_2(\Phi(x))$ for the quintic is $5.2\times 10^{-4}$, which occurs at zero.

[It's not completely clear what you mean by "within 0.2 + 10% or so". If you could elaborate so as to make your criterion explicit, then I could address that in detail, and maybe adjust the weights to better optimize your criterion.]

When evaluating polynomials, if speed matters, you should keep Horner's method in mind.


As cardinal suggested, the plot is quite illustrative. Since I'd already generated one, I should have put it here:

enter image description here

Here's the (signed) error (absolute scale error in the logs):

enter image description here

it looks much as we might expect for a least squares fit. The lack of fit is pretty moderate; for many purposes that would be fine.


An alternative is you can flip the Karagiannidis & Lioumpas approximation (see here, just above "$\text{Values}$") for the upper tail around to the lower tail (by replacing $x$ by $-x$ in their formula) and taking logs:

$$Q(x)\approx\frac{\left( 1-e^{-1.4x}\right) e^{-\frac{x^{2}}{2}}}{1.135\sqrt{2\pi}x}, x >0 $$

So we get

$$\ln(\Phi(x))\approx \ln(1-e^{1.4x})-\ln(-x) -\frac{x^2}{2} - 1.04557$$

to get base 2 logs, you just multiply the result by $\log_2(e)$

This is less accurate than the quintic fit I mentioned, and likely slower to evaluate because of the logs and exponentiation. Still, it's nice and short, which has some advantages. Note that it wasn't designed for the log-scale.


The original paper has K&L's Equation 6 as:

$$\frac{(1-e^{-Ax}) e^{-x^2}}{B\sqrt{\pi}x}\approx\text{erfc}(x)$$

For $x$ values on the range [0,20] they suggest $A=1.98$ and $B=1.135$.

Dividing $x$ through by $\sqrt{2}$ to obtain $Q$, that suggests the formula on the Wikipedia page ($1.98/\sqrt{2}\approx 1.40007$)


Let's look at the quality of the approximation on the log-scale.

enter image description here

The purple dashed line is the K&L approximation. Now let's look at the error:

enter image description here

The size of the error gets quite a bit larger than our quintic. The fact that it's nearly linear in $x$ at the left half of the range suggests that we might improve the error by adding about $0.02x$ or $0.025x$ to the formula in the logs - but this would make the approximation a little worse for values near -1. Whether one would do that depends on what characteristics are desired.

share|improve this answer
1  
For a number of reasons, that Wikipedia page needs some significant attention, or, at least, some TLC from a knowledgeable statistician or probabilist. While not the only example, the statement regarding the K&L approximation would make any mathematician cringe since the absolute relative error is obviously (i.e., by inspection) nearly 90% in the tails! :-) –  cardinal Jul 7 at 3:01
    
(+1) Simple (e.g., polynomial or rational) approximations can do quite well over a wide range of values of the argument for $\log \Phi$ since it's actually quite linear near zero. A simple graph would depict this nicely. –  cardinal Jul 7 at 3:04
    
@cardinal Thanks for both comments. I've added some graphs, including one for $\log_2(\Phi(x))$ (in which the near-linearity at zero can be seen), another for the error in the quintic approximation I got, and I also had a closer look at the K&L approximation on the log-scale (again with graphs). –  Glen_b Jul 7 at 4:28
    
I didn't expect such a comprehensive answer! By "<0.2+10% or so" I meant $<0.2+0.1*\log_2(\Phi(x))$ i.e. better accuracy closer to $x=0$, but by pre-constraining the polynomial's y-intercept to the correct value I'm getting exactly what I needed. Thank you so much! –  Museful Jul 7 at 9:44
    
I'm glad it was useful to you. –  Glen_b Jul 7 at 10:03

To cover a wider range than originally requested, I eventually came up with this rational approximation

$$ \ln(\Phi(x<0)) \approx -\frac{1}{2}x^2 -4.8 + 2509\frac{x-13}{(x-40)^2(x-5)} $$

which has absolute error under 0.04 out to 20 standard deviations, after which the error may exceed that but remains under 0.04% of the value (as far as I can verify with numerical calculations).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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