= Star discrepancy
{title2=$D_N^*$}
For points $x_1,\ldots,x_N$ in $[0,1)^d$, star discrepancy compares their empirical frequencies in anchored boxes with <Lebesgue measure>:
$$
D_N^*=\sup_{u\in[0,1]^d}\left|\frac1N\sum_{i=1}^N\mathbf1_{x_i\in[0,u)}-\prod_{j=1}^du_j\right|,
\qquad [0,u)=\prod_{j=1}^d[0,u_j).
$$
The half-open box convention makes boundary membership precise. Small <star discrepancy> means that every such box contains nearly its uniform share of points; it does not mean the points are independent random samples.
In one dimension, take midpoint points $x_i=(i-1/2)/N$. Between consecutive points, the empirical count is constant while the interval length increases linearly. Just before or after a point the largest difference is $1/(2N)$, so $D_N^*=1/(2N)$. Repeating a single point instead leaves large gaps and large discrepancy. The definition directly controls the integration error for indicators of anchored boxes and motivates deterministic sampling for <numerical integration>.
Back to article page
