Fact-checked by Grok 2 weeks ago

Halton sequence

The Halton sequence is a deterministic low-discrepancy sequence designed to provide more uniform coverage of the unit hypercube than traditional pseudorandom sequences, making it a key tool in quasi-Monte Carlo methods for approximating multidimensional integrals and simulations.^[1] Introduced by John H. Halton in 1960 as an extension of the one-dimensional van der Corput sequence, it constructs points by representing successive integers in different prime bases and reversing their digits to form fractional parts, ensuring low discrepancy for efficient sampling.^[1]^[2] In one dimension, the sequence is generated using a single prime base b: for the index n, express n in base b as digits a_k a_{k-1} \dots a_1 a_0, then compute x_n = \sum_{i=0}^k a_i b^{-(i+1)}, which reverses the digits after the radix point.^[2] For example, in base 10, the sequence begins with 0.0, 0.1, 0.2, ..., 0.9, 0.01, 0.11, and so on, cycling through permutations to fill the unit interval evenly.^[3] Multidimensional versions employ distinct prime bases (e.g., 2, 3, 5 for three dimensions) for each coordinate to avoid correlations and achieve low discrepancy across the unit cube, typically up to several thousand points before correlations may increase.^[2]^[3] Halton sequences are particularly valued in applications requiring high accuracy with fewer samples, such as maximum simulated likelihood estimation in econometric models like mixed logit^[3] and financial risk assessment via Monte Carlo integration.^[4] Their deterministic nature allows for reproducible results and error bounds based on discrepancy measures, outperforming random sampling in convergence rates for smooth integrands, though they can suffer from higher discrepancy in higher dimensions without modifications like scrambling or randomization.^[2] Despite these limitations, the sequence remains a foundational method in numerical analysis due to its simplicity and effectiveness in moderate dimensions.^[1]

Mathematical Definition

One-Dimensional Halton Sequence

The one-dimensional Halton sequence is fundamentally a van der Corput sequence constructed in a prime base b. The van der Corput sequence, introduced by J. G. van der Corput in 1935, generates points in the unit interval [0,1) using the radical inverse function \phi_b(n). For a nonnegative integer n with base-b expansion n = \sum_{k=0}^\infty a_k b^k, where $0 \leq a_k < b are the digits, the radical inverse is defined as

\phi_b(n) = \sum_{k=0}^\infty \frac{a_k}{b^{k+1}}. $&#36; [](https://arxiv.org/pdf/1506.03764) This function effectively reverses the digits of $n$ in base $b$ and interprets them as a fractional value in $[0,1)&#36;.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) A concrete example is the binary van der Corput sequence with $b=2$, where the radical inverse $\phi_2(n)$ is obtained by reflecting the binary representation of $n$ after the binary point. For $n=0$, the binary expansion is &#36;0$, so $\phi_2(0) = 0$. For $n=1$ (binary &#36;1$), $\phi_2(1) = 0.1_2 = 0.5$. For $n=2$ (binary &#36;10$), $\phi_2(2) = 0.01_2 = 0.25$. For $n=3$ (binary &#36;11$), $\phi_2(3) = 0.11_2 = 0.75$. Subsequent terms continue this pattern, filling the interval with successively finer binary fractions.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) In the context of the Halton sequence, the one-dimensional case selects a prime base $b$ (such as &#36;2$, &#36;3$, or &#36;5$) and defines the $n$th term as $X_n = \phi_b(n)$ for $n = 0, 1, 2, \dots$. This choice of prime base ensures compatibility with multidimensional extensions while maintaining low-discrepancy properties in one dimension.[](https://link.springer.com/article/10.1007/BF01386213) ### Multi-Dimensional Extension The multi-dimensional Halton sequence extends the one-dimensional version by constructing points in the unit hypercube $[0,1)^d$ for $d$ dimensions, where each coordinate is generated independently using the radical inverse function with a distinct prime base for that dimension.[](https://link.springer.com/article/10.1007/BF01386213) Specifically, the first $d$ prime numbers—such as $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, and so on—are selected as bases $p_i$ for $i = 1$ to $d$, ensuring mutual coprimality among the bases to promote low correlation and good distribution properties across dimensions.[](https://link.springer.com/article/10.1007/BF01386213) The $n$th point in the $d$-dimensional sequence is then given by $\mathbf{x}_n = (\phi_{p_1}(n), \phi_{p_2}(n), \dots, \phi_{p_d}(n))$, where $\phi_{p_i}(n)$ denotes the radical inverse of $n$ in base $p_i$.[](https://link.springer.com/article/10.1007/BF01386213) This construction leverages the radical inverse from the one-dimensional case but applies it component-wise with different bases to fill the higher-dimensional space uniformly.[](https://pbr-book.org/4ed/Sampling_and_Reconstruction/Halton_Sampler) The choice of the first $d$ primes minimizes potential correlations that could arise from shared factors in the bases, as distinct primes are inherently coprime.[](https://link.springer.com/article/10.1007/BF01386213) For a concrete illustration in two dimensions ($d=2$), using bases 2 and 3, the sequence generates points in $[0,1)^2$ as follows: the 0th point is $(0, 0)$; the 1st is $(0.5, 1/3)$; the 2nd is $(0.25, 2/3)$; and the 3rd is $(0.75, 1/3)$.[](https://pbr-book.org/4ed/Sampling_and_Reconstruction/Halton_Sampler) These points are computed by expressing $n$ in the respective base, reversing the digits, and interpreting the result as a fractional value in $[0,1)$.[](https://link.springer.com/article/10.1007/BF01386213) ## Properties ### Discrepancy Measures The discrepancy of a finite set of points $ P_N = \{ \mathbf{x}_1, \dots, \mathbf{x}_N \} $ in the unit cube $[0,1]^d$ quantifies the deviation from uniform distribution and is defined as the extreme discrepancy

D_N(P_N) = \sup_{J \subset [0,1]^d} \left| \frac{A(J; P_N)}{N} - \lambda(J) \right|,

where the supremum is over all subintervals $ J $ (axis-aligned boxes), $ A(J; P_N) $ is the number of points in $ J $, and $ \lambda(J) $ is the [Lebesgue measure](/page/Lebesgue_measure) (volume) of $ J $. The star discrepancy $ D_N^*(P_N) $ restricts the supremum to anchored subintervals $ J^* = \prod_{j=1}^d [0, z_j) $ with $ 0 \leq z_j \leq 1 $, providing a computationally simpler measure that bounds the extreme discrepancy via $ D_N^*(P_N) \leq D_N(P_N) \leq 2^d D_N^*(P_N) $. These measures are central to analyzing the low-discrepancy properties of Halton sequences, as lower discrepancy implies tighter error bounds in quasi-Monte Carlo integration via the Koksma–Hlawka inequality.[](https://www.math.ucla.edu/~caflisch/Pubs/Pubs1990-1994/Morokoffsisc1994.pdf)[](https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf) For the one-dimensional case, the Halton sequence reduces to the van der Corput sequence in base $ b \geq 2 $. Halton's theorem establishes that the star discrepancy satisfies $ D_N^* = O\left( \frac{\log_b N}{N} \right) $. This bound arises from estimating the number of points falling into subintervals using the base-$ b $ digit expansion of the indices; specifically, the proof involves a direct count of how the radical-inverse function distributes points by considering the contributions over up to $ m \approx \log_b N $ digit levels, where discrepancies accumulate via base-$ b $ harmonic-like sums, leading to the logarithmic term. More refined asymptotics show $ N D_N^* \sim \frac{\log N}{\log b} $, confirming the order $ O\left( \frac{\log N}{N} \right) $.[](https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf) In multiple dimensions, the Halton sequence extends the van der Corput construction using distinct prime bases $ b_1, \dots, b_d $. Halton's theorem generalizes to show that both the extreme and star discrepancies satisfy $ D_N = O( (\log N)^d / N ) $ and $ D_N^* = O( (\log N)^d / N ) $, with the leading constant depending on the product over bases $ \prod_{j=1}^d (b_j - 1)/(2 \log b_j) $. The proof relies on the tensor product structure: the discrepancy factors across dimensions via the independence of digit expansions in coprime bases, bounding the local discrepancy in each coordinate and multiplying the logarithmic factors, yielding the $ d $-th power. This asymptotic rate grows slower than the expected $ O(\sqrt{\log N / N}) $ for pseudorandom sequences in fixed $ d $, but excels in integration error bounds of order $ O( (\log N)^d / N ) $ for functions of bounded variation. Improved variants, such as generalized or scrambled Halton sequences, achieve similar or slightly better constants through digit permutations that reduce the discrete discrepancy in individual coordinates.[](https://www.math.uwaterloo.ca/~clemieux/papers/hfclMCM09_Sep10.pdf)[](https://www.math.ucla.edu/~caflisch/Pubs/Pubs1990-1994/Morokoffsisc1994.pdf) To illustrate, consider the first $ N=4 $ points of the one-dimensional base-2 van der Corput sequence: $ 0, 0.5, 0.25, 0.75 $. Sorted as $ x_{(1)}=0, x_{(2)}=0.25, x_{(3)}=0.5, x_{(4)}=0.75 $, the star discrepancy is computed as

D_4^* = \max\left( \max_{1 \leq k \leq 4} \left| \frac{k}{4} - x_{(k)} \right|, \max_{1 \leq k \leq 4} \left| x_{(k)} - \frac{k-1}{4} \right|, \frac{1}{4} \right) = 0.25,

achieved at multiple points (e.g., $ 1/4 - 0 = 0.25 $). This value is consistent with the order of the bound $ O((\log N)/N) $.[](https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf) ### Correlation Issues and Remedies One notable limitation of the Halton sequence arises in low dimensions, particularly the first two dimensions using bases 2 and 3, where correlations between coordinates produce visible ray-like patterns along diagonals in two-dimensional projections.[](https://www.caee.utexas.edu/prof/bhat/abstracts/scrambled_halton_sequences.pdf) These artifacts stem from the synchronized periodic structures in the radical inverse functions for small primes, which cause points to cluster along linear trajectories rather than distributing uniformly.[](https://www.sciencedirect.com/science/article/abs/pii/S037847540500087X) Small prime bases exacerbate these correlations because their short cycle lengths in the base-$b$ expansion lead to repetitive digit patterns that align across dimensions, making discrepancies apparent even in simple projections.[](https://www.sciencedirect.com/science/article/pii/S0377042705003717) In contrast, larger primes introduce longer cycles that delay such visible alignments to higher dimensions, but the initial dimensions remain susceptible due to the fundamental arithmetic similarities in low-radix representations.[](https://www.caee.utexas.edu/prof/bhat/abstracts/scrambled_halton_sequences.pdf) To mitigate these issues, generalized Halton sequences employ digit permutations in the radical inverse, known as scrambling, to disrupt correlations while preserving low discrepancy. Seminal approaches include the deterministic permutations of Braaten and Weller, which optimize for reduced discrepancy by selecting digit rearrangements that minimize clustering.[](https://www.sciencedirect.com/science/article/pii/S0377042705003717) Another influential method is Owen scrambling, which uses random-like permutations to achieve probabilistic uniformity bounds, enhancing performance in quasi-Monte Carlo applications. Recent advances, such as improved scrambling techniques, further reduce correlations in projections while maintaining low discrepancy.[](https://artowen.su.domains/reports/rhalton.pdf)[](https://arxiv.org/abs/2405.15799) The permuted radical inverse is formally defined as

\phi_b^\pi(n) = \sum_{k=0}^\infty \frac{\pi(d_k)}{b^{k+1}},

\phi_b(n) = \sum_{k=0}^{\infty} d_k b^{-(k+1)}.

By convention, $\phi_b(0) = 0$.[](https://link.springer.com/article/10.1007/BF01386213) This function admits a straightforward iterative computation that avoids explicit digit storage, making it suitable for numerical implementation. The standard algorithm proceeds by successively extracting the base-$b$ digits of $n$ from least to most significant and accumulating their contributions to the fractional value. A pseudocode implementation is as follows: ``` function radical_inverse(b, n): if n == 0: return 0.0 result = 0.0 power = 1.0 / b while n > 0: result += (n % b) * power power /= b n = n // b # integer division return result ``` This approach ensures $O(\log_b n)$ time complexity, proportional to the number of digits in $n$'s base-$b$ expansion. For illustration, consider $b = 3$ and $n = 10$. The base-3 expansion of 10 is $101_3$, yielding digits $d_0 = 1$, $d_1 = 0$, $d_2 = 1$. Thus,

\phi_3(10) = \frac{1}{3} + \frac{0}{9} + \frac{1}{27} = \frac{9}{27} + \frac{1}{27} = \frac{10}{27} \approx 0.37037.

Applying [the algorithm](/page/The_Algorithm) confirms this: first iteration ($n=10$): digit 1, result $1 \times \frac{1}{3} = \frac{1}{3}$, $n=3$; second ($n=3$): digit 0, result $\frac{1}{3} + 0 \times \frac{1}{9} = \frac{1}{3}$, $n=1$; third ($n=1$): digit 1, result $\frac{1}{3} + 1 \times \frac{1}{27} = \frac{10}{27}$. ### Practical Algorithms and Permutations The Halton sequence in $d$ [dimensions](/page/Dimension) is generated by computing the radical inverse function $\phi_{p_i}(n)$ independently for each [dimension](/page/Dimension) $i = 1$ to $d$, where $p_i$ are the first $d$ prime numbers serving as [bases](/page/Base), and $n$ ranges from 0 to $N-1$ to produce $N$ points.[](https://web.maths.unsw.edu.au/~josefdick/MCQMC_Proceedings/MCQMC_Proceedings_2010_Preprints/OktenShahGoncharov-final.pdf) For each $n$, the value in [dimension](/page/Dimension) $i$ is obtained by expressing $n$ in [base](/page/Base) $p_i$ as digits $a_k a_{k-1} \dots a_1 a_0$, then forming $\phi_{p_i}(n) = \sum_{j=0}^k a_j / p_i^{j+1}$.[](https://artowen.su.domains/reports/rhalton.pdf) To reduce correlations between dimensions, especially in higher dimensions where bases are large, permutations are applied to the digits of the radical inverse. These permutations $\pi$ scramble the digit values $\{0, 1, \dots, p_i - 1\}$ for each base $p_i$, yielding a generalized Halton point $\phi_{p_i}^\pi(n) = \sum_{j=0}^k \pi(a_j) / p_i^{j+1}$.[](https://web.maths.unsw.edu.au/~josefdick/MCQMC_Proceedings/MCQMC_Proceedings_2010_Preprints/OktenShahGoncharov-final.pdf) Deterministic permutations, such as those based on linear congruential generators, decorrelate dimensions effectively; for example, $\pi(k) = (a k + c) \mod p_i$, where $a$ and $c$ are chosen to ensure $\pi$ is a full-period permutation (e.g., $a$ coprime to $p_i$, $c \neq 0$).[](https://www.cirm-math.fr/RepOrga/2255/Slides/slides-Okten1and2.pdf) Random permutations can also be used, independently for each digit position and dimension, to introduce variability while preserving low discrepancy.[](https://artowen.su.domains/reports/rhalton.pdf) For improved distribution in finite samples, the first $2^d$ points are sometimes omitted, as the initial segment may exhibit clustering near the origin or axes.[](https://people.sc.fsu.edu/~jburkardt/datasets/halton/halton.html) This skipping helps achieve better uniformity, particularly when $N$ is small relative to the dimension $d$.[](https://people.sc.fsu.edu/~jburkardt/datasets/halton/halton.html) A practical consideration for large $N$ is the base leap method, where instead of generating all points sequentially, every $l$-th index is taken ($n = m \cdot l$ for $m = 0, 1, \dots$), with $l$ chosen coprime to all bases $p_i$ to maintain low discrepancy in subsequences.[](https://www.mathworks.com/help/stats/haltonset.html) The following Python-like pseudocode illustrates generating a 2D Halton sequence with $N=100$ points using bases 2 and 3, applying a linear congruential permutation $\pi(k) = (k + 1) \mod p_i$ (with $a=1$, $c=1$) to each dimension's digits, and skipping the first $2^2 = 4$ points: ``` def radical_inverse_permuted(n, base, a=1, c=1): if n == 0: return 0.0 perm = lambda k: (a * k + c) % base result = 0.0 f = 1.0 / base while n > 0: digit = n % base result += perm(digit) * f f /= base n //= base return result def halton_2d(N, skip=4): points = [] base1, base2 = 2, 3 for i in range(skip, N + skip): x1 = radical_inverse_permuted(i, base1) x2 = radical_inverse_permuted(i, base2) points.append((x1, x2)) return points # Example usage sequence = halton_2d(100) ```[](https://artowen.su.domains/reports/rhalton.pdf)[](https://www.cirm-math.fr/RepOrga/2255/Slides/slides-Okten1and2.pdf)[](https://people.sc.fsu.edu/~jburkardt/datasets/halton/halton.html)

References

[1]
On the efficiency of certain quasi-random sequences of points in ...
Halton, J.H. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84–90 (1960). https ...
[2]
Quasi-Random Sequences - Prof. Michael T. Heath
Halton sequences, one of the earliest methods for generating quasi-random sequences, depend on choosing a prime number b as the base or radix to generate the ...
[3]
[PDF] Quasi-random simulation of discrete choice models
A Halton sequence is defined in terms of a base. The sequence in base 10 is most easily ex- plained; sequences in other bases are created the same as in base 10 ...
[4]
[PDF] From van der Corput to modern constructions of sequences for quasi ...
Jun 11, 2015 · Abstract. In 1935 J.G. van der Corput introduced a sequence which has excellent uniform distribution properties modulo 1.
[5]
[PDF] Uniform Distribution of Sequences
Uniform distribution of sequences. (Pure and applied mathematics) ... KUIPERS. H. NIEDERREITER. Page 10. Page 11. CONTENTS. Chapter 1 Uniform Distribution Mod 1.
[6]
8.6 Halton Sampler
The -dimensional Halton sequence is defined using the radical inverse base , with a different base for each dimension. The bases used must all be relatively ...
[7]
[PDF] Quasi-Random Sequences and Their Discrepancies
Examples of such sequences that will be considered below include the Halton sequence, Sobol' sequence, and Faure sequence. Bounds on the discrepancy of ...
[8]
[PDF] Random Number Generation and QuasimMonte Carlo Methods
the star discrepancy, the current "record holder" is a generalized van der Corput ... Recall that the Euler-Mascheroni constant is given by. -y = lim (F 1 ...
[9]
[PDF] Improved Halton sequences and discrepancy bounds
Using such scrambled one-dimensional sequences as coordinates of generalized Halton or generalized Faure sequences gives very good results in experi- ments with ...
[10]
[PDF] Simulation Estimation of Mixed Discrete Choice Models Using ...
2.1 The standard Halton sequence The standard Halton sequence is designed to span the domain of the S-dimensional unit. cube uniformly and efficiently (the ...
[11]
On the optimal Halton sequence - ScienceDirect.com
First a brief review of the Halton sequence is presented in Section 2. This is followed by the analysis of poor two-dimensional projections and correlations ...
[12]
Good permutations for deterministic scrambled Halton sequences in ...
Apparently, the results are best for the L 2 -star discrepancy, but also in the case of L 2 -extreme discrepancy the curve for the reverse Halton permutations ...
[13]
[PDF] A randomized Halton algorithm in R - Art Owen
Some QMC methods work best with specially chosen sample sizes such as large prime numbers or powers of small prime numbers. Halton se- quences can be used with ...
[14]
From van der Corput to modern constructions of sequences for quasi ...
Aug 6, 2025 · In 1935 J.G. van der Corput introduced a sequence which has excellent uniform distribution properties modulo 1. This sequence is based on a very ...
[15]
A note on Weyl's equidistribution theorem
Feb 14, 2025 · Weyl proved in Weyl (Eins Math Ann 77(3):313–352, 1916) that integer evaluations of polynomials are equidistributed mod 1 whenever at least ...
[16]
[PDF] on the discrepancy of the van der corput sequence indexed by ...
It is well-known that for any base b ≥ 2 the van der Corput sequence is uniformly distributed modulo one and that NDN (xn) = O(log N), see, for example, [1]. In ...
[17]
The generalized and modified Halton sequences in Cantor bases
Oct 22, 2018 · Perhaps the most famous example of a low-discrepancy sequence is the van der Corput sequence. In 1935, van der Corput [4] introduced a ...<|control11|><|separator|>
[18]
Quasi-Monte Carlo Integration - ScienceDirect.com
In this paper quasi-random (Halton, Sobol', and Faure) and pseudo-random sequences are compared in computational experiments designed to determine the effects ...Missing: seminal | Show results with:seminal
[19]
[PDF] Real-Time Reconstruction for Path-Traced Global Illumination
A low-discrepancy Halton sequence [Halton and Smith 1964] is used to sample light sources and scattering directions. We loop through a small set of Halton ...
[20]
[PDF] Sampling with Hammersley and Halton Points - Tien-Tsin Wong
We discuss the implementation issues and experience in choosing suitable bases of. Hammersley and Halton points on 2D plane and spherical surface. The ...Missing: diagonal | Show results with:diagonal<|control11|><|separator|>
[21]
On the distribution of points in a cube and the approximate ...
Volume 7, Issue 4, 1967, Pages 86-112 On the distribution of points in a cube and the approximate evaluation of integrals.Missing: original | Show results with:original
[22]
[PDF] ZANCO Journal of Pure and Applied Sciences Comparing Halton ...
The results show that the performance of Sobol sequence is better and more stable than Halton sequence. The results also show that Sobol sequence maintains the ...
[23]
[PDF] Monte Carlo and quasi-Monte Carlo methods
The resulting convergence rate is O((logN)kN~l). Because of the correlations, quasi-random sequences are less versatile than random or pseudo-random sequences.
[24]
[PDF] Random and Deterministic Digit Permutations of the Halton ...
The star discrepancy of the Halton sequence, or any low-discrepancy sequence, is O(N−1(logs N)). This fact, together with the Koksma-Hlawka inequality, lay the.
[25]
[PDF] Number sequences for simulation - CIRM
Example: Linear Congruential Generators. Introduced by Lehmer in 1949: xn ... The transformation can be generalized so that the orbit gives the permuted Halton ...
[26]
HALTON - Halton Datasets
In some cases, it is recommended that the initial portion of the sequence be skipped over. A general suggestion is to let STEP be the first power of 2 that is ...
[27]
haltonset - Halton quasirandom point set - MATLAB - MathWorks
Generate a three-dimensional Halton point set, skip the first 1000 values, and then retain every 101st point. p = haltonset(3,Skip=1e3,Leap=1e2). p = Halton ...