• Source: Discrepancy theory

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.
A significant event in the history of discrepancy theory was the 1916 paper of Weyl on the uniform distribution of sequences in the unit interval.




Theorems


Discrepancy theory is based on the following classic theorems:

Geometric discrepancy theory
The theorem of van Aardenne-Ehrenfest
Arithmetic progressions (Roth, Sarkozy, Beck, Matousek & Spencer)
Beck–Fiala theorem
Six Standard Deviations Suffice (Spencer)




Major open problems


The unsolved problems relating to discrepancy theory include:

Axis-parallel rectangles in dimensions three and higher (folklore)
Komlós conjecture
Heilbronn triangle problem on the minimum area of a triangle determined by three points from an n-point set




Applications


Applications for discrepancy theory include:

Numerical integration: Monte Carlo methods in high dimensions
Computational geometry: Divide-and-conquer algorithm
Image processing: Halftoning
Random trial formulation: Randomized controlled trial




See also


Discrepancy of hypergraphs
Geometric discrepancy theory




References






Further reading


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. Vol. 18. Berlin: Springer. ISBN 3-540-65528-X.

Kata Kunci Pencarian:

• Barisan tanda
• Manusia
• Terence Tao
• Teorema Euclid-Euler
• Daftar masalah matematika yang belum terpecahkan
• Discrepancy theory
• Self-discrepancy theory
• Low-discrepancy sequence
• Discrepancy function
• Discrepancy
• Cognitive dissonance
• Sign sequence
• Job satisfaction
• Ramsey theory
• Geometric discrepancy