Low-discrepancy sequence
A low-discrepancy sequence, also known as a quasi-random sequence, is a sequence of numbers that is designed to cover a multi-dimensional space more uniformly than uncorrelated random points. These sequences are used in numerical methods, particularly in the field of Monte Carlo integration, where they can significantly improve the accuracy and convergence rate of the integration process.
Definition[edit | edit source]
The discrepancy of a sequence is a measure of its deviation from uniform distribution. For a sequence \(\{x_1, x_2, \ldots, x_N\}\) in the unit interval \([0,1)\), the discrepancy \(D_N\) is defined as: \[ D_N = \sup_{0 \le a < b \le 1} \left| \frac{A([a,b))}{N} - (b - a) \right| \] where \(A([a,b))\) is the number of points \(x_i\) in the interval \([a,b)\).
A sequence is considered a low-discrepancy sequence if its discrepancy \(D_N\) grows slowly as \(N\) increases. Specifically, for a sequence to be low-discrepancy, \(D_N\) should grow at a rate of \(O\left(\frac{\log^k N}{N}\right)\) for some constant \(k\).
Examples[edit | edit source]
Several well-known low-discrepancy sequences include:
Each of these sequences has specific properties and construction methods that make them suitable for different types of numerical integration and simulation tasks.
Applications[edit | edit source]
Low-discrepancy sequences are widely used in various fields, including:
- Numerical integration: They are used to improve the accuracy of integration in higher dimensions.
- Computer graphics: They help in rendering images by providing more uniform sampling.
- Financial mathematics: They are used in the valuation of complex financial derivatives.
- Optimization: They are used in global optimization algorithms to explore the search space more efficiently.
Related Concepts[edit | edit source]
- Quasi-Monte Carlo method
- Uniform distribution (discrete)
- Random number generation
- Pseudo-random number generator
See also[edit | edit source]
Navigation: Wellness - Encyclopedia - Health topics - Disease Index - Drugs - World Directory - Gray's Anatomy - Keto diet - Recipes
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
WikiMD is not a substitute for professional medical advice. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Contributors: Prab R. Tumpati, MD