Editing Low-discrepancy sequence (section)

==Definition of discrepancy==

The ''discrepancy'' of a set <math>P = \{x_1, \dots, x_N }\</math> is defined, using [[Harald Niederreiter|Niederreiter's]] notation, as
:<math> D_N(P) = \sup_{B\in J}
  \left|  \frac{A(B;P)}{N} - \lambda_s(B)  \right|</math>

where <math>\lambda_s</math> is the <math>s</math>-dimensional [[Lebesgue measure]],
<math>A(B;P)</math> is the number of points in <math>P</math> that fall into <math>B</math>,
and <math>J</math> is the set of <math>s</math>-dimensional intervals or boxes of the form

:<math> \prod_{i=1}^s [a_i, b_i) = \{ \mathbf{x} \in \mathbf{R}^s : a_i \le x_i < b_i \} \, </math>

where <math> 0 \le a_i < b_i \le 1 </math>.

The ''star-discrepancy'' <math>D^*_N(P)</math> is defined similarly, except that the supremum is taken over the set <math>J^*</math> of rectangular boxes of the form

:<math> \prod_{i=1}^s [0, u_i) </math>

where <math>u_i</math> is in the half-open interval <nowiki>[0, 1)</nowiki>.

The two are related by

:<math>D^*_N \le D_N \le 2^s D^*_N . \,</math>

''Note'': With these definitions, discrepancy represents the worst-case or maximum point density deviation of a uniform set. However, also other error measures are meaningful, leading to other definitions and variation measures. For instance, <math>L^2</math>-discrepancy or modified centered <math>L^2</math>-discrepancy are also used intensively to compare the quality of uniform point sets. Both are much easier to calculate for large <math>N</math> and <math>s</math>.