Discrepancy theory

From Wikipedia, the free encyclopedia

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.

History

  • The 1916 paper of Weyl on the uniform distribution of sequences in the unit interval
  • The theorem of van Aardenne-Ehrenfest

Classic theorems

  • Axis-parallel rectangles in the plane (Roth, Schmidt)
  • Discrepancy of half-planes (Alexander, Matoušek)
  • Arithmetic progressions (Roth, Sarkozy, Beck, Matousek & Spencer)
  • Beck–Fiala theorem [1]
  • Six Standard Deviations Suffice (Spencer)[2]

Major open problems

  • Axis-parallel rectangles in dimensions three and higher (Folklore)
  • Komlós conjecture
  • The three permutations problem (Beck) – disproved by Newman and Nikolov.[3]
  • Erdős discrepancy problem – Homogeneous arithmetic progressions (Erdős, $500)
  • Heilbronn triangle problem on the minimum area of a triangle determined by three points from an n-point set

Applications

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

See also

References

  1. ↑ József Beck and Tibor Fiala. "“Integer-making” theorems". Discrete Applied Mathematics 3 (1). 
  2. ↑ 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. 
  3. ↑ http://front.math.ucdavis.edu/1104.2922

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 18. Berlin: Springer. ISBN 3-540-65528-X. 
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.