.. _ProcHaltonDesign:

Procedure: Generate a Halton design
===================================

Description and Background
--------------------------

A Halton design is one of a number of non-random space-filling designs
suitable for defining a set of points in the
:ref:`simulator<DefSimulator>` input space for creating a :ref:`training
sample<DefTrainingSample>`.

The :math:`n` point Halton design in :math:`p` dimensions is generated by a
generator set :math:`g=(g_1,\ldots,g_p)` of prime numbers. See the
"Additional Comments" below for discussion of the choice of generators.

Inputs
------

-  Number of dimensions :math:`p`
-  Number of points desired :math:`n`
-  Set of prime generators :math:`g_1,\ldots,g_p`

Outputs
-------

-  Halton design :math:`D = \{x_1, x_2, \ldots, x_n\}`

Procedure
---------

#. For each :math:`i=1,2,\ldots,p` and :math:`j=1,2,\ldots,n`, let :math:`a_{ij}`
   be the representation in prime base :math:`g_i` of the number :math:`j`.
   Let :math:`n_{ij}` be the number of digits used for :math:`a_{ij}` (i.e.
   :math:`n_{ij}` is the logarithm to base :math:`g_i` of :math:`j`, rounded up
   to the nearest integer), and let :math:`R_{ij}` be the result of
   reversing the digits of :math:`a_{ij}` and evaluating this as a number
   in base :math:`g_i`.
#. For each :math:`i=1,2,\ldots,p` and :math:`j=1,2,\ldots,n`, let :math:`x_{ij} =
   R_{ij} /g_i^{n_{ij}}`.
#. For :math:`j=1,2,\ldots,n`, the j-th design point is :math:`x_j = (x_{1j},
   x_{2j}, \ldots, x_{pj})`.

For example, if :math:`j=10` and :math:`g_i=2`, then :math:`a_{ij}=1010`, from
which we have :math:`n_{ij}=4`. Then :math:`R_{ij}` is the binary number 0101,
i.e 5, so that :math:`x_{ij}=5/2^4=0.3125`.

Additional Comments
-------------------

A potential problem with Halton designs is the difficulty in finding
suitable generators. One suggestion is to let :math:`g_i` be the :math:`i`-th
prime, but this may not work well when :math:`p` is large.

References
----------

The following is a link to the repository for Matlab code for the Halton
sequence in up to 11 dimensions:
`CPHaltonSequence.m <https://virgo.aston.ac.uk/MUCM/WP3_1/code/CPHaltonSequence.m>`_
(:ref:`disclaimer<MetaSoftwareDisclaimer>`).