Discrepancy theory
Page Module:Message box/ambox.css has no content.
This article needs additional citations for verification. (January 2018) |
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.[1]
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[2]
- Six Standard Deviations Suffice (Spencer)[3]
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[4][5][6]
See also
References
Page Template:Reflist/styles.css has no content.
- ^ Page Module:Citation/CS1/styles.css has no content.Weyl, Hermann (1 September 1916). "Über die Gleichverteilung von Zahlen mod. Eins" [About the equal distribution of numbers]. Mathematische Annalen (in Deutsch). 77 (3): 313–352. doi:10.1007/BF01475864. ISSN 1432-1807. S2CID 123470919.
- ^ Page Module:Citation/CS1/styles.css has no content.József Beck and Tibor Fiala (1981). ""Integer-making" theorems". Discrete Applied Mathematics. 3 (1): 1–8. doi:10.1016/0166-218x(81)90022-6.
- ^ Page Module:Citation/CS1/styles.css has no content.Joel Spencer (June 1985). "Six Standard Deviations Suffice". Transactions of the American Mathematical Society. 289 (2). Transactions of the American Mathematical Society, Vol. 289, No. 2: 679–706. doi:10.2307/2000258. JSTOR 2000258.
- ^ Page Module:Citation/CS1/styles.css has no content.Harshaw, Christopher; Sävje, Fredrik; Spielman, Daniel A; Zhang, Peng (2024). "Balancing covariates in randomized experiments with the Gram--Schmidt walk design". Journal of the American Statistical Association. 119 (548): 2934–2946. arXiv:1911.03071. doi:10.1080/01621459.2023.2285474.
- ^ Page Module:Citation/CS1/styles.css has no content.Spielman, Daniel (11 May 2020). Using discrepancy theory to improve the design of randomized controlled trials.
- ^ Page Module:Citation/CS1/styles.css has no content.Spielman, Daniel (29 January 2021). Discrepancy Theory and Randomized Controlled Trials.
Further reading
- Page Module:Citation/CS1/styles.css has no content.Beck, József; Chen, William W. L. (1987). Irregularities of Distribution. New York: Cambridge University Press. ISBN 0-521-30792-9.
- Page Module:Citation/CS1/styles.css has no content.Chazelle, Bernard (2000). The Discrepancy Method: Randomness and Complexity. New York: Cambridge University Press. ISBN 0-521-77093-9.
- Page Module:Citation/CS1/styles.css has no content.Matousek, Jiri (1999). Geometric Discrepancy: An Illustrated Guide. Algorithms and combinatorics. Vol. 18. Berlin: Springer. ISBN 3-540-65528-X.
Lua error in package.lua at line 80: module 'Module:Authority control/config' not found.
