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 positionn
- 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
-
van_der_corput(unsigned b = 2u, unsigned n = 0u)#
-
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 positionn
- 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