Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

It is common to use weights in applications like mixture modeling and to linearly combine basis functions. Weights $w_i$ must often obey $w_i ≥$ 0 and $\sum_{i} w_i=1$. I'd like to randomly choose a weight vector $\mathbf{w} = (w_1, w_2, …)$ from a uniform distribution of such vectors.

It may be tempting to use $w_i = \frac{\omega_i}{\sum_{j} \omega_j}$ where $\omega_i \sim$ U(0, 1), however as discussed in the comments below, the distribution of $\mathbf{w}$ is not uniform.

However, given the constraint $\sum_{i} w_i=1$, it seems that the underlying dimensionality of the problem is $n-1$, and that it should be possible to choose a $\mathbf{w}$ by choosing $n-1$ parameters according to some distribution and then computing the corresponding $\mathbf{w}$ from those parameters (because once $n-1$ of the weights are specified, the remaining weight is fully determined).

The problem appears to be similar to the sphere point picking problem (but, rather than picking 3-vectors whose $ℓ_2$ norm is unity, I want to pick $n$-vectors whose $ℓ_1$ norm is unity).

Thanks!

share|improve this question
2  
Your method does not generate a uniformly distributed vector on the simplex. To do what you want correctly, the most straightforward way is to generate $n$ iid $\mathrm{Exp}(1)$ random variables and then normalize them by their sum. You could try to do it by finding some other method to draw only $n-1$ variates directly, but I have my doubts regarding the efficiency tradeoff since $\mathrm{Exp}(1)$ variates can be very efficiently generated from $U(0,1)$ variates. –  cardinal Aug 9 '11 at 22:24

2 Answers 2

up vote 11 down vote accepted

Choose $\mathbf{x} \in [0,1]^{n-1}$ uniformly (by means of $n-1$ uniform reals in the interval $[0,1]$). Sort the coefficients so that $0 \le x_1 \le \cdots \le x_{n-1}$. Set

$$\mathbf{w} = (x_1, x_2-x_1, x_3 - x_2, \ldots, x_{n-1} - x_{n-2}, 1 - x_{n-1}).$$

Because we can recover the sorted $x_i$ by means of the partial sums of the $w_i$, the mapping $\mathbf{x} \to \mathbf{w}$ is $(n-1)!$ to 1; in particular, its image is the $n-1$ simplex in $\mathbb{R}^n$. Because (a) each swap in a sort is a linear transformation, (b) the preceding formula is linear, and (c) linear transformations preserve uniformity of distributions, the uniformity of $\mathbf{x}$ implies the uniformity of $\mathbf{w}$ on the $n-1$ simplex. In particular, note that the marginals of $\mathbf{w}$ are not necessarily independent.

3D point plot

This 3D point plot shows the results of 2000 iterations of this algorithm for $n=3$. The points are confined to the simplex and are approximately uniformly distributed over it.


Because the execution time of this algorithm is $O(n \log(n)) \gg O(n)$, it is inefficient for large $n$. But this does answer the question! A better way (in general) to generate uniformly distributed values on the $n-1$-simplex is to draw $n$ uniform reals $(x_1, \ldots, x_n)$ on the interval $[0,1]$, compute

$$y_i = -\log(x_i)$$

(which makes each $y_i$ positive with probability $1$, whence their sum is almost surely nonzero) and set

$$\mathbf w = (y_1, y_2, \ldots, y_n) / (y_1 + y_2 + \cdots + y_n).$$

This works because each $y_i$ has a $\Gamma(1)$ distribution, which implies $\mathbf w$ has a Dirichlet$(1,1,1)$ distribution--and that is uniform.

[3D point plot 2]

share|improve this answer
    
Is this an algorithm for sampling from Dir(1)? –  Chris Aug 10 '11 at 10:48
    
@Chris If by "Dir(1)" you mean the Dirichlet distribution with parameters $(\alpha_1, \ldots, \alpha_n)$ = $(1,1,\ldots,1)$, then the answer is yes. –  whuber Aug 10 '11 at 12:04
    
Thanks @whuber. –  Chris Aug 10 '11 at 12:20
    
(+1) One minor comment: The intuition is excellent. Care in interpreting (a) may need to be taken, as it seems that the "linear transformation" in that part is a random one. However, this is easily worked around at the expense of additional formality by using exchangeability of the generating process and a certain invariance property. –  cardinal Aug 10 '11 at 12:25
1  
@whuber: Interesting remarks. Thanks for sharing! I always appreciate your insightful thoughts on such things. Regarding my previous comment on "random linear transformation", my point was that, at least through $\mathbf{x}$, the transformation used depends on the sample point $\omega$. Another way to think of it is there is a fixed, predetermined function $T: \mathbb{R}^{n-1} \to \mathbb{R}^{n-1}$ such that $\mathbf{w} = T(\mathbf{x})$, but I wouldn't call that function linear, though it is linear on subsets that partition the $(n-1)$-cube. :) –  cardinal Aug 10 '11 at 16:48
    zz <- c(0, log(-log(runif(n-1))))
    ezz <- exp(zz)
    w <- ezz/sum(ezz)

The first entry is put to zero for identification; you would see that done in multinomial logistic models. Of course, in multinomial models, you would also have covariates under the exponents, rather than just the random zzs. The distribution of the zzs is the extreme value distribution; you'd need this to ensure that the resulting weights are i.i.d. I initially put rnormals there, but then had a gut feeling that this ain't gonna work.

share|improve this answer
    
That doesn't work. Did you try looking at a histogram? –  cardinal Aug 9 '11 at 21:53
    
So what should we expect to see on a histogram? I don't know, frankly. The distribution of weights can't be U[0,1]. hist(w) is a skewed distribution, but that's inevitable with non-linear transformations of i.i.d.s. –  StasK Aug 9 '11 at 21:58
4  
Your answer is now almost correct. If you generate $n$ iid $\mathrm{Exp}(1)$ and divide each by the sum, then you will get the correct distribution. See Dirichlet distribution for more details, though it doesn't discuss this explicitly. –  cardinal Aug 9 '11 at 22:02
1  
Given the terminology you are using, you sound a little confused. –  cardinal Aug 9 '11 at 22:21
2  
Actually, the Wiki link does discuss this (fairly) explicitly. See the second paragraph under the Support heading. –  cardinal Aug 9 '11 at 22:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.