Title:

Quasi-Monte Carlo integration and pseudo-random generators

Partners

·          Slovak Academy of Sciences, Mathematical Institute, Bratislava (O. Strauch)

·          Slovak University of Technology, Faculty of Chemical and Food Technology, Department of Inform. Eng. and Process Kontrol, Bratislava (V. Baláž)

·          Bulgarian Academy of Sciences, Institute of Mathematics and Informatics, Sofia, Bulgaria (S.S. Stailova)

·          South West University “Neophit Rilsky” , Faculty of Natural Sciences and Mathematics, Department of Mathematics , Blagoevgrad, Bulgaria (V. Grozdanov)

Date: 2009-2010

Anotation:

We shall try to find a new error term in the numerical integration in the high dimension, discrepancy and diaphony of some new types of nets, some new combination of pseudo-random generators and a new concept of densities for natural numbers.

Keywords:

Uniform distribution theory, quasi-Monte Carlo integration, random number generators, nets, discrepancy and diaphony, densities for natural number.

Goals of project:

We shall try to find a new error term in the numerical integration in the high dimension, discrepancy and diaphony of some new types of nets, some new combination of pseudo-random generators and  a new concept of densities for natural numbers.

The aim of the project in the narrow international cooperation is to find new results in the theory of uniformly distributed sequences which began in 1916 with the pioneering paper of H. Weyl. Up to now there are 8 basic monographs, for instance:

[KN] K. Kuipers-H. Niederreiter: Uniform Distribution of Sequences (1974);

[DT] M.Drmota-R.F.Tichy: Sequences, Discrepancies and Applications (1996);

[SP] O.Strauch-Š.Porubský: Distribution of Sequences; A Sampler (2005).

The main result of this theory is a transformation of Monte Carlo methods to the quasi-Monte Carlo method. For example in the numerical integration the Monte Carlo method gives only probabilistic error term, but in the quasi-Monte Carlo method the error term is given as a product V(f)D_N of Hardy-Krause variation V(f) of integrable function f(x) and D_N is the discrepancy of the used deterministic sequence x_n, see the Koksma-Hlawka theorem [SP, p. 1-66]. Also in other applications of Monte Carlo method the random sequence can be replaced by deterministic pseudo-random sequence.

A random numbers is a physical process of measurement in which any further measurement is statistically independent. Generator of pseudo-random numbers is exactly defined algorithm by means of which we compute the sequence so called pseudorandom number sequence, thus it is deterministic. The quality of such sequences is measured e.g. by discrepancies of couples, triples, etc. The most important pseudorandom sequences are congruential  (linear, quadratic , power ). The (t, m, s) - nets on base b are an example of nets with very good distribution of their points in [0, 1) ^s. Practically, all concrete constructions of (t, m, s)-nets on base b are based on the general scheme of construction of “ digital point nets”. Larcher, Niederreiter and Schmid [LNS] Digital nets and sequences constructed over finite rings and their applications to quasi-Monte Carlo integration, Monatsh. Math. 121 (1996) 231-253 introduce common algebraic methods of constructing digital (t, m, s)-nets over finite  groups and ring.  Owen [O] Monte Carlo variance of scrambled net quadrature, SIAM J. Numer. Anal. 34 (5) (1997), 1884-1910 announces one more class of well-distributed nets – the so-called (λ, t, m, s)-nets on base b. An effective analytical algorithm of constructing digital (λ, t, m, s)-sets is shown. Recently Dick  [D] Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order (in press) defines special digital nets, the so-called (t,α,β,σ.n,m,s)-nets over Z_{b} and uses these nets in quasi-Monte Carlo integration in Sobolev spaces.

The density on the set of natural numbers is every nonnegative measure. The basic density is the asymptotic density which is used in the definition of uniformly distributed sequences. Further we have Buck density, logarithmic density weight density, density with respect to summation methods, specially, densities with respect to matrix summation methods. There is also known Abel density, zeta density, Schnirelman density. Using these densities, it is possible to define different types of uniform distributions. By means of density we can define also convergence. This is a special case of the so-called I–convergence with respect to ideal I of null sets. In this way we can define the statistical convergence, the uniform convergence with respect to a density. Further types of convergences are almost convergence, strong p–Ceasaro convergence, φ–convergence and so on. Between sets of all convergent sequences are studied some inclusion and Baire category.

In this project we shall deal with the following problems:

1. The Koksma-Hlawka theorem with low discrepancy sequences is do not appropriate for quasi-Monte Carlo integration for a large dimension. For this we shall study sequences where discrepancy-bounds depend on square of dimension (see S. Heinrich, E. Novak, G.W. Wasilkowski and Wozniakowski [Acta Arith. 96(2001), no. 3, 279--302; MR1814282(2002b:11103)]). Also study some reduction of dimension of integrable f(x).  

2. We shall study special low discrepancy sequences called (t,m,s)-nets (cf. [SP,1-23]) to obtain an upper estimation of the weighted b-adic diaphony (cf. [SP, p. 1-75]).

3. Combining pseudo-random sequences, our problem is to find new pseudorandom generators. First we shall combine  quadratic generator with the van der Corput sequence (it  is not pseudo-random).  

4. Our aim is to find new relations among uniformly distributed sequences with respect to different densities and also to find new relations among different types of sets of convergent sequences.