Category Archives: Research

Here are posts on my research.

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

Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo

Recently we uploaded the paper

In a sense, this paper is an extension of the paper

In this paper we prove bounds on the discrepancy of Markov chains which are generated by a deterministic driver sequence u_1, u_2, \ldots, u_n \in [0,1]^s. We also prove a Koksma-Hlawka inequality. The main assumption which we use is uniform ergodicity of the transition (Markov) kernel. We describe the essential ingredients and results in the following. Continue reading

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

http://roth.cs.kuleuven.be/

This page is currently hosted at the Katholieke Universiteit Leuven.

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

Some possible simplifications of the notation of higher order nets and sequences

In this entry I discuss the definition of (digital) higher order nets and sequences and some possible simplifications of the notation.

Digital higher order nets and sequences have been introduced in

whereas higher order nets have been introduced in

  • [2] J. Dick and J. Baldeaux, Equidistribution properties of generalized nets and sequences. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 305–323, 2009. doi: 10.1007/978-3-642-04107-5_19 An earlier version can be found here.

There are several parameters occurring in the definition of higher order nets, namely t, \alpha,\beta, n, m, s, b and for higher order sequences we have the parameters t, \alpha, \beta, \sigma, s, b.

(Digital) higher order nets and sequences are point sets \{\boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1}\} \subset [0,1)^s and sequences \{\boldsymbol{x}_0,\boldsymbol{x}_1, \ldots, \} such that

\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} - \frac{1}{N} \sum_{n=0}^{N-1} f(\boldsymbol{x}_n) \right| = \mathcal{O} (N^{-\alpha} (\log N)^{\alpha s}),

where {}N =b^m is the number of quadrature points and {} \alpha is the smoothness of the integrand {}f. Continue reading

Korobov discovered the component-by-component construction of lattice rules in 1959

Alexey Ustinov recently pointed out that Korobov invented the component-by-component construction of lattice rules in 1959. He provided two references for this result, namely

  • @article {MR0104086,
        AUTHOR = {Korobov, N. M.},
         TITLE = {Approximate evaluation of repeated integrals},
       JOURNAL = {Dokl. Akad. Nauk SSSR},
      FJOURNAL = {Doklady Akademii Nauk SSSR},
        VOLUME = {124},
          YEAR = {1959},
         PAGES = {1207–1210},
    }
  • Theorem 18 on page 120 in Korobov’s book from 1963:

    @book {MR0157483,
    AUTHOR = {Korobov, N. M.},
    TITLE = {Teoretiko-chislovye metody v priblizhennom analize},
    PUBLISHER = {Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow},
    YEAR = {1963},
    PAGES = {224},
    }

In this post I provide a (rough) translation of the results of Korobov (I do not know Russian, so I only understand the formulae). Indeed, as can be seen below, Korobov used the algorithm which is now called component-by-component construction (and which was re-invented much later by Sloan and Reztsov in Sloan, I. H.; Reztsov, A. V. Component-by-component construction of good lattice rules. Math. Comp. 71 (2002), no. 237, 263–273). He also proved that lattice rules constructed component-by-component achieve the optimal rate of convergence of the integration error for functions in the class E^\alpha_s (i.e., he showed that P_\alpha = \mathcal{O}(p^{-\alpha} (\ln p)^{\alpha s}) where {}p is the number of quadrature points).

Unfortunately many authors were not aware of Korobov’s result, hence Korobov has not received due credit for this result. To rectify this situation somewhat (and help make authors aware of Korobov’s result), we provide the details of Korobov’s result here. Continue reading