Tuesday, February 03, 2015

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:
W. Shaw has an excellent overview of the accuracy of the various methods in his paper Refinement of the normal quantile.

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:
This allows to leak less correlation than the standard full truncated Euler.

No comments :

Post a Comment