Editing Low-discrepancy sequence (section)

=== 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.