This article needs additional citations for verification. (January 2018) (Learn how and when to remove this template message)
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of classical discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one.
Discrepancy theory can be described as the study of inevitable irregularities of distributions, in measure-theoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity.
Discrepancy theory is based on the following classic theorems:
Major open problemsEdit
The unsolved problems relating to discrepancy theory include:
Applications for discrepancy theory include:
- Weyl, Hermann (1 September 1916). "Über die Gleichverteilung von Zahlen mod. Eins" [About the equal distribution of numbers]. Mathematische Annalen (in German). 77 (3): 313–352. doi:10.1007/BF01475864. ISSN 1432-1807. S2CID 123470919.
- József Beck and Tibor Fiala. ""Integer-making" theorems". Discrete Applied Mathematics. 3 (1): 1–8. doi:10.1016/0166-218x(81)90022-6.
- Joel Spencer (June 1985). "Six Standard Deviations Suffice". Transactions of the American Mathematical Society. Transactions of the American Mathematical Society, Vol. 289, No. 2. 289 (2): 679–706. doi:10.2307/2000258. JSTOR 2000258.
- Beck, József; Chen, William W. L. (1987). Irregularities of Distribution. New York: Cambridge University Press. ISBN 0-521-30792-9.
- Chazelle, Bernard (2000). The Discrepancy Method: Randomness and Complexity. New York: Cambridge University Press. ISBN 0-521-77093-9.
- Matousek, Jiri (1999). Geometric Discrepancy: An Illustrated Guide. Algorithms and combinatorics. 18. Berlin: Springer. ISBN 3-540-65528-X.