High dimensional Sobol' sequences
"There was general mystification among the investment banks I contacted about this ("Snowball sequences?") One bank even told me that if I cracked it it would be worth millions to them. I'll send you a share if I ever crack it."
"There is a commercial library module available from an organisation called BRODA that can generate Sobol sequences in up to 370 dimensions. In a way, this module can claim to be a genuine Sobol number generator since Professor Sobol himself is behind the initialisation numbers that drive the sequence, and he is also linked to the company distributing the library."
Peter Jackel, Monte Carlo Methods in Finance
John Wiley & Sons, 2002
"Preponderance of the experimental evidence amassed to date points to Sobol' sequences as the most effective quasi-Monte Carlo method for application in financial engineering."
Paul Glasserman, Monte Carlo Methods in Financial Engineering
Many complex problems of numerical computation including finance can be effectively solved only by using Monte Carlo (MC) methods. However, in its conventional form, MC approach has slow convergence and low accuracy. By using low discrepancy sequences (LDS) instead of random numbers efficiency of the MC approach can be dramatically improved. It has been recognized through theory and practice that Sobol' LDS is superior to other known LDS. I. Sobol' constructed his sequence by following three main requirements:
- Best uniformity of distribution as N goes to infinity, where N is a number of sampled points.
- Good distribution for fairly small initial sets (N is small).
- A very fast computational algorithm.
Further details can be found in [1-6]. In Sobol's algorithm direction numbers is a key component to its efficiency. Their calculation should be based on solid mathematical analysis. Unfortunately, in some implementations (see f.e. ) this critical issue was overlooked. As a result, constructed LDS did not satisfy above-mentioned criteria and did not perform well in tests.
- Sobol' I.M. On the distribution of points in a cube and the approximate evaluation of integrals. Comput. Math. Math. Phys, 7, 86-112 (1967).
- Sobol' I.M. Uniformly distributed sequences with additional uniformity properties. USSR Computational Mathematics and Mathematical Physics, 16, 5, 236-242 (1976).
- Sobol' I.M., Turchaninov S, Levitan V, Shukhman B.V. Quasirandom sequence generators. Keldysh Inst. Appl. Maths RAS Acad. Sci., Moscow, 24 p. (1992).
- Sobol' I.M. Primer for the Monte Carlo Method, CRC Press (1994).
- Sobol' I.M., Shukhman B.V. Integration with quasirandom sequences: Numerical experience. Internat. J, Modern Phys. C, 6(2), 263-275 (1995).
- Sobol' I.M. On quasi-Monte Carlo integrations. Mathematics and Computers in Simulation, 47, 103-112 (1998).
- Tezuka S. Uniform Random Numbers: Theory and Practice, Kluwer Academic Publishers (1995).
- Sobol’ I.M.,Asotsky D.,Kreinin A.,Kucherenko S. Construction and Comparison of High-Dimensional Sobol’ Generators, Wilmott Journal (2012).
SobolSeq software packages are implementations of the 32000 dimensional Sobol' sequences with modified direction numbers. Dimension of generated LDS can be up to and including 32000. The software was developed developed jointly with Prof. Sobol'. Sobol' sequences produced by SobolSeq satisfy additional uniformity properties: Property A for all dimensions and Property A' for adjacent dimensions. The comparison shows that SobolSeq generators outperform all other known generators both in speed and accuracy.
SobolSeq software packages contain source codes (in C++ and/or FORTRAN) and self-contained Dynamic Link Libraries (DLL) intended for use with Windows applications. The library may be called from, amongst others, Microsoft C/C++, C#, Digital Visual FORTRAN, Microsoft Excel, MATLAB and S-Plus.