Discrepancy theory measures how evenly a finite configuration or coloring can satisfy many constraints at once. For a finite set and a family of subsets, its two-color discrepancy isThe sum is the difference between the two color counts in . A single balanced total does not guarantee small discrepancy on every constrained subset.
If and contains all contiguous intervals, alternating the colors gives discrepancy at most one: each even-length interval has equal counts, and each odd-length interval differs by one. Singleton constraints show that one is optimal. More complicated overlapping families can force much larger imbalance.
A related geometric formulation compares point counts in test regions with their expected volume. Star discrepancy uses boxes anchored at the origin. Such bounds quantify how well a deterministic point set approximates uniform integration, linking combinatorics with numerical integration.
Discrepancy theory is a branch of mathematics and statistical theory that deals with the differences or discrepancies between two or more sets of data, distributions, or mathematical objects. It is often concerned with quantifying how much two sets differ from each other, which can be particularly useful in various fields such as statistics, optimization, and machine learning.
New to topics? Read the docs here!