Low-discrepancy sequences#

A number of utilities to generate and use low- discrepancy sequences

std::vector<double> pagmo::sample_from_simplex(std::vector<double> in)#

Sample from a simplex.

Samples a point on a \(n\) dimensional simplex from a \(n-1\) dimensional point

In order to generate a uniform distribution on a simplex, that is to sample a \(n\)-dimensional point \(\mathbf x\) such that \(\sum_{i=1}^{n} x_i = 1\) one can follow the following approach: take \(n-1\) random numbers from the interval (0,1)(0,1), then add a 0 and 1 to get a list of \(n+1\) numbers. Sort the list and record the differences between two consecutive elements. This creates a list of \(n\) number that, by construction, will sum up to 1. Moreover this sampling is uniform. As an example the following code would generate points distributed on a \(n\) dimensional simplex:

std::vector<std::vector<double>> points_on_a_simplex;
halton ld_rng(n-1);
for (auto i = 0u; i < 100u; ++i) {
     points_on_a_simplex.push_back(project_to_simplex(ld_rng()));
}

See: Donald B. Rubin, The Bayesian bootstrap Ann. Statist. 9, 1981, 130-134.

Parameters

in – a std::vector containing a point in \(n+1\) dimensions.

Throws

std::invalid_argument – if the input vector elements are not in [0,1]
std::invalid_argument – if the input vector has size 0 or 1.

Returns

a std::vector containing the projected point of \(n\) dimensions.

class van_der_corput#

Van der Corput sequence.

A Van der Corput sequence is the simplest one-dimensional low-discrepancy sequence over the unit interval; it was first described in 1935 by the Dutch mathematician Johannes van der Corput. It is constructed by reversing the base representation of the sequence of natural number (1, 2, 3, …). A positive integer \(n \ge 1\) is represented, in the base \(b\) by:

\[ n = \sum_{i=0}^{L-1}d_i(n) b^i, \]

where \(L\) is the number of digits needed. The \(n\)-th number in a van der Corput sequence is thus defined as:

\[ g_n=\sum_{i=0}^{L-1}d_i(n) b^{-i-1}. \]

so that, for example, if \(b = 10\):

\( seq = \{ 0, \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}, \tfrac{71}{100}, \tfrac{81}{100}, \tfrac{91}{100}, \tfrac{2}{100}, \tfrac{12}{100}, \tfrac{22}{100}, \tfrac{32}{100}, \ldots \} \,\)

or, if \(b = 2\):

\( seq = \{0, \tfrac{1}{2}, \tfrac{1}{4}, \tfrac{3}{4}, \tfrac{1}{8}, \tfrac{5}{8}, \tfrac{3}{8}, \tfrac{7}{8}, \tfrac{1}{16}, \tfrac{9}{16}, \tfrac{5}{16}, \tfrac{13}{16}, \tfrac{3}{16}, \tfrac{11}{16}, \tfrac{7}{16}, \tfrac{15}{16}, \ldots.\} \)

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

Public Functions

van_der_corput(unsigned b = 2u, unsigned n = 0u)#

Constructor from base and starting element.

Construct a van der Corput lowp-discrepancy sequence with base b and starting element position n

Parameters

b – base
n – position of the starting element

Throws

std::invalid_argument – if the base is 0u or 1u

double operator()()#

Returns the next number in the sequence.

Returns: the next number in the sequence

class halton#

Halton sequence.

The Halton sequence is, essentially, a generalization of the van der Corput sequence to higher dimensions. It considers, along each dimension, a van der Corput sequence referred to co-prime numbers. Here, by default, we consider the sequence of all prime numbers starting from 2, 3, 5, …… so that, for example, for dim equal two the following sequence is generated:

\[ seq = \left\{ (0, 0), \left(\frac 12, \frac 13\right), \left(\frac 14, \frac 23\right), \left(\frac 34, \frac 19\right), \left(\frac 18, \frac 49\right), \left(\frac 58, \frac 79\right), \left(\frac 38, \frac 29\right), ... \right\} \]

See: https://en.wikipedia.org/wiki/Halton_sequence

Param n: selects which element of the sequence to return
Param dim: dimensions of the returned point

Public Functions

halton(unsigned dim = 2u, unsigned n = 0u)#

Constructor from base and starting element.

Construct a Halton low-discrepancy sequence with dimension dim and starting element position n

Parameters

dim – dimension
n – position of the starting element

Throws

unspecified – all exceptions thrown by pagmo::van_der_corput

std::vector<double> operator()()#

Returns the next number in the sequence.

Returns: the next number in the sequence