2
$\begingroup$

I am interested in low discrepancy sets for its applications in Monte Carlo integration - KH inequality tells us that the error will be lesser if the discrepancy of the sample is lesser. Every reference on Halton talks about the discrepancy of the Halton sequence - not the Halton set.

Why do people generally look at discrepancy of the sequence (and not the discrepancy of the set)? What is the discrepancy of the Halton set?

Note: I had posted this question earlier in stack exchange, reposting here as I did not receive any answer.

$\endgroup$
11
  • 1
    $\begingroup$ Monte-Carlo implementations use sequences rather than sets. then what you are generating is a $\endgroup$ Commented Apr 23, 2019 at 13:56
  • 2
    $\begingroup$ Equidistribution is a property of sequences since its formulation involves limits. $\endgroup$ Commented Apr 23, 2019 at 19:22
  • 2
    $\begingroup$ @Liviu, I reckon Monte-Carlo implementations use initial segments of sequences, which amounts to using finite sets, and the discrepancy of these finite sets is an important consideration in these implementations. $\endgroup$ Commented Apr 23, 2019 at 22:53
  • 2
    $\begingroup$ The m.se post can be found at math.stackexchange.com/questions/3186682/… $\endgroup$ Commented Apr 23, 2019 at 22:55
  • 3
    $\begingroup$ How about we split the difference: discrepancy is well defined for finite sets, but it is relevant to Monte Carlo method that deals with sequences. In that case only certain sets are interesting, namely initial segments, i.e., the sets formed by consecutive terms of the sequence. $\endgroup$ Commented Apr 24, 2019 at 15:11

1 Answer 1

1
$\begingroup$

It is true that in general there is a difference between "sets" and "sequences". The later, unlike sets, may have repeating elements, and also unlike sets, the order of elements matter.

https://en.wikipedia.org/wiki/Sequence

Having said that the way discrepancy is defined, plus the way Low-Discrepancy-Sequences (LDS) are created, plus the way they are used for numerical quadratures, all that does treat a sequence like a "set". Let me walk through the justification of each of these points.

Definition: The discrepancy of a set $P = \{x_1, \cdots, x_N\}$ is defined, using Niederreiter's notation, as $$D_{N}(P)=\sup _{{B\in J}}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right| \;\;\;\;\;\;\;\;\;\;\;\;\;(1)$$

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

$$\prod_{i=1}^s [ a_i , b_i ) = \{ \mathbf{x} \in \mathcal{R}^s : a_i ≤ x_i < b_i \}$$

where $0 ≤ a_i < b_i ≤ 1$.

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

$$\prod _{{i=1}}^{s}[0,u_{i})$$

where $u_i$ is in the half-open interval $[0, 1)$.

https://en.wikipedia.org/w/index.php?title=Low-discrepancy_sequence&oldid=1121367580

Now, from these definitions, discrepancy represents the worst-case or maximum point density deviation of a uniform set, but it is possible to derive the error for uniform point sets: This is the case of the LDS, and the reason why it works comes from the Koksma-Hlawka inequality:

For any point set $\{x_1,\cdots,x_N\}$ in the the $s$-dimensional unit cube, $\bar{I}^s = [0, 1] \times \cdots \times [0, 1]$ and any $\varepsilon >0$, there is a function $f$ with bounded variation and $V(f) = 1$ such that

$$ \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|>D_{N}^{*}(x_{1},\ldots ,x_{N})-\varepsilon\;\;\;\;\;\;\;(2)$$

Therefore, the quality of a numerical integration rule depends only on the discrepancy $D^*_N(x_1,\cdots,x_N)$.

Clearly, in this case the point set is an LDS. So, this definition names LDS as "sets". But if this is still unconvincing, let me go ahead and describe

How LDS are used:

Formula (1) require the usage of Lebesgue measures, and recall that a Lebesgue measure is the set of all subsets $E$ that have the following property: For any interval $I = [ a , b ]\; I = [a,b]$, or $I = ( a , b )$, in the set $\mathbb{R}$ of real numbers, let $ \ell (I)=b-a$ denote its length. For any subset $E\subseteq {\mathbb {R}}$, the Lebesgue outer measure $ \lambda ^{\!*\!}(E)$ is defined as an infimum

$$ \lambda ^{\!*\!}(E)=\inf \left\{\sum _{k=1}^{\infty }\ell (I_{k}):{(I_{k})_{k\in \mathbb {N} }}{\text{ is a sequence of open intervals with }}E\subset \bigcup _{k=1}^{\infty }I_{k}\right\}.$$

Some sets $E$ satisfy the Carathéodory criterion, which requires that for every $ A\subseteq \mathbb {R} $,

$$ \lambda ^{\!*\!}(A)=\lambda ^{\!*\!}(A\cap E)+\lambda ^{\!*\!}(A\cap E^{c}).$$

The set of all such $E$ forms a $\sigma$-algebra. For any such $E$, its Lebesgue measure is defined to be its Lebesgue outer measure: $\lambda (E)=\lambda ^{\!*\!}(E)$. A $\sigma$-algebra itself is formed using sets (actually subsets of a certain set $X$).

https://en.wikipedia.org/wiki/Lebesgue_measure

Again, LDS could be treated as sets.

Generation of LDS: There are several ways to generate LDS. Without loss of generality, Let us take the decimal Van der Corput sequence: $$ \left\{{\tfrac {1}{10}},{\tfrac {2}{10}},{\tfrac {3}{10}},{\tfrac {4}{10}},{\tfrac {5}{10}},{\tfrac {6}{10}},{\tfrac {7}{10}},{\tfrac {8}{10}},{\tfrac {9}{10}},{\tfrac {1}{100}},{\tfrac {11}{100}},{\tfrac {21}{100}},{\tfrac {31}{100}},{\tfrac {41}{100}},{\tfrac {51}{100}},{\tfrac {61}{100}},\ldots \right\},$$

or in decimal representation:

$$\left\{ 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61,\ldots \right\},$$

https://en.wikipedia.org/wiki/Van_der_Corput_sequence

The point being that there is a order in this sequence, but the order comes from the algorithm for creating the sequence, not necessarily the canonical way of ordering real numbers, and in this sense they comply with the definition of "sequence". However, the elements in the sequence, taken as a whole, they do become a well-ordered set, in the sense of having a least element, and each element has a successor.

https://en.wikipedia.org/wiki/Well-order

This Van der Corput sequence actually forms a dense set in the closed interval $[0,1]$, and this last property not only is shared by all LDS, but also it can be exploited for using LDS's for numerical quadrature, as a quasi-random method. More of that in the next section. Also, most (if not all) LDS generate unique elements, unlike random generators, in the sense that the distribution of points of LDS in a given space is more uniform than random points, the later having the tendency to "cluster" in some parts, and produce "voids" in other parts of the space.

Numerical quadratures and LDS: From (1) and (2), it is possible to see that LDS can be used for numerical integration, and the way they behave is more like Lebesgue integration, in the sense that the points from LDS need not come from a partition in the canonical order, but the final sum will approximate fairly well the value of a given integral. This numerical property should suggest that the discrepancy of the LDS can be taken as a set.

Summarizing: Most (if not all) ways of constructing LDS generate unique elements, and despite the order they are generated (according to the particular algorithm they came from), while used in integration the order of those elements is irrelevant, thus we could say that at least in the context of quasi-random integration, LDS have features of both sequences and sets, therefore (by (1) and (2)) speaking of discrepancy of the sequence is equivalent to speaking of the discrepancy of the set of elements of that sequence.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .