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

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

Higher order nets and a higher order Sudoku

In the following we first describe a connection of $(t,m,s)$-nets and Sudoku and then generalize the Sudoku in analogy to higher order $(t,\alpha, \beta, m, n, s)$-nets in base 3. A new type of Sudoku puzzle is presented at the end. 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

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