Sobol quasi-random sequences
Quasi-random sequences (also known as low-discrepancy sequences) are designed to place points in an N-dimensional space aiming to fill it as uniformly, homogeneously and fast as possible. A simulation based on such a sequence may look like a random process but really there is nothing random (or even pseudo-random) about it, since the points are placed strategically and of course deterministically. Just like the points on a regular Cartesian grid that we could use in order to numerically integrate a function over some N-dimensional space. Perhaps the most popular such sequence in quantitative finance is due to Prof. Sobol. The construction of Sobol sequences is based on a set of initial direction numbers and so depending on those the resulting sequences will have better or worse properties. See P. Jäckel, 2002 [1] for a concise and practical presentation of this subject and Monte Carlo methods in finance in general. The pricer uses the set of initial direction numbers published by Joe & Kuo, 2010. See Joe & Kuo, 2008 [2] for the methodology used to obtain those numbers.
The above presentation illustrates the use of Sobol sequences for the pricing of three types of options included in the pricer in decreasing order of typically gained advantage, namely Asian, barrier and Bermudan vanilla options. The blue line marks the exact price which (when not available analytically) is calculated by the PDE solver on a very high resolution grid. The exact time-marching scheme is used for all simulations so that discretization bias doesn't cloud the comparisons. The first two slides demonstrate where Sobol sequences really shine, i.e. Asian option pricing. No variance reduction techniques are involved, i.e the first slide is based on plain Monte Carlo without antithetic sampling and the second uses a Sobol sequence as is, i.e. without the Brownian bridge path construction. The Sobol numbers advantage is quite dramatic. The next two slides compare the performance for barrier option pricing, but this time with the usual variance reduction techniques applied in each case. The benefit from using Sobol sequences is still undoubted, though it seems less dramatic than with the Asian option. Since in this example the option is European and the barrier continuously monitored, the number of monitoring / exercising dates specified is not applicable, but it is still used by the pricer for the time-discretization, i.e. Sobol variates / vectors of dimension 12 are used for the paths construction. You can use the pricer to see how the situation changes for example when the barrier monitoring is discrete. Finally simple Bermudan vanilla put pricing seems to be where the least benefit is. Slides 5 and 6 compare the number generators directly, 7 and 8 with the usual variance reduction techniques applied. As can be seen, there still is something to be gained from the use of the quasi-random sequence, so overall we can say advantage Dr Sobol!
Sobol sequences in high dimensions
It is a known fact that low-discrepancy sequences (Sobol included) see their low-discrepancy advantage get eroded in high dimensions. Jäckel, 2002 [1] finds that even properly initialized Sobol sequences offer no discrepancy advantage over pseudo-random numbers for dimension N=100, or even N=15 for that matter. While I have not calculated and compared the discrepancy of the present Sobol sequences in this manner, I thought I could try indirectly through their application in pricing.
So here is a one-year maturity Asian option with daily sampling, i.e. the dimension of the problem is 252, quite high. Having read [1] I was not expecting to see any benefit directly from plain Sobol numbers. Surprisingly though, the 252-D Sobol variates still seem to hold a visible advantage over their pseudo-random counterparts in terms of convergence to the exact value, even without the dimension reordering effected by the Brownian bridge (BB) path construction. Adding BB to the mix just kills it (the variance that is). At this point you may be wondering what in the world a "warmed up" sequence is and why would we need to use it. Well it can be seen that using the sequence as it comes (slide 3) makes the convergence graph start biased low and then trying to catch up. This behavior can be eliminated by discarding the first half of the total number of Sobol vectors that we generate, which is "warming up" the sequence. It's a trick used sometimes, presumably to avoid situations like this. Another example of such behavior can be seen here.
Of course that's not all there is to it when it comes to making sure that quasi-random sequences are fit for purpose and conceivably there may be hidden problems that just don't manifest themselves in the particular application of Asian option pricing. But for the (educational) purpose of this application I will trust Kuo & Joe have done their extensive tests properly and say well done!
You can reproduce the above graphs, or experiment further if you wish, using the standalone pricer (free beta version for Windows PCs).
References
[1] Jäckel, P. (2002). Monte Carlo Methods in Finance. John Wiley & Sons Ltd.
[2] Joe, S. & Kuo F. Constructing Sobol Sequences with Better Two-Dimensional Projections, SIAM Journal on Scientific Computing, 30(5) (2008), pp. 2635–2654.
[2] Joe, S. & Kuo F. Constructing Sobol Sequences with Better Two-Dimensional Projections, SIAM Journal on Scientific Computing, 30(5) (2008), pp. 2635–2654.