Polynomial discrepancy of sequences

DOI10.1016/S0377-0427(97)00117-9MaRDI QIDQ1372100zbMATH OpenFDO

Authors Bernhard Klinger, Robert F. Tichy

Publication date 17 March 1999

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0377-0427(97)00117-9

zbMATH Keywords

polynomial discrepancy of a point set quasi-Monte Carlo methods spherical cap discrepancy

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45)

Review text

Let \((x_n)^\infty_{n= 1}\) be a sequence of points \(x_n= (x^{(1)}_n,\dots, x^{(k)}_n)\in [0,1)^k\), where \(k\geq 1\). We define \[ P_n= \underset{(m_1,\dots, m_k)\in\mathbb{N}^k}{\text{Sup}} \Biggl|{1\over N} \sum^N_{n= 1} (x^{(1)}_n)^{m_1}\cdots (x^{(k)}_n)^{m_k}- \prod^k_{j= 1} {1\over m_j+1}\Biggr|, \] which was first introduced by Hlawka and called the polynomial discrepancy of a point set \(X_N= \{x_1,\dots, x_N\}\). In his paper [Sitzungsber., Abt. II, Österr. Akad. Wiss., Math.-Naturwiss., Kl. 193, 513-519 (1984; Zbl 0564.10052)], \textit{R. F. Tichy} proved that \(P_N\leq D_N\leq c_k\left(\log{1\over P_N}\right)^{-1}\), where \(D_N\) is the usual discrepancy of \(X_N\), and \(c_k\) is a constant depending only on \(k\). This result is best possible in the case \(k=1\). In the present paper, the authors prove that for any \(k\geq 1\) and any \(\varepsilon>0\), there exists an integer \(N\) and a set \(X_N\subset [0,1)^k\) such that \[ P_N< \varepsilon\quad\text{and}\quad D_N> c^*_k\Biggl(\log{1\over P_N}\Biggr)^{-k} \] with a constant \(c^*_k\) depending only on \(k\). Furthermore, an analogue \(D^S_N\) of the polynomial discrepancy for points on a unit sphere \(S^d\) is introduced, and the relation between \(D^S_N\) and \(D^C_N\) (the spherical cap discrepancy) is given. Finally, the corresponding computational results are also provided.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Polynomial discrepancy of sequences

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