Random sets are close to low-discrepancy sets

Abstract

A random sample typically has star discrepancy of order n^{-1/2}, while carefully constructed point sets can achieve discrepancy nearly n^{-1}. We show that these two regimes are much closer than they appear. For any probability measure, one can move only a small fraction of the points of an iid sample and obtain an n-point set with nearly optimal star discrepancy relative to the original measure. The proof gives an explicit online procedure based on multiscale balancing. This is joint work with Roman Vershynin.