Exercise: Why Halton fails in high dimensions — projection pathology

The Halton sequence uses prime bases: $p_1 = 2, p_2 = 3, p_3 = 5, \ldots$ The $j$-th coordinate of point $n$ is $\phi_{p_j}(n)$, the radical inverse of $n$ in base $p_j$.

Tasks

1. Generate the first $N = 1000$ points of the 30-dimensional Halton sequence. Plot the 2D projections $(x^{(1)}, x^{(2)})$ (dimensions 1 and 2, bases $2, 3$) and $(x^{(29)}, x^{(30)})$ (dimensions 29 and 30, bases $113, 127$).

2. Describe the visual pattern in each projection. Why are the two so different?

3. Compute the 2-dimensional star-discrepancy of each projection numerically using a Monte Carlo approximation (sample many test boxes, take the max deviation). Compare.

4. Explain the mathematical reason: for consecutive integers $n$ and $n+1$, $\phi_{p}(n+1) - \phi_{p}(n) \approx 1/p$ (modulo "carry" effects), so when $p_j, p_k$ are both large, consecutive Halton points are close in both coordinates, tracing parallel lines.

5. Leaped Halton — one fix — takes every $\ell$-th point for well-chosen $\ell$. Explain how leaping disrupts the projection pathology and why Sobol sequences avoid the problem structurally.

Hint