15
$\begingroup$

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\}$?

  • 0
    @joriki correct. @lundmark correct. Sorry for the sloppy language. It was edited. @gerben correct. I thought of that procedure, but it's highly inefficient.2011-03-07

3 Answers 3

14

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.

  • 7
    (+1) It is quite unfortunate that the authors of that paper have expended so much energy, and so recently(!), at promoting the Kraemer algorithm with $O(n \log n)$ runtime. A simpler $O(n)$ algorithm is as follows: Let $X_1, \ldots, X_n$ be iid unit exponential random variables and $S = \sum_i X_i$. Define $Y_i = X_i / S$. Then $(Y_1, \ldots, Y_n)$ is uniform in the standard simplex. Generating $X_i$ from standard uniforms is easy, just take $X_i = -\log(U_i)$ for $U_i \sim \mathcal U(0,1)$. For more general related issues, [click here](http://en.wikipedia.org/wiki/Dirichlet_distribution).2011-09-21
9

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 .

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?

  • 0
    @Fabian: (+1) This algorithm is quite nice and clever. One drawback is that it is $O(n\log n)$, whereas there are simple $O(n)$ approaches. See my comment to Mariano.2011-09-21
1

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.

  • 0
    Yeah, it's no good beyond dimension 3 or 4.2011-03-06