# Is it expected that uniform points would have non zero discrepancy?

Let's say that I have a single point at $(0.5,0.5)$.

The single data point is uniformly distributed in the unit square so I would sort of expect it to have zero discrepancy. (related: How to calculate discrepancy of a sequence)

However, if we calculate it, we get a non zero result, because for instance the half open region $[(0.0, 0.0), (0.5, 0.5))$ contains no points and has an area of 0.25.

Is it expected that a uniformly distributed data set wouldn't have a discrepancy of zero?

My best guess is that yes this is expected because discrepancy compares area vs density which are both continuous values, while specific data points are discrete.

Is this correct / the correct thinking?

• If only rectangles with one corner at the origin are allowed, we can get $0.5$: the half-open rectangle $[0,1) \times [0,0.5)$ also contains no points, but has an area of $0.5$, for a discrepancy of $0.5$.
• If we allow arbitrary rectangles, we can get arbitrarily close to $1$: the half-open rectangle $[0.5, 0.5+\epsilon) \times [0.5, 0.5+\epsilon)$ contains $1$ point and an area of $\epsilon^2$, for a discrepancy of $1-\epsilon^2$.
Finally, in two or more dimensions, you shouldn't think of a regular grid pattern as being "uniform": it does not even have particularly low discrepancy! Arranging $N$ points in a $2$-dimensional grid achieves a discrepancy of $\mathcal O(\sqrt N)$ in either interpretation: we can exploit either the long and thin gaps between the points, or the fact that we can put a rectangle of near-zero area around $\sqrt N$ collinear points. This is still better than a random arrangement, but it's possible to achieve a discrepancy of $\mathcal O(\log N)$ by a more clever arrangement of points.