TL;DR
This paper establishes a fundamental lower bound for the star discrepancy of random point sets, proving that their expected discrepancy is at least proportional to $\sqrt{s/N}$, where $s$ is the dimension and $N$ is the number of points. This result demonstrates that random point sets are asymptotically optimal in terms of discrepancy for high-dimensional spaces, a significant finding for numerical integration and related fields.
What Problem Does This Paper Address?
The paper tackles a long-standing open problem in discrepancy theory: finding a lower bound for the star discrepancy of a random point set. Discrepancy theory is concerned with how uniformly a set of points is distributed within a given space, typically the unit cube $[0,1]^s$. A low discrepancy means the points are well-distributed, which is crucial for applications like quasi-Monte Carlo integration, where it directly impacts the accuracy of numerical approximations.
While there are known constructions of point sets with very low discrepancy (often achieving bounds like $O(\frac{(\log N)^{s-1}}{N})$ for fixed $s$), and even for high dimensions ($O(\sqrt{s/N})$), the question of how well random point sets perform has been less clear. Previous work showed that random sets can achieve good upper bounds (meaning their discrepancy is at most $O(\sqrt{s/N})$ with high probability), but a matching lower bound was missing. This paper provides that missing piece, showing that random sets are not just "good enough" but are, in a fundamental sense, as good as the best known constructions for high dimensions.
Methods
The core of the proof relies on a probabilistic argument using a lemma about binomial distributions. The authors define a signed discrepancy measure called "excess" for a given box. They then construct a sequence of nested boxes, starting from the full unit cube, by iteratively shrinking one dimension at each step.
The key idea is to show that at each step, with a certain probability, the process can create a box with a significantly larger excess of points than expected. This is achieved by leveraging a lemma (Lemma 2) that bounds the deviation of a binomial random variable from its mean. Specifically, Lemma 2 states that for a binomial distribution with parameters $n$ and $p$ (where $p$ is small), the probability of observing a value significantly below the mean is bounded. By applying this lemma iteratively, the authors show that a box with a large positive excess can be constructed with non-negligible probability. The proof then uses a Chernoff bound to argue about the expected number of such "successful" shrinking steps, leading to the final lower bound.
Datasets
Not discussed in the paper. The paper deals with theoretical properties of randomly generated point sets, not empirical evaluation on specific datasets.
Key Insights and Ideas
- Randomness is Optimal (Asymptotically): The most striking insight is that random point sets, despite their simplicity, achieve the best possible asymptotic discrepancy behavior in high dimensions, matching the best known deterministic constructions. This suggests that for many practical purposes, simply sampling points uniformly at random is a highly effective strategy.
- Binomial Deviations are Powerful: The proof's reliance on a lemma about binomial distribution deviations highlights the power of these probabilistic tools in analyzing geometric and combinatorial problems. The ability to bound how far a random sum can stray from its expected value is key to constructing the "problematic" boxes.
- Iterative Construction: The inductive approach of building a box with a large excess by sequentially refining dimensions is an elegant way to leverage the probabilistic lemma. Each step contributes to the overall excess, and the probability of success at each step is sufficient to guarantee a non-trivial lower bound.
Key Results
The main quantitative result is Theorem 1, which states that for $N$ points chosen independently and uniformly at random from $[0,1]^s$, the expected star discrepancy $E[D^*(P)]$ satisfies:
$E[D^*(P)] \geq K \sqrt{s/N}$
where $K$ is an absolute constant. The probability that the discrepancy is less than $K \sqrt{s/N}$ is bounded by $\exp(-\Theta(s))$. This confirms that the upper bounds of $O(\sqrt{s/N})$ previously established for random point sets are indeed asymptotically tight.
Limitations and Future Work
- Constant Factors: The paper explicitly states that the authors did not focus on finding "good explicit values for the constants" ($K$ in the theorem). Improving these constants would be a natural next step.
- Generalization to Other Discrepancy Notions: The paper focuses on the star discrepancy. Extending these lower bound results to other discrepancy measures (e.g., $L_p$ discrepancies) would be valuable.
- Deterministic Constructions: While random sets are shown to be optimal, the paper doesn't directly address how to construct such optimal sets deterministically, which is a separate, active area of research.
- Fixed Dimension vs. High Dimension: The paper's result is particularly relevant for high dimensions ($s$ growing with $N$ or $s$ being large). The behavior for fixed $s$ and large $N$ is different, where discrepancy bounds are typically better (e.g., $O((\log N)^{s-1}/N)$). This paper's contribution is in the regime where dimension is a significant factor.
Summary updated