1

How to generate a vectors, uniformely distributed into convex polytope? I awared of the solution of reduced problem: uniform sampling on a unit simplex. Also I know how to split (even non-convex) polytope into the simplicial pieces (by means of Delaunay triangulation). Having such splitting I can simply work with particular simplicies, considering its hypervolumes as weights.

But how to deal with just a simplicies? I can't simply deform the unit simplex (internals of which consists of random points) to give the arbitrary simplex only using linear transformations. The uniformity of spatial distribution is violated in such case.

I awared that Dirichlet distribution is connected to the problem. But I do not know the means of how to.

I suspect that there is some functional (maybe linear?) dependency between parametres of Gamma-distributions of the components and dot products of radius-vectors of simplex vertices (Gramian matrix, just a supposition).

EDIT:

I want to specifically note, that only the rejection-step-less algorithms are interested. Or, another words, optimal in sense of minimum of amount of generated uniformely distributed "source" values.

EDIT:

Finally I found the solution.

Community
  • 1
  • 1
Tomilov Anatoliy
  • 15,657
  • 10
  • 64
  • 169
  • 2
    One way would be to use acceptance/rejection. Generate values uniformly over the unit simplex and throw them away if they don't fall within your desired simplex. Depending on the relative volumes involved, this isn't necessarily all that inefficient. – pjs Jul 17 '14 at 10:36
  • @pjs OK, I can simply generate random points into bounding box hypercube/parallelotope, then makes a rejection step for the points not lies into an intersection of the corresponding halfspaces. But if I have simplex=(origin + scaled orts) the hypervolume of the simplex is `n!` times less than hypervolume of the correspoinding parallelotope. So, there is worse than even exponential degradation of performance WRT growing of dimensionalities of concerned spaces. – Tomilov Anatoliy Jul 17 '14 at 10:44
  • 2
    "I can't simply deform the unit simplex to give the arbitrary simplex only using linear transformations." Really? – Henrik Jul 17 '14 at 10:52
  • @Henrik Be sure! You just can imagine the simpliest case: 2-simplex - equilateral triangle. Let's begin to squeeze one of the sides. The points near the side in direction of this side (imagine any collinear vector) begins concentrate. The points near the opposite vertex no (and especially in direction of corresponding altitude). Isn't it? – Tomilov Anatoliy Jul 17 '14 at 10:58
  • You can greatly improve the efficiency by creating outer bounds that are easy to generate over (hyperrectangles or hyperspheres) that are mutually exclusive and closely bound subsections of your simplex. Pick a bounding segment with probability proportional to its volume, then do the acceptance/rejection with high probability of acceptance. You can also define inner volumes in which points are always accepted, so the only marginal cases are near the boundaries of your simplex. – pjs Jul 17 '14 at 10:58
  • @Orient Assume one of the vertices has coordinates (0,0). If the triangle is not degenerate, there is certainly a linear transform that maps the other two vertices to (0,1) and (1,0) respectively. – Henrik Jul 17 '14 at 11:08
  • @Henrik Please read [this](http://cs.stackexchange.com/questions/3227/uniform-sampling-from-a-simplex/3229#3229). Simple projections generally violates uniformity of distribution. – Tomilov Anatoliy Jul 17 '14 at 11:12
  • @Henrik Another usefull notes is [here](http://stackoverflow.com/questions/3010837/sample-uniformly-at-random-from-an-n-dimensional-unit-simplex/3080946#3080946). – Tomilov Anatoliy Jul 17 '14 at 11:13
  • I suspect you'll have better chances to get a good answer if you drop the c++ and ask on one math.se or cs.se. – CodesInChaos Jul 18 '14 at 13:13
  • 1
    Orient, @Henrik is correct. You are confused. You linked to something pointing out that you can't normalize a *hypercube* in a silly way to get a uniform distribution on a simplex. Henrik is correct that an invertible linear transformation of the uniform distribution on the unit simplex gives a uniform distribution on another simplex of the same dimension. (If you project to a lower dimensional simplex then the projected distribution is typically not uniform.) – Douglas Zare Jul 20 '14 at 12:05
  • Henrik @DouglasZare You are right. Both. Thank you. – Tomilov Anatoliy Jul 25 '14 at 03:32
  • I think this report answers your problem https://www.brown.edu/academics/public-health/research/evidence-based-medicine/sites/brown.edu.academics.public-health.research.evidence-based-medicine/files/uploads/EfficientsamplingSMAA.pdf – Khoa Jul 17 '16 at 02:58

0 Answers0