We study the
Lp-discrepancy of random point sets in high dimensions, with emphasis on small values of
p. Although the classical
Lp-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 \emph{generalized}
Lp-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
Fd,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
L1-discrepancy for deterministic point sets.