Simulating uniformly on $S^1=\{x \in \mathbb{R}^n \mid \|x\|_1=1\}$

A scheme to generate random variates distributed uniformly in $S^2=\{x\in \mathbb{R}^n \mid \|x\|_2=1\}$ is well known: generate a standard normal variate in $\mathbb{R}^n$ and normalize it to unit norm.

Is there a similarly simple and clever procedure to simulate uniformly distributed variates on the $1$-ball $S^1=\{x \in \mathbb{R}^n \mid \|x\|_1=1\}$?

Solution 1:

Flip $n$ fair coins to pick an orthant—that is, to pick the signs of the coordinates of the point you are choosing. Now pick a point uniformly in the standard simplex, and flip the signs of its coordinates according to what the coins told you.

Solution 2:

Does the following work? (read the comment of joriki to convince yourself that the algorithm works --- thanks joriki)

Cut a line of length 1 into $n$ parts. Mathematically, throw $n-1$ random numbers between uniform between 0 and 1. Sort them to obtain $\mathbf{s}=(0,s_1, \dots, s_{n-1},1)$ with $s_i \leq s_j$; $\forall i <j$.

Take the point $\mathbf{x}= \left[\sigma_1(s_1- s_0), \sigma_2(s_2 - s_1), \dots, \sigma_n(s_n - s_{n-1})\right] \in S^1$. Here, $\sigma_i = \pm 1$ are randomly choosen. It is quite clear that $\mathbf{x}$ is on the unit sphere. The question remains: is it uniform on the sphere?

Solution 3:

Here's the method I proposed in the comment. Pick a random point $(x_1,\ldots,x_{n-1})$ from the $n-1$-dimensional hypercube. (This amounts to choosing $n-1$ real numbers uniformly in $[0,1]$)

Now, if $\sum_{i=1}^{n} x_i \geq 1$ throw the point out and start again, if not keep it.

Transform the point using the following affine map:

$$f:\mathbb{R}^{n-1}\to\mathbb{R}^{n}: (x_1,\ldots,x_{n-1}) \mapsto (x_1,\ldots,x_{n-1},1-\sum_{i=1}^{n} x_i) \; .$$

Now, similarly to what Fabian does, select $n$ signs $\sigma_i=\pm 1$ randomly and multiply each component of the vector you obtained by these signs.

As pointed out already by joriki and Gerben, for high dimensions, this method is very wasteful since a fraction $\frac{(n-1)!-1}{(n-1)!}$ points will have to be thrown out.