4
$\begingroup$

Let the dimension n=200 be fixed. The problem I am interested in is sampling points in n-dimensional Euclidean space uniformly from the region $$ \sum_{i=1}^{n} x_{i}\leq 1, $$ where $0\leq x_{i}\leq 1$ for all $1\leq i\leq n$.

One naive approach is to sample n points uniformly from the unit cube and then reject the sample if the sum is greater than 1. But this is a very inefficient approach. By simple MonteCarlo simulations I am observing that the Probability of the event $\sum_{i=1}^{n} x_{i}\leq 1$ is less than $10^{-6}$.

So is there any efficient way to do this sampling?

$\endgroup$
6
  • 2
    $\begingroup$ First sample $\sum_{i=1}^n x_i=S\in[0,1]$ using $p_S(s)\propto s^{n-1}$. Then sample uniformly from simplex $S=s$ using one of these algorithms. $\endgroup$
    – A.S.
    Nov 12, 2015 at 4:32
  • $\begingroup$ Btw, probability of $S\le 1$ for naive sampling is $\frac 1 {n!}$ which is much smaller than $10^{-6}$. $\endgroup$
    – A.S.
    Nov 12, 2015 at 4:41
  • 1
    $\begingroup$ Or, even simpler, sample uniformly from $\sum_{i=1}^{n+1}x_i=1$ and drop the last coordinate. $\endgroup$
    – A.S.
    Nov 12, 2015 at 5:16
  • $\begingroup$ I thought about the sampling from simplex and then scaling the norms in approppriate way so as to fill the region similar to sampling in a unit ball via sampling on a sphere first. But didn't know the property $p_{S}(s)\propto s^{n-1}$. Is it trivial to see this? $\endgroup$ Nov 12, 2015 at 6:27
  • $\begingroup$ Yes. $S=s$ is a $n-1$ dimensional subspace, so its "volume" is proportional to the linear scale ($s$) to the power ${n-1}$. Scaling is similar to sphere/ball. $\endgroup$
    – A.S.
    Nov 12, 2015 at 6:38

0

You must log in to answer this question.

Browse other questions tagged .