Low-discrepancy sequence

Error creating thumbnail:

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

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

Several well-known low-discrepancy sequences include:

• Van der Corput sequence
• Halton sequence
• Sobol sequence
• Faure sequence
• Niederreiter sequence

Each of these sequences has specific properties and construction methods that make them suitable for different types of numerical integration and simulation tasks.

Applications

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

• Quasi-Monte Carlo method
• Uniform distribution (discrete)
• Random number generation
• Pseudo-random number generator

See also

• Monte Carlo method
• Numerical analysis
• Simulation
• Stochastic process