Quasi-Monte Carlo sampling with a summation constraint

Question

The problem Given arbitrary integers $n$ and $d$, I want to sample $n$ data points, each of dimension $d$. An additional constraint should be satisfied, namely that the values of each individual data point should sum to 1. I want the generated set to be of low-discrepancy (evenly spread in the space, with little gaps).

My attempt Sampling low-discrepency sets is typically done by Quasi-Monte Carlo sampling, for example by means of the Halton sequence. For $n=16$ and $d=2$, a Halton sequence will produce the following:

One method would be to normalise each data point such that the constraint (each data point should sum to 1) is satisfied, but doing so will not leave the low-discrepancy property intact. This is shown below: the points are clearly not evenly spread across the diagonal line and there are gaps and clusters among them.

For $d=2$, the solution $\{\{\frac{0}{n}, \frac{n}{n}\}, \{\frac{1}{n}, \frac{n-1}{n}\}, ... , \{\frac{n}{n}, \frac{0}{n}\} \}$ should satisfy. But for $d \geq 3$, I am not sure what a good solution would be. I tried searching for literature that discusses this problem but was unable to find anything useful.

The question What is an effective way to do low-discrepency sampling while maintaining this 'summation' constraint? Can anyone point me to some relevant literature?

Thanks in advance.

Answer 1

Fleshing my comment out to an answer. I'm not sure that this will work, but I think it's worth trying.

Let $H_n^d$ denote the first $n$ points from the $d$-dimensional Halton sequence. Since you're really trying to generate points on a $(d-1)$-dimensional space, consider generating $x_n := H_n^{d-1}$, then setting the $d^{\text{th}}$ coordinate of each of the points in $x_n$ to be $ 1- \sum_{i=1}^{d-1} x_i$.

The catch is that in many cases, this last coordinate will be negative, which is undesirable -- but we can just discard the points in $x_n$ for which that holds and oversample points until we have the number of them we need. If you generate $d-1$ independent uniformly random numbers, the probability that their sum will be less than $1$ is $\frac{1}{(d-1)!}$, so that gives a good heuristic for how many we'd need to generate. The modified algorithm would look something like this:

• generate $x_n := H_{(d-1)! \cdot n}^{d-1}$ (you might need a few more terms than $(d-1)! \cdot n$ to account for the non-randomness of the Halton sequence)
• set the $d^{\text{th}}$ coordinate of each point in $x_n$ to be $1 - \sum_{i=1}^{d-1} x_i$
• discard the elements in $x_n$ for which the final coordinate is negative

Unless I'm underthinking something, it seems clear to me that if you take points generated in this way and project them down to the first $d-1$ coordinates, they'll have the desired distribution (sparsely covering the whole space). It would probably be wise to project them to other $(d-1)$-dimensional subspaces to be sure that they haven't clumped together in a way that's not obvious to me.