Editing Low-discrepancy sequence (section)

==Applications==

[[Image:Subrandom Kurtosis.gif|thumb|370px|right|Error in estimated kurtosis as a function of number of datapoints. 'Additive quasirandom' gives the maximum error when ''c''&nbsp;=&nbsp;({{radic|5}}&nbsp;&minus;&nbsp;1)/2. 'Random' gives the average error over six runs of random numbers, where the average is taken to reduce the magnitude of the wild fluctuations]]

Quasirandom numbers have an advantage over pure random numbers in that they cover the domain of interest quickly and evenly.

Two useful applications are in finding the [[characteristic function (probability theory)|characteristic function]] of a [[probability density function]], and in finding the [[derivative]] function of a deterministic function with a small amount of noise. Quasirandom numbers allow higher-order [[moment (mathematics)|moments]] to be calculated to high accuracy very quickly.

Applications that don't involve sorting would be in finding the [[mean]], [[standard deviation]], [[skewness]] and [[kurtosis]] of a statistical distribution, and in finding the [[integral]] and global [[maxima and minima]] of difficult deterministic functions. Quasirandom numbers can also be used for providing starting points for deterministic algorithms that only work locally, such as [[Newton–Raphson iteration]].

Quasirandom numbers can also be combined with search algorithms. With a search algorithm, quasirandom numbers can be used to find the [[mode (statistics)|mode]], [[median]], [[confidence intervals]] and [[cumulative distribution function|cumulative distribution]] of a statistical distribution, and all [[local minima]] and all solutions of deterministic functions.

=== Low-discrepancy sequences in numerical integration ===

Various methods of [[numerical integration]] can be phrased as approximating the integral of a function <math>f</math> in some interval, e.g. <nowiki>[0,1]</nowiki>, as the average of the function evaluated at a set <math>\{x_1, \dots, x_N }\</math> in that interval:
:<math> \int_0^1 f(u)\,du \approx \frac{1}{N}\,\sum_{i=1}^N f(x_i). </math>

If the points are chosen as  <math>x_i = i/N</math>, this is the ''rectangle rule''.
If the points are chosen to be randomly (or [[pseudorandom]]ly) distributed, this is the ''[[Monte Carlo method]]''.
If the points are chosen as elements of a low-discrepancy sequence, this is the ''quasi-Monte Carlo method''.
A remarkable result, the '''Koksma–Hlawka inequality''' (stated below), shows that the error of such a method can be bounded by the product of two terms, one of which depends only on <math>f</math>, and the other one is the discrepancy of the set <math>\{x_1, \dots, x_N }\</math>.

It is convenient to construct the set <math>\{x_1, \dots, x_N }\</math> in such a way that if a set with <math>N+1</math> elements is constructed, the previous <math>N</math> elements need not be recomputed.
The rectangle rule uses points set which have low discrepancy, but in general the elements must be recomputed if <math>N</math> is increased.
Elements need not be recomputed in the random Monte Carlo method if <math>N</math> is increased,
but the point sets do not have minimal discrepancy.
By using low-discrepancy sequences we aim for low discrepancy and no need for recomputations, but actually low-discrepancy sequences can only be incrementally good on discrepancy if we allow no recomputation.