Upper bounds for generalized Lp-discrepancy of random points

We study the L p -discrepancy of random point sets in high dimensions, with emphasis on small values of p . Although the classical L p -discrepancy suffers from the curse of dimensionality for all p ∈ ( 1 , ∞ ) , the gap between known upper and lower bounds remains substantial, in particular for small p ≥ 1 . To clarify this picture, we review the existing results for i.i.d. uniformly distributed points and derive new upper bounds for generalized L p -discrepancies, obtained by allowing non-uniform sampling densities and corresponding non-negative quadrature weights. Using the probabilistic method, we show that random points drawn from optimally chosen product densities lead to significantly improved upper bounds. For p = 2 these bounds are explicit and optimal; for general p ∈ [ 1 , ∞ ) we obtain sharp asymptotic estimates. The improvement can be interpreted as a form of importance sampling for the underlying Sobolev space F d , q . Our results also reveal that, even with optimal densities, the curse of dimensionality persists for random points when p ≥ 1 , and it becomes most pronounced for small p . This suggests that the curse should also hold for the classical L 1 -discrepancy for deterministic point sets.