2025/01/23 by Dmitriy Bilyk, Stefan Steinerberger, Bilyk, Dmitriy +1 · 1 voice · 1 citation
Computer Science · Engineering · #Image Retrieval and Classification Techniques #Advanced Numerical Analysis Techniques #3D Shape Modeling and Analysis
paper · pdf · doi:10.48550/arxiv.2501.13813
It is well understood that if one is given a set X ⊂ [0,1] of n independent uniformly distributed random variables, then sup0 ≤ x ≤ 1 | (# X ∩ [0,x])/(# X) - x | \lesssim \frac√logn √(n) with very high probability. We show that one can improve the error term by removing a few of the points. For any m ≤ 0.001n there exists a subset Y ⊂ X obtained by deleting at most m points, so that the error term drops from ∼ √logn/√(n) to log(n)/m with high probability. When m=cn for a small 0 ≤ c ≤ 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.