Definitions

# Discrepancy theory

In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be. It is also called 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.

## Classic theorems

• Axis-parallel rectangles in the plane (Roth, Schmidt)
• Discrepancy of half-planes (Alexander, Matousek)
• Arithmetic progressions (Roth, Sarkozy, Beck, Matousek & Spencer)
• Beck-Fiala theorem
• Six Standard Deviations Suffice (Spencer)

## Major open problems

• Axis-parallel rectangles in dimensions three and higher (Folklore)
• Komlos conjecture
• The three permutations problem (Beck)
• Homogeneous arithmetic progressions (Erdos, \$500)

## Applications

• Numerical Integration: Monte Carlo methods in high dimensions.
• Computational Geometry: Divide and conquer algorithms.
• Image Processing: Halftoning

## Further reading

• Beck, József; Chen, William W. L. (1987). Irregularities of Distribution. New York: Cambridge University Press.
• Chazelle, Bernhard (2000). The Discrepancy Method: Rrandomness and Complexity. New York: Cambridge University Press.
• Matousek, Jiri (1999). Geometric Discrepancy: An Illustrated Guide. Berlin: Springer.

Search another word or see Discrepancy theoryon Dictionary | Thesaurus |Spanish
Copyright © 2013 Dictionary.com, LLC. All rights reserved.
• Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT