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."

Contingency Analysis Forum

"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
Springer, 2003

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:

  1. Best uniformity of distribution as N goes to infinity, where N is a number of sampled points.
  2. Good distribution for fairly small initial sets (N is small).
  3. A very fast computational algorithm.

Comparisson between SobolSeq370 and random numbers, n=2

Further details can be found in [1-6], [8]. 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. [7]) this critical issue was overlooked. As a result, constructed LDS did not satisfy above-mentioned criteria and did not perform well in tests.

  1. 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).
  2. Sobol' I.M. Uniformly distributed sequences with additional uniformity properties. USSR Computational Mathematics and Mathematical Physics, 16, 5, 236-242 (1976).
  3. Sobol' I.M., Turchaninov S, Levitan V, Shukhman B.V. Quasirandom sequence generators. Keldysh Inst. Appl. Maths RAS Acad. Sci., Moscow, 24 p. (1992).
  4. Sobol' I.M. Primer for the Monte Carlo Method, CRC Press (1994).
  5. Sobol' I.M., Shukhman B.V. Integration with quasirandom sequences: Numerical experience. Internat. J, Modern Phys. C, 6(2), 263-275 (1995).
  6. Sobol' I.M. On quasi-Monte Carlo integrations. Mathematics and Computers in Simulation, 47, 103-112 (1998).
  7. Tezuka S. Uniform Random Numbers: Theory and Practice, Kluwer Academic Publishers (1995).
  8. Sobol’ I.M., Asotsky  D., Kreinin  A., Kucherenko S. Construction and Comparison of High-Dimensional Sobol’ Generators, Wilmott, Nov, 64-79 (2012).

SobolSeq software packages are implementations of the 32- and 64-bit 32768 and 65536 dimensional Sobol' sequences with modified direction numbers (standard and scrambled versions). Dimension of generated LDS can be up to and including 65536. 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, S-Plus and Python.

To get your FREE non-commercial version of SobolSeq, please go to the Download section.