It is well understood that if one is given a set \(X \subset [0,1]\) of n independent uniformly distributed random variables, then \(\begin{aligned} \sup _{0 \le x \le 1} \left| \frac{\# X \cap [0,x]}{\# X} - x \right| \lesssim \frac{\sqrt{\log {n}}}{ \sqrt{n}} \qquad \text{ with } \text{ high } \text{ probability. } \end{aligned}\) We show that one can improve the error term by removing a few of the points. For any \(m \le 0.001n\) there exists a subset \(Y \subset X\) obtained by deleting at most m points, so that the error term drops from \(\sim \sqrt{\log {n}}/\sqrt{n}\) to \( \log {(n)}/m\) with high probability. When \(m=cn\) for a small \(0 \le c \le 0.001\) , this achieves the essentially optimal asymptotic order of discrepancy \(\log (n)/n\) . The proof is constructive and works in an online setting (where one is given the points sequentially, one at a time, and has to decide whether to keep or discard it). A change of variables shows the same result for any random variables on the real line with absolutely continuous density.
