Exercise: Computing star-discrepancy by hand

The 1-dimensional star-discrepancy of a point set $\mathcal{P} = \{x_1, \ldots, x_N\} \subset [0, 1]$ is

D_N^*(\mathcal{P}) = \sup_{b \in [0, 1]}\left|\frac{|\{x_i \le b\}|}{N} - b\right|.

Tasks

Sort the points $\mathcal{P} = \{0.1, 0.4, 0.6, 0.85\}$ , $N = 4$ . At each sorted value $x_{(k)}$ , compute the empirical CDF $F_N(x_{(k)}) = k/N$ and $F_N(x_{(k)}^-) = (k-1)/N$ . For each $k$ , compute both $|F_N(x_{(k)}) - x_{(k)}|$ and $|F_N(x_{(k)}^-) - x_{(k)}|$ .
Why does the supremum in the discrepancy definition reduce to a finite maximum over these $2N$ quantities? (Think about where the worst box edge can lie.)
Compute $D_4^*(\mathcal{P})$ for this set.
Compare with the first $4$ terms of the 1-dimensional Halton / van der Corput base-2 sequence: $\{0.5, 0.25, 0.75, 0.125\}$ . Compute its star-discrepancy and compare with the random set.
For $N$ large, uniform IID has $D_N^* = O(\sqrt{\log\log N / N})$ while the van der Corput sequence has $D_N^* = O(\log N / N)$ . At $N = 10^6$ roughly how many times smaller is the QMC discrepancy?

For part 2, the discrepancy function $|F_N(b) - b|$ is piecewise affine in $b$ , with jumps at the sample points. Extrema occur at the breakpoints.