Discrepancy theory

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.



  • 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
  • Six Standard Deviations Suffice (Spencer)[1]

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.[2]
  • Erdős discrepancy problem‎ - Homogeneous arithmetic progressions (Erdős, $500)


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

See also


  1. ^ 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. 
  2. ^ 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 0521307929. 
  • Chazelle, Bernard (2000). The Discrepancy Method: Randomness and Complexity. New York: Cambridge University Press. ISBN 0521770939. 
  • Matousek, Jiri (1999). Geometric Discrepancy: An Illustrated Guide. Algorithms and combinatorics. 18. Berlin: Springer. ISBN 354065528X. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Discrepancy of hypergraphs — is an area of discrepancy theory. Contents 1 Hypergraph discrepancies in two colors 2 Theorems 2.1 Classic theorems 3 Major open problems …   Wikipedia

  • Discrepancy — may refer to: Mathematics Discrepancy of a sequence Discrepancy theory in structural modelling Discrepancy of hypergraphs, an area of discrepancy theory Statistics Discrepancy function in the context of structural equation models Other Desire… …   Wikipedia

  • Discrepancy function — A discrepancy function is a mathematical function which describes how closely a structural model conforms to observed data. Larger values of the discrepancy function indicate a poor fit of the model to data. In general, the parameter estimates… …   Wikipedia

  • Theory of everything — A theory of everything (TOE) is a putative theory of theoretical physics that fully explains and links together all known physical phenomena. Initially, the term was used with an ironic connotation to refer to various overgeneralized theories.… …   Wikipedia

  • Identity control theory — Identity Control Theory, created by Peter Burke, focuses on the nature of peoples identities and the relationship between their identities and their behavior within the realm of their social structure. The identities of the individual are rooted… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Expectancy violations theory — sees communication as the exchange of information that is high in relational content and can be used to violate the expectations of another, who will perceive the exchange either positively or negatively depending on the liking between the two… …   Wikipedia

  • Labor theory of value — The labor theories of value (LTV) are theories in economics according to which the values of commodities are related to the labor needed to produce them.There are many different accounts of labor value, with the common element that the value of… …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

  • History of gravitational theory — In physics, theories of gravitation postulate mechanisms of interaction governing the movements of bodies with mass. There have been numerous theories of gravitation since ancient times.AntiquityIn the 4th century BC, the Greek philosopher… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”