Regularizing Random Points by Deleting a Few

Abstract It is well understood that if one is given a set $$X \subset [0,1]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo>⊂</mml:mo> <mml:mo>[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:munder> <mml:mo>sup</mml:mo> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>x</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:munder> <mml:mfenced> <mml:mfrac> <mml:mrow> <mml:mo>#</mml:mo> <mml:mi>X</mml:mi> <mml:mo>∩</mml:mo> <mml:mo>[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mi>x</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>#</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> </mml:mfrac> <mml:mo>-</mml:mo> <mml:mi>x</mml:mi> </mml:mfenced> <mml:mo>≲</mml:mo> <mml:mfrac> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> </mml:mfrac> <mml:mspace/> <mml:mspace/> <mml:mtext>with</mml:mtext> <mml:mspace/> <mml:mspace/> <mml:mtext>high</mml:mtext> <mml:mspace/> <mml:mspace/> <mml:mtext>probability.</mml:mtext> <mml:mspace/> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> </mml:math> We show that one can improve the error term by removing a few of the points. For any $$m \le 0.001n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>0.001</mml:mn> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> there exists a subset $$Y \subset X$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Y</mml:mi> <mml:mo>⊂</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> obtained by deleting at most m points, so that the error term drops from $$\sim \sqrt{\log {n}}/\sqrt{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>∼</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msqrt> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> </mml:mrow> </mml:math> to $$ \log {(n)}/m$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>log</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>/</mml:mo> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> with high probability. When $$m=cn$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>=</mml:mo> <mml:mi>c</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> for a small $$0 \le c \le 0.001$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>c</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>0.001</mml:mn> </mml:mrow> </mml:math> , this achieves the essentially optimal asymptotic order of discrepancy $$\log (n)/n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>log</mml:mo> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> . 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.