Error Bounds for quasi-Monte Carlo integration with nets

We analyze the error introduced by approximately calculating the -dimensional Lebesgue measure of a Jordan-measurable subset of . We give an upper bound for the error of a method using a -net, which is a set with a very regular distribution behavior. When the subset of is defined by some function of bounded variation on , the error is estimated by means of the variation of the function and the discrepancy of the point set which is used. A sharper error bound is established when a -net is used. Finally a lower bound of the error is given, for a method using a -net. The special case of the 2-dimensional Hammersley point set is discussed.

     

Error bounds for quasi-Monte Carlo integration with uniform point sets

We establish new error bounds for quasi-Monte Carlo integration for node sets with a special kind of uniformity property. The methods of proving these error bounds work for arbitrary probability spaces. Only the bounds in terms of the modulus of continuity of the integrand require also the structure of a metric space.     

The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation.

Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor is bounded by for some exponent and some positive constant . The -exponent of tractability is defined as the smallest power of in these bounds. It is shown by using Monte Carlo quadrature that the -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.

     

Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights

We study the problem of constructing shifted rank-1 lattice rules for the approximation of high-dimensional integrals with a low weighted star discrepancy, for classes of functions having bounded weighted variation, where the weighted variation is defined as the weighted sum of Hardy–Krause variations over all lower-dimensional projections of the integrand. Under general conditions on the weights, we prove the existence of rank-1 lattice rules such that for any δ>0, the general weighted star discrepancy is O(n^−1+δ) for any number of points n>1 (not necessarily prime), any shift of the lattice, general (decreasing) weights, and uniformly in the dimension. We also show that these rules can be constructed by a component-by-component strategy. This implies in particular that a single infinite-dimensional generating vector can be used for integrals in any number of dimensions, and even for infinite-dimensional integrands when they have bounded weighted variation. These same lattices are also good with respect to the worst-case error in weighted Korobov spaces with the same types of general weights. Similar results were already available for various special cases, such as general weights and prime n, or arbitrary n and product weights, but not for the most general combination of n composite, general weights, arbitrary shift, and star discrepancy, considered here. Our results imply tractability or strong tractability of integration for classes of integrands with finite weighted variation when the weights satisfy the conditions we give. These classes are a strict superset of those covered by earlier sufficient tractability conditions.     

Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension

In a celebrated construction, Chen and Skriganov gave explicit examples of point sets achieving the best possible _L2$L_2$-norm of the discrepancy function. We consider the discrepancy function of the Chen–Skriganov point sets in Besov spaces with dominating mixed smoothness and show that they also achieve the best possible rate in this setting. The proof uses a b$b$-adic generalization of the Haar system and corresponding characterizations of the Besov space norm. Results for further function spaces and integration errors are concluded.     

Fast algorithms for component-by-component construction of rank- lattice rules in shift-invariant reproducing kernel Hilbert spaces

We reformulate the original component-by-component algorithm for rank- lattices in a matrix-vector notation so as to highlight its structural properties. For function spaces similar to a weighted Korobov space, we derive a technique which has construction cost , in contrast with the original algorithm which has construction cost . Herein is the number of dimensions and the number of points (taken prime). In contrast to other approaches to speed up construction, our fast algorithm computes exactly the same quantity as the original algorithm. The presented algorithm can also be used to construct randomly shifted lattice rules in weighted Sobolev spaces.