Sampling from the diamond: $|x_1|+\ldots+|x_n| \le 1$?

Question

Let $\left(x_1, \ldots, x_n \right)$ be a point in $\mathbb R^n$.
Sample uniformly at random from the diamond $$ |x_1|+\ldots+|x_n| \le 1. $$

In $\mathbb R^2$, one way is to sample the square, then translate/reflect any point that fall outside the diamond, back into the diamond.
But in $\mathbb R^n$, this doesn't work.

I considered rejection sampling. But, as my target dimension is $n=500$.
The rejection rate will be too high.

Answer 1

You can constrain your problem to finding a point in a simplex where each $x_i \ge 0$ and $\sum x_i \le 1$, then generate 500 random bits and negate the corresponding $x_i$.

The simplex is the n-dimensional version of a triangle or tetrahedron. I googled over my head and found this. Don't ask me to explain it, though. :)

Uniform distribution on a simplex via i.i.d. random variables

https://stackoverflow.com/questions/3010837/sample-uniformly-at-random-from-an-n-dimensional-unit-simplex

Sampling uniformly in the Unit Simplex

Sampling frmo the simplex

After looking at these I've seen this algorithm crop up:

1. Generate 500 $y_i$ on the interval (0,1)
2. $z_i = - \log y_i$
3. $S = \sum z_i$.
4. $x_i = \frac{z_i}{S}$

I don't really understand it and can't vouch for it being correct though.

Answer 2

Here is a sketch of an idea. Suppose we know $|x_i|$ for $i=1,\ldots, n$ then by tossing a fair coin we can attach $\pm$ to each of the $x_i$'s. Now let us focus on sampling $|x_i|$ for all $i$. Step 1) Uniformly randomly select an index from $1,\ldots,n$. Then, generate $U_1 = U[0,1]$. We now have a budget of $1 - U_1$ left. Step 2) We pick another index uniformly from the remaining indices and set it to $U_2 = (1- U_1)U[0,1]$. We now have a budget of $1 - U_1 - U_2$ left. Like this continue till step $n$.