Monte Carlo & Inverse Cumulative Normal Distribution
In most financial Monte-Carlo simulations, there is the need of generating normally distributed random numbers. One technique is to use the inverse cumulative normal distribution function on uniform random numbers. There are several different popular numerical implementations:- Wichura AS241 (1988)
- Moro "The full Monte" (1995)
- Acklam (2004)
- Shaw breakless formula optimized for GPUs (2011)
But what about performance? In Monte-Carlo, we could accept a slighly lower accuracy for an increase in performance.
I tested the various methods on the Euler full truncation scheme for Heston using a small timestep (0.01). Here are the results with Sobol quasi-rng:
AS241 0.9186256922511046 0.42s
MORO 0.9186256922459066 0.38s
ACKLAM 0.9186256922549364 0.40s
ACKLAM REFINED 0.9186256922511045 2.57s
SHAW-HYBRID 0.9186256922511048 0.68s
In practice, the most accurate algorithm, AS241, is of comparable speed as the newer but less accurate algorithms of MORO and ACKLAM. Acklam refinement to go to double precision (which AS241 is) kills its performance.
What about the Ziggurat on pseudo rng only? Here are the results with Mersenne-Twister-64, and using the Doornik implementation of the Ziggurat algorithm:
AS241 0.9231388565879476 0.49s
ZIGNOR 0.9321405648313437 0.44s
There is a more optimized algorithm, VIZIGNOR, also from Doornik which should be a bit faster. As expected, the accuracy is quite lower than with Sobol, and the Ziggurat looks worse. This is easily visible if one plots the implied volatilities as a function of the spot for AS241 and for ZIGNOR.
 |
| AS241 implied volatility on Mersenne-Twister |
 |
| ZIGNOR implied volatility on Mersenne-Twister |
Zignor is much noisier.
Note the slight bump in the scheme EULER-FT-BK that appears because the scheme, that approximates the Broadie-Kaya integrals with a trapeze (as in Andersen QE paper), does not respect martingality that well compared to the standard full truncated Euler scheme EULER-FT, and the slightly improved EULER-FT-MID where the variance integrals are approximated by a trapeze as in Van Haastrecht paper on Schobel-Zhu:
