Editing Halton sequence

{{Short description|Type of numeric sequence used in statistics}}
{{multiple image
   | direction = vertical
   | width     = 
   | footer    = 256 points from the first 256 points of the 2,3 Halton sequence (top) compared with a pseudorandom number source (bottom).  The Halton sequence covers the space more evenly. (red=1,..,10, blue=11,..,100, green=101,..,256)
   | image1    = Halton sequence 2D.svg
   | alt1      = 
   | caption1  = 
   | image2    = Pseudorandom sequence 2D.svg
   | alt2      = 
   | caption2  = 
  }}
In [[statistics]], '''Halton sequences'''<!-- Who's Halton? --> are  [[sequence]]s used to generate points in space for numerical methods such as [[Monte Carlo simulations]].  Although these sequences are [[Deterministic system (mathematics)|deterministic]], they are of [[Low-discrepancy sequence|low discrepancy]], that is, appear to be [[random]] for many purposes. They were first introduced in 1960 and are an example of a [[quasi-random number]] sequence.  They generalize the one-dimensional [[van der Corput sequence]]s.

== Example of Halton sequence used to generate points in (0,&nbsp;1) &times; (0,&nbsp;1) in R<sup>2</sup> ==
[[File:Halton_sequence_2_3.svg|thumb|250px|Illustration of the first 8 points of the 2,3 Halton sequence]]
The Halton sequence is constructed according to a deterministic method that uses [[coprime integers|coprime numbers]] as its bases. As a simple example, let's take one dimension of the two-dimensional Halton sequence to be based on 2 and the other dimension on 3.  To generate the sequence for 2, we start by dividing the interval (0,1) in half, then in fourths, eighths, etc., which generates

: {{frac|2}}, 
: {{frac|4}}, {{frac|3|4}}, 
: {{frac|8}}, {{frac|5|8}}, {{frac|3|8}}, {{frac|7|8}}, 
: {{frac|16}}, {{frac|9|16}},...

Equivalently, the nth number of this sequence is the number n written in binary representation, inverted, and written after the decimal point. This is true for any base. As an example, to find the sixth element of the above sequence, we'd write 6 = 1*2{{sup|2}} + 1*2{{sup|1}} + 0*2{{sup|0}} = 110{{sub|2}}, which can be inverted and placed after the decimal point to give 0.011{{sub|2}} = 0*2{{sup|-1}} + 1*2{{sup|-2}} + 1*2{{sup|-3}} = {{frac|3|8}}. So the sequence above is the same as

: 0.1{{sub|2}}, 0.01{{sub|2}}, 0.11{{sub|2}}, 0.001{{sub|2}}, 0.101{{sub|2}}, 0.011{{sub|2}}, 0.111{{sub|2}}, 0.0001{{sub|2}}, 0.1001{{sub|2}},...

To generate the sequence for 3 for the other dimension, we divide the interval (0,1) in thirds, then ninths, twenty-sevenths, etc., which generates

: {{frac|3}}, {{frac|2|3}}, {{frac|9}}, {{frac|4|9}}, {{frac|7|9}}, {{frac|2|9}}, {{frac|5|9}}, {{frac|8|9}}, {{frac|27}},...
When we pair them up, we get a sequence of points in a [[unit square]]:

: ({{frac|2}}, {{frac|3}}), ({{frac|4}}, {{frac|2|3}}), ({{frac|3|4}}, {{frac|9}}), ({{frac|8}}, {{frac|4|9}}), ({{frac|5|8}}, {{frac|7|9}}), ({{frac|3|8}}, {{frac|2|9}}), ({{frac|7|8}}, {{frac|5|9}}), ({{frac|16}}, {{frac|8|9}}), ({{frac|9|16}}, {{frac|27}}).

Even though standard Halton sequences perform very well in low dimensions, correlation problems have been noted between sequences generated from higher primes.  For example, if we started with the primes 17 and 19, the first 16 pairs of points: ({{frac|17}}, {{frac|19}}), ({{frac|2|17}}, {{frac|2|19}}), ({{frac|3|17}}, {{frac|3|19}}) ... ({{frac|16|17}}, {{frac|16|19}}) would have perfect [[linear correlation]]. To avoid this, it is common to drop the first 20 entries, or some other predetermined quantity depending on the primes chosen. Several other methods have also been proposed. One of the most prominent solutions is the scrambled Halton sequence, which uses permutations of the coefficients used in the construction of the standard sequence. Another solution is the ''leaped Halton'', which skips points in the standard sequence. Using, e.g., only each 409th point (also other prime numbers not used in the Halton core sequence are possible), can achieve significant improvements.<ref name="Kc1997">Kocis and Whiten, 1997</ref>

== Implementation ==
In [[pseudocode]]:
 '''algorithm''' Halton-Sequence '''is'''
     '''inputs''': index <math>i</math>
             base <math>b</math>
     '''output''': result <math>r</math>
 
     <math>f \larr 1</math>
     <math>r \larr 0</math>
 
     '''while''' <math>i > 0</math> '''do'''
         <math>f \larr f/b</math>
         <math>r \larr r + f * (i \operatorname{mod} b)</math>
         <math>i \larr \lfloor i/b \rfloor</math>
 
     '''return''' <math>r</math>

An alternative implementation that produces subsequent numbers of a Halton sequence for base ''b'' is given in the following [[Generator (computer programming)#Python|generator function]] (in [[Python (programming language)|Python]]).<ref name="BerblingerSchlier1991">{{cite journal|last1=Berblinger|first1=Michael|last2=Schlier|first2=Christoph|title=Monte Carlo integration with quasi-random numbers: some experience|journal=Computer Physics Communications|volume=66|issue=2–3|year=1991|pages=157–166|issn=0010-4655|doi=10.1016/0010-4655(91)90064-R|bibcode=1991CoPhC..66..157B |url=https://www.freidok.uni-freiburg.de/dnb/download/3927 }}</ref> This algorithm uses only [[integer]] numbers internally, which makes it robust against round-off errors.
<syntaxhighlight lang="python">
def halton_sequence(b):
    """Generator function for Halton sequence."""
    n, d = 0, 1
    while True:
        x = d - n
        if x == 1:
            n = 1
            d *= b
        else:
            y = d // b
            while x <= y:
                y //= b
            n = (b + 1) * y - x
        yield n / d
</syntaxhighlight>

== See also ==
* [[Constructions of low-discrepancy sequences]]

==References==
{{Reflist}}
* {{citation | last1=Kuipers | first1=L. | last2= Niederreiter | first2=H. | author2-link = Harald Niederreiter | title = Uniform distribution of sequences | publisher=[[Dover Publications]] | year=2005 | isbn=0-486-45019-8 | page=129 }}
* {{citation | last=Niederreiter | first=Harald | authorlink = Harald Niederreiter | title=Random number generation and quasi-Monte Carlo methods | publisher=[[Society for Industrial and Applied Mathematics|SIAM]] | year=1992 | isbn=0-89871-295-5 | page=29 }}.
* {{citation | last=Halton | first=J. | title=Algorithm 247: Radical-inverse quasi-random point sequence | journal=Communications of the ACM | volume=7 | year=1964 | issue=12 | doi=10.1145/355588.365104 | page=701-701 | s2cid=47096908 | doi-access=free }}.
* {{citation | last1=Kocis | first1=Ladislav | last2=Whiten | first2=William | title=Computational Investigations of Low-Discrepancy Sequences | journal=ACM Transactions on Mathematical Software | volume=23 | year=1997 | issue=2 | doi=10.1145/264029.264064 | pages=266–296 | s2cid=183263 | doi-access=free }}.

[[Category:Low-discrepancy sequences]]
[[Category:Sequences and series]]
[[Category:Articles with example pseudocode]]
[[Category:Articles with example Python (programming language) code]]