Comparing Halton and Sobol Sequences in Integral Evaluation

  • Nadia A. Mohammed Department of Mathematics, College of Basic Education, University of Duhok, Kurdistan Region, Iraq
Keywords: Halton sequence Monte Carlo Quasi-Monte Carlo Sobol sequence

Abstract

        Halton and Sobol sequences are two of the most popular number sets used in quasi-Monte Carlo methods.  These sequences are effectively used instead of pseudo random numbers in the evaluation of integrals. In this paper, the two sequences are compared in terms of the size of the number sets and dimensionality. The comparison is implemented with matlab programming for evaluating numerical integrals. The absolute error, which is the absolute difference between the exact and estimated errors, is plotted against dimensions for different functions. The practical results show that, except the first dimension, Sobol sequence is better than Halton sequence. The results also show that Sobol sequence outputs are more stable.

References

Bratley, P. & Fox, B.L., 1988. Algorithm 659: Implementing Sobol’s quasirandom sequence generator. ACM Transactions on Mathematical Software (TOMS), 14(1), 88–100.
Caflisch, R.E., 1998. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica, 7, 1–49.
Dalal, I.L., Stefan, D. & Harwayne-Gidansky, J., 2008. Low discrepancy sequences for Monte Carlo simulations on reconfigurable platforms. In 2008 International Conference on Application-Specific Systems, Architectures and Processors. 108–113.
Frey, R., 2008. Monte Carlo methods: with application to the pricing of interest rate derivatives. University of St. Gallen. (Doctoral dissertation)
Jank, W., 2005. Quasi-Monte Carlo sampling to improve the efficiency of Monte Carlo EM. Computational statistics & data analysis, 48(4), 685–701.
Kocis, L. & Whiten, W.J., 1997. Computational Investigations of Low- Discrepancy Sequences. ACM Transactions on Mathematical Software, 23(2), 266–294.
Krykova, I., 2004. Evaluating of Path-Dependent Securities with Low Discrepancy Methods. Worcester Polytechnic Institue. (Doctoral dissertation)
Kuo, F.Y. & Sloan, I.H., 2013. High-dimensional integration : The quasi-Monte Carlo way. Acta Numerica, 22, 133-288.
Landau, D.P. & Binder, K., 2005. A Guide to Monte Carlo Simulations in Statistical Physics 2nd ed., cambridge university press.
Lemieux, C., 2009. Monte Carlo and Qusi-Monte Carlo Sampling, Springer.
Levy, G., 2002. An introduction to quasi-random numbers. Numerical Algorithms Group Ltd., 143.
McLeish, D.L., 2011. Monte Carlo simulation and finance (Vol. 276). John Wiley & Sons.
Morokoff, W.J. & Caflisch, R.E., 1995. Quasi-monte carlo integration. Journal of computational physics, 122(2), 218–230.
Owen, A.B., 2009. Monte Carlo and Quasi-Monte Carlo for Statistics. In Monte Carlo and Quasi-Monte Carlo Methods. Springer Berlin Heidelberg., 3–18.
Serre, L., 2010. A Matlab Program for Testing Quasi-Monte Carlo Constructions. University of Waterloo. (Master dissertation)

Sloan, I.H. & Woźniakowski, H., 1998. When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals? Journal of Complexity, 14(1), 1-33.
Sobol’, I.M., 1967. On the distribution of points in a cube and the approximate evaluation of integrals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 7(4), 784–802.
Tuffin, B., 2008. Randomization of Quasi-Monte Carlo methods for error estimation: survey and normal approximation. Monte Carlo Methods and Applications, 10(3–4), 617–628.
Veach, E., 1997. Robust monte carlo methods for light transport simulation. Stanford University. (Doctoral dissertation)
Published
2019-02-27
How to Cite
Mohammed, N. “Comparing Halton and Sobol Sequences in Integral Evaluation”. ZANCO Journal of Pure and Applied Sciences, Vol. 31, no. 1, Feb. 2019, pp. 32-39, doi:10.21271/ZJPAS.31.1.5.