Low-discrepancy sequence

From WikiMD's Wellness Encyclopedia

Subrandom Kurtosis

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]

See also[edit | edit source]

Template:Numerical-analysis-stub

Contributors: Prab R. Tumpati, MD