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?


That's the right way to think about it. Or to give discrepancy another interpretation: it measures the degree to which you can misrepresent the density by averaging over a subset of some prescribed type. Even if your points are evenly spread out, you can still misrepresent the density to some nonzero extent.

By the way, your example actually has a larger discrepancy:

  • 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.