3
$\begingroup$

I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices).

One way to efficiently generate points that are uniformly distributed over the ENTIRETY of the $k$-simplex is to generate samples of $k$ iid exponential random variables, $E_i$, $i\in \left[1,k\right]$, then normalize, and $\vec{X}=\frac{\left\langle E_1,E_2,\dots,E_k\right\rangle}{\sum_{i=1}^k E_i}$, will be uniformly distributed over the entire $k$-simplex.

My problem is that the probability that one of these points lands on the surface (i.e. at a vertex, or along a hyper-edge, or on hyper-face, etc.) is nearly $0$, so that in practice all of the points end up being in the INTERIOR of the $k$-simplex.

In an attempt to sample the SURFACE of the $k$-simplex I have considered each hyper-edge, hyper-face, etc. separately and generated uniformly distributed samples on each (since they are themselves lower dimensional simplices). However, the problem becomes computationally unfeasible as $k$ increases because the number of hyper-edges, hyper-faces, etc. blows up.

Does anyone know of a method to explicitly generate samples that are uniformly distributed over the SURFACE (or BOUNDARY) of a standard $k$-simplex?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ There are only $k+1$ facets on the surface. Where does the unfeasibility come from? $\endgroup$
    – Chao Xu
    Dec 18, 2013 at 21:12
  • 7
    $\begingroup$ I'm not sure I understand the problem. If you're sampling uniformly form the k-simplex, then the union of all the $k-1$-simplexes (i.e the faces) is a set of measure zero. It's hardly surprising therefore that you'll miss out on getting the surface facets. If you want to sample explicitly from the surface, then as Chao Xu points out there are k+1 facets, and so you can easily sample by picking a facet at random and then running the standard algorithm on it. Or even easier, sample from the $k-1$-simplex, and insert a zero randomly. $\endgroup$
    – Suresh Venkat
    Dec 19, 2013 at 18:25

1 Answer 1

Reset to default
-2
$\begingroup$

I created an algorithm for that. for detail see http://www.sciencedirect.com/science/article/pii/0098300493900457

briefly speaking, you can use following recursive formula to generate:

x_1=1-R_1^{1/n-1}
x_k=(1-\sum_{i=1}^{k} x_i)(1-R_k^{1/n-k}),    k=2,…,n-1
x_n=1-\sum_{i=1}^{n-1} x_i

Best wishes

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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