Overview
A Halton sequence maps an integer index through radical-inverse functions in different prime bases. The resulting points cover low-dimensional unit domains more evenly than many pseudorandom samples.
CoreSource checked
Halton Sequence
Generates deterministic low-discrepancy points from radical inverses in prime bases.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Randomness & Sampling
- Difficulty
- Intermediate
- Family
- Low-Discrepancy Sequence
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
radical inverseprime baselow discrepancydeterministic sampling
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(dimensions log n)
Average
O(samples * dimensions log n)
Worst
O(samples * dimensions log n)
Space
O(1)
When to Use
- Use when deterministic coverage of a low-dimensional unit domain is useful.
- Use when reproducibility matters more than independent random draws.
When Not to Use
- Avoid in high dimensions without scrambling or careful base choices.
- Avoid when independent random samples are required by the analysis.
What It Does
- Converts sample indices through radical-inverse functions
- Uses different prime bases per dimension
- Produces deterministic low-discrepancy sample points
Use Cases
- Quasi-Monte Carlo integration
- Deterministic sampling in low-dimensional domains
- Repeatable design-of-experiment point sets
Inputs
- Random source
- Distribution or weights
- Sample count
Outputs
- Samples
- Estimated statistic
- Randomized selection
Key Formulas (1)
Radical inverse
xi = radicalinverse base b(i)
x_i = radical_inverse_base_b(i)Maps an integer index to a low-discrepancy sample coordinate.
Pseudocode
- 1.Choose one prime base for each dimension
- 2.For each sample index
- 3.Compute the radical inverse of the index in each base
- 4.Combine those values into one point
- 5.Repeat until the requested sample count is reached
Canonical Example
- Input
- indices 1, 2, 3 in bases 2 and 3
- Output
- 2D points such as (0.5, 1/3), (0.25, 2/3), (0.75, 1/9)
- Explanation
- Each coordinate is the radical inverse of the same index in a different prime base.
Implementation Notes
- Implement radical inverse separately and test it in a single base.
- Use the first few prime bases consistently across dimensions.
- Consider scrambling when artifacts matter.
Common Pitfalls
- High-dimensional Halton sequences can show correlation artifacts.
- Starting at index zero or one must be consistent across implementations.
- Treating deterministic low-discrepancy points as independent random samples can invalidate uncertainty estimates.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryPlot generated samples against the target distribution or domain.
Step 1 of 5: Choose one prime base for each dimension
randomness-sampling-mechanismNotes
Halton sequences are deterministic; randomized error estimates need additional scrambling or sampling strategy.
Sources (2)
What each reference supports for this entry.
Random Number Generation and Quasi-Monte Carlo Methods
BookQuasi-Monte Carlo reference for Halton Sequence's low-discrepancy construction and integration use case.
On the Optimal Halton Sequence
PaperSpecific reference for Halton low-discrepancy sequences, radical-inverse construction, and correlation issues.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toSobol Sequence
Randomness & Sampling · Extended
Halton and Sobol sequences are both low-discrepancy sampling methods.
Compare with thisRelationships
View full relationship pageConceptual neighborHammersley Sequence
Hammersley sequences also use radical inverse coordinates.
Alternative toSobol Sequence
Halton and Sobol sequences are both low-discrepancy sampling methods.
Related Algorithms
Tags
Randomness & SamplingLow-DiscrepancyQuasi Monte CarloSampling