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
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
settings. Just as
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...
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
Hermann Klaus Hugo Weyl (; ; 9 November 1885 – 8 December 1955) was a German mathematician, theoretical physicist, logician and philosopher. Although much of his working life was spent in Zürich, Switzerland, and then Princeton, New Jersey, ...
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
Beck David Hansen (born Bek David Campbell; July 8, 1970), known mononymously as Beck, is an American musician, singer, songwriter, and record producer. He rose to fame in the early 1990s with his Experimental music, experimental and Lo-fi mus ...
, 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
In discrete geometry and discrepancy theory, the Heilbronn triangle problem is a problem of placing points in the plane, avoiding triangles of small area. It is named after Hans Heilbronn, who conjectured that, no matter how points are placed in ...
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 method
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be ...
s in high dimensions
* Computational geometry:
Divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dir ...
* Image processing:
Halftoning
Halftone is the reprographic technique that simulates continuous-tone imagery through the use of dots, varying either in size or in spacing, thus generating a gradient-like effect.Campbell, Alastair. ''The Designer's Lexicon''. ©2000 Chronicl ...
* Random trial formulation:
Randomized controlled trial
A randomized controlled trial (or randomized control trial; RCT) is a form of scientific experiment used to control factors not under direct experimental control. Examples of RCTs are clinical trials that compare the effects of drugs, surgical ...
See also
*
Discrepancy of hypergraphs
Discrepancy of hypergraphs is an area of discrepancy theory that studies the discrepancy of general set systems.
Definitions
In the classical setting, we aim at partitioning the vertices of a hypergraph \mathcal=(V, \mathcal) into two classes ...
*
Geometric discrepancy theory
References
Further reading
*
*
*
{{Authority control
Diophantine approximation
Unsolved problems in mathematics
Discrepancy theory
Measure theory