Discrepancy Bounds for Mixed Sequences

Multi-Version Program Analysis

计算机科学;物理学

Michael Gnewuch

Others  :  http://drops.dagstuhl.de/opus/volltexte/2009/2297/pdf/09391.GnewuchMichael.ExtAbstract.2297.pdf
PID  :  6411

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

A common measure for the uniformity of point distributions is the star discrepancy. Letλ_s denote the s-dimensional Lebesgue measure. Then the star discrepancy of a multiset P = {p1, . . . , pN} ⊂[0, 1]~s is given byND* _N(P) := sup |λ_s([0, α)) −1/NΣ 1_[0,α)(pk)| ;α[0,1]~s k=1 here [0, α) denotes the s-dimensional axisparallel box [0, α_1) × • • • × [0, α_s) and 1[0,α) its characteristic function. For an infinite sequence p in [0, 1]s we denote by D ~*_N (p) the discrepancy of its first N points. The smallest star discrepancy of any N-point set isD* (N, s) := infD~*_ N(P),P⊂ [0,1]~s , |P|=Nand the inverse of the star discrepancy is given byN *(ε, s) := inf{N ∈ N|D* (N, s) ≤ε}.There are bounds known describing the behavior of the star discrepancy in the number of points N and in the dimension s, see, e.g., [5, 2]. In [5] Heinrich, Novak, Wasilkowski, and Wozniakowski provedD* (N, s)≤ C√(s/N) and N (ε , s)≤ ⌈C~2sε~(−2)⌉, (1)where the constant C does not depend on N, s or ε. The dependence of the inverse of the star discrepancy on s is optimal here; this was proved by a lower bound in , which was improved by Hinrichs in: There exist constants c, ε_0 > 0 such thatD* (N, s)≥ min{ε_0, cs/N} and N (ε, s)≥ csε~(−1) for all ε∈ (0, ε_0). (2)