# Category Archives: Quasi-Monte Carlo

Research on quasi-Monte Carlo

## Digital Nets and Sequences Preprint

A complete preprint of the book

is now available here. The final published version can be obtained directly from Cambridge University Press here.

The preprint version differs of course from the final version, for instance, the page numbers are different. However, the numbering of Chapters, Sections, Theorems, Lemmas, Corollaries, Definitions and Examples is the same in both versions. The list of corrections is for the published version. We do not have a separate list for the preprint version (though the corrections for the published version also apply to the preprint version).

## New: MCQMC Wiki page

Thanks to the hard work of Dirk Nuyens and the support of Ronald Cools, there is now a Wiki page for the Monte Carlo and quasi-Monte Carlo community at

If you would like to contribute, please sign up with your true name at http://roth.cs.kuleuven.be/w-mcqmc/index.php?title=Special:UserLogin&returnto=Main_Page. After logging in, you can update information, contribute new pages and generally help to make the MCQMC Wiki a success.

## Sobol’s book from 1969

Recently a colleague forward me an email with a link to a scanned copy of Sobol’s book from 1969. The link is:

http://www.regmed.ru/getfile.asp?CatId=db&Name=IMSobol_1969_book.pdf The book can be cited using:

• @preamble{
“\def\cprime{$’$} ”
}
@book {Sobol1969,
AUTHOR = {{{\cyr{T}}sobol{\cprime}, I. M.}},
TITLE = {Mnogomernye kvadraturnye formuly i funktsii {K}haara},
PUBLISHER = {Izdat. “Nauka”, Moscow},
YEAR = {1969},
PAGES = {288}
}

The english translation of the book title is ‘Multidimensional quadrature formulae and Haar functions’.

Update 01/12/2010: Professor Sobol provided a response which is added at the end of this entry. Continue reading

## QMC rules over R^s: Matlab code and numerical example

In this post you can find a Matlab code for constructing digital nets on $\mathbb{R}^s$ which was recently proposed in J. Dick, Quasi-Monte Carlo numerical integration on $\mathbb{R}^s$: digital nets and worst-case error. Submitted, 2010. See the previous post where an explanation of the method and a link to the paper can be found. In the numerical example we consider a simple three-dimensional integral. In this example the computation time with the new method is reduced by a factor of ten and additionally the integration error is also reduced. The numerical result in the paper shows that, for the example considered there, that the computation time can be reduced from two and a half minutes to less than two seconds for a certain given error level. Continue reading

## Higher order scrambling

This paper deals with a generalization of Owen’s scrambling algorithm which improves on the convergence rate of the root mean square error for smooth integrands. The bound on the root mean square error is best possible (apart from the power of the $\log N$ factor) and this can also be observed from some simple numerical examples shown in the paper (note that the figures in the paper show the standard deviation (or root mean square error) and not the variance of the estimator). In this post you can also find Matlab programs which generate the quadrature points introduced in this paper and a program to generate the numerical results shown in the paper. Continue reading

## How to generate higher order Sobol points in Matlab and some numerical examples

Higher order digital nets and sequences are quasi-Monte Carlo point sets $\{\boldsymbol{x}_{n-1}\}_{n=1}^N,$ where $N=b^m$ for digital nets and $N=\infty$ for digital sequences (for more background information on this topic see Chapters 1-4 and Chapter 8 in the book; several sample chapters of this book can be downloaded here), which satisfy the following property:

$\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \, \mathrm{d} \boldsymbol{x} - \frac{1}{b^m} \sum_{n=0}^{b^m-1} f(\boldsymbol{x}_n) \right| \le C_{s,\alpha} \frac{(\log N)^{s \alpha}}{N^\alpha}, \hspace{2cm} (1)$

where $\alpha \ge 1$ is the smoothness of the integrand ${}f$ and $C_{s,\alpha} \textgreater 0$ is a constant which only depends on ${}s$ and ${}\alpha$ (but not on ${}N).$ For instance, if ${}f$ has square integrable partial mixed derivatives up to order ${}2$ in each variable, then we get a convergence rate of $\mathcal{O}(N^{-2+\varepsilon}),$ where ${}N$ is the number of quadrature points used in the approximation and $\varepsilon >0$ can be chosen arbitrarily small. If ${}f$ has ${}3$ derivatives then we get a convergence of $\mathcal{O}(N^{-3+\varepsilon}),$ and so on.

This method has been introduced in the papers:

The first paper only deals with periodic functions, whereas the second paper also includes nonperiodic functions.

For some heuristic explanation how higher order digital nets and sequences work see the paper:

• J. Dick, On quasi-Monte Carlo rules achieving higher order convergence. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 73–96, 2009. doi: 10.1007/978-3-642-04107-5_5 An earlier version can be found here.

In this entry we provide a Matlab program which generates point sets which satisfy the property (1). Continue reading

## The connection between the logarithmic Walsh degree of exactness, the t value of digital nets and an idea for future research

In this entry we show how the Walsh degree of a digital net is connected to its t value. This can lead to future research by using ideas developed for finding lattice rules with large trigonometric degree. Continue reading