Constructing optimal star discrepancy sets

General theory of distribution modulo (1) (11K06) Special sequences (11K31) Pseudo-random numbers; Monte Carlo methods (11K45) Monte Carlo methods (65C05)

Review text

In the present article the authors provide a constructive proof of optimal \(L_\infty\) star discrepancy values in dimension 2 for up to 21 points and up to 8 points in dimension 3. This extends a work of \textit{B. E. White} [Numer. Math. 27, 157--164 (1977; Zbl 0327.65029)] for up to six points in dimension 2 and \textit{G. Larcher} and \textit{F. Pillichshammer} [J. Comput. Appl. Math. 206, No. 2, 977--985 (2007; Zbl 1201.11084)] for two points in arbitrary dimension. It is shown that these optimal sets have a far lower discrepancy that the previous constructed nets.\N\NIn the introduction of the paper the concept of \(L_\infty\) star discrepancy \(d^*_\infty(n,d)\) is reminded and its relationship to the Koksma-Hlawka inequality is discussed. The problems of finding the best discrepancy value \(d^*_\infty(n,d)\) for a given number of points \(n\) in a given dimension \(d\) and explicit constructions of optimal sets minimazing the discrepancy point sets are considered.\N\NIn Theorem 1.1 the optimal \(L_\infty\) star discrepancy values for point sets of size \(1 \leq n \leq 21\) in dimension 2 are given in table form. The proof is constructive and gives the possibility to obtain several sets obtaining these optimal discrepancy values. In Figure 1 such a optimal point set with 21 points is given. In Figure 2 visualizations of the local discrepancy values over \([0,1)^2\) for the 12-point Fibonacci net and the first 12 points of the Sobol' net are presented.\N\NIn Section 2 a formula in explicit form for the \(L_\infty\) star discrepancy of an arbitrary net is presented. In Lemma 2.1 \(P\) is an arbitrary point net with \(n\) points in \([0,1)^d\). It is shown that if \(d=2\) and \(n \geq 4\), or \(d \geq 3\) and \(n \geq 3\), then the \(L_\infty\) star discrepancy of the net \(P\) satisfies the lower bound \(d^*_\infty(P) \geq \frac{1}{n}\).\N\NIn Definition 2.2 the concept of the so-called admissible \((j,i,\delta)\)-shift of the points of the nets is given.\N\NIn Lemma 2.3 \(P\) is an arbitrary net of \(n\) points in \([0,1)^d\) and \(s_{j,i,\delta}(P)\) is the set obtained after an admissible \((j,i,\delta)\)-shift of \(P\). Then, the inequality \(d^*_\infty(P) \geq d^*_\infty(s_{j,i,\delta}(P))\) is proved.\N\NIn Section 3.1 the proof of Theorem 1.1 is realized. In Section 3.2 the concept of the nonlinear programming model is developed. In Section 3.3 the possibility to obtain lower and upper bounds of the \(L_\infty\) star discrepancy for higher \(n\) is commented. Such bounds are provided in Table 2. In Figure 3 the truncated local discrepancies for \(n=12\) of the Fibonacci and Sobol' nets are presented.\N\NIn Section 4 some possible extensions of the obtained results are discussed. In Section 4.1 results related with the optimal \(L_\infty\) star discrepancy in dimension 3 are developed. In Section 4.2 other discrepancy notions as the periodic and extreme discrepancy are discussed. In Theorem 4.2 the optimal multiple-corner discrepancy values \(d^{4c}_\infty(n,d)\) of point sets of size \(1 \leq n \leq 18\) in dimension 2 are presented in table form. These values also are graphically illustrated.

Cites work

Cited in

(1)

Robust high-dimensional non-parametric representative points via density-guided clustering

This page was built for publication: Constructing optimal star discrepancy sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6975749)