Probabilistic discrepancy bound for Monte Carlo point sets.

Christoph Aistleitner, Markus Hofer

Research output: Contribution to journalArticlepeer-review

Abstract

Abstract. By a profound result of Heinrich, Novak, Wasilkowski, and Wo´znia-
kowski the inverse of the star-discrepancy n∗(s, ε) satisfies the upper bound
n∗(s, ε) ≤ cabssε−2. This is equivalent to the fact that for any N and s
there exists a set of N points in [0, 1]s whose star-discrepancy is bounded by
cabss1/2N −1/2. The proof is based on the observation that a random point
set satisfies the desired discrepancy bound with positive probability. In the
present paper we prove an applied version of this result, making it applicable
for computational purposes: for any given number q ∈ (0, 1) there exists an
(explicitly stated) number c(q) such that the star-discrepancy of a random set
of N points in [0, 1]s is bounded by c(q)s1/2N −1/2 with probability at least q,
uniformly in N and s
Original languageEnglish
Pages (from-to)1373-1381
JournalMathematics of Computation
Volume83
Issue number287
DOIs
Publication statusPublished - 2014

Fields of Expertise

  • Sonstiges

Fingerprint

Dive into the research topics of 'Probabilistic discrepancy bound for Monte Carlo point sets.'. Together they form a unique fingerprint.

Cite this