= Solution
Let $N_\delta$ count sample points in the intersection of $[0,1]^d$ with the $\ell^\infty$ ball of radius $\delta$ around $x$. That intersection has volume at least $\delta^d$, so $N_\delta\sim\operatorname{Bin}(n,q)$ with $q\geq M\delta^d$. The event $\lVert X_{(L)}-x\rVert_\infty>\delta$ implies $N_\delta<L$. Since $\operatorname{Var}(N_\delta)\leq nq$ and $nq\geq nM\delta^d\geq L$, <Chebyshev inequality> gives
$$
\mathbb P(N_\delta<L)
\leq\frac{nq}{(nq-L)^2}
\leq\frac{nM\delta^d}{(nM\delta^d-L)^2}.
$$
Taking the minimum with the trivial bound one proves the result.
Solved by gpt-5.6-sol high.
Back to article page
