Sampling from the diamond: $|x_1|+\ldots+|x_n| \le 1$? 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.
 A: 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:


*

*Generate 500 $y_i$ on the interval (0,1)

*$z_i = - \log y_i$

*$S = \sum z_i$.

*$x_i = \frac{z_i}{S}$


I don't really understand it and can't vouch for it being correct though.
A: 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$.
