Lowdiscrepancy sequences
Lowdiscrepancy 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 \(n1\) 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 \(n1\) 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(n1); 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, 130134.
 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 onedimensional lowdiscrepancy 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}^{L1}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}^{L1}d_i(n) b^{i1}. \]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 lowpdiscrepancy 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 coprime 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 lowdiscrepancy 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