Discrepancy

In this section, we follow Chapter 2 of Niederreiter [#!kn:Niederreiter1992!#], especially pages 14 and 19.

The most important Discrepancy is Star Discrepancy.

Definition 3 (Subintervals anchored at zero)   Consider a unit hypercube in s dimensions. Suppose that in each dimension i, the i-th dimension's coordinate is greater than or equal to 0 and less than or equal to $u_i$. A set of points satisfying these inequalities is a type of sub-interval of the unit hypercube.

Definition 4 (Star Discrepancy)   Consider a unit hypercube in s dimensions. Consider the sub-intervals anchored at zero, and let B be such a sub-interval. For N points, let P be the set $x_1,...,x_N$. Let A(B,P) be the number of points of P in the sub-interval B. The Star Discrepancy is

$$D_N^{*}(P) = sup \vert\frac{A(B,P)}{N} - \lambda_s(B)\vert$$ (2.1)

where $\lambda_s(B)$ is the volume of the sub-interval B.

When we use the term discrepancy, we shall mean Star Discrepancy unless the sense indicates otherwise.