Any point in a convex polytope can be expressed as a convex linear combination of the n vertices. The coefficients of these convex linear combinations are positive and add up to 1. They are called barycentric coordinates. Therefore, they are in the n-part simplex S^n, which is (n-1)-dimensional. In compositional data analysis some families of logistic transformations from S^n into R^{n-1} are frequently used. They are called alr (additive-log-ratio, Aitchison 1986), ilr (isometric log-ratio, Egozcue et al. 2003) or even clr (centered log-ratio, Aitchison 1986). All of them are invertible, so that a simulated sample in R^{n-1} can be transformed, first to the simplex S^n via alr^{-1}, ilr^{-1} or clr^{-1}, and then into the polytope via barycentric coordinates.

For your specific case I would recommend to use alr transformation (also known as logistic transformation; its use is also frequent in logistic regression). If X=(x_1, x_2, ..., x_{n-1}) is a vector in R^{n-1}, Y=alr^{-1}(X)= C exp[x_1, x_2, ..., x_{n-1},0] , where C is a normalising constant such that the X's components add to 1 and Y is in S^n. The alr-transformation is defined as X = log[y_1/y_n, y_2/y_n, ..., y_{n-1}/y_n].

If you know the distribution you want to simulate in the coordinates Y the problem is solved. However, I guess that your distribution is defined and known on R^n and then restricted to the polytope (e.g. a multivariate normal distribution). This kind of choice is frequently based on the convenience. In this case there is no convenience at all. I would recommend to define a (n-1)-multivariate normal distribution on the alr-coordinates, simulate it, and then translate it into the polytope: R^{n-1}--alr^{n-1}--> S^n -- barycentric coord --> polytope.

Any point in a convex polytope can be expressed as a convex linear combination of the n vertices. The coefficients of these convex linear combinations are positive and add up to 1. They are called barycentric coordinates. Therefore, they are in the n-part simplex S^n, which is (n-1)-dimensional. In compositional data analysis some families of logistic transformations from S^n into R^{n-1} are frequently used. They are called alr (additive-log-ratio, Aitchison 1986), ilr (isometric log-ratio, Egozcue et al. 2003) or even clr (centered log-ratio, Aitchison 1986). All of them are invertible, so that a simulated sample in R^{n-1} can be transformed, first to the simplex S^n via alr^{-1}, ilr^{-1} or clr^{-1}, and then into the polytope via barycentric coordinates.

For your specific case I would recommend to use alr transformation (also known as logistic transformation; its use is also frequent in logistic regression). If X=(x_1, x_2, ..., x_{n-1}) is a vector in R^{n-1}, Y=alr^{-1}(X)= C exp[x_1, x_2, ..., x_{n-1},0] , where C is a normalising constant such that the X's components add to 1 and Y is in S^n. The alr-transformation is defined as X = log[y_1/y_n, y_2/y_n, ..., y_{n-1}/y_n].

If you know the distribution you want to simulate in the coordinates Y the problem is solved. However, I guess that your distribution is defined and known on R^n and then restricted to the polytope (e.g. a multivariate normal distribution). This kind of choice is frequently based on the convenience. In this case there is no convenience at all. I would recommend to define a (n-1)-multivariate normal distribution on the alr-coordinates, simulate it, and then translate it into the polytope: R^{n-1}--alr^{n-1}--> S^n -- barycentric coord --> polytope.

I thank you very much for the suggestion, It seems like a good idea, and I will try it out. Nonetheless, I will add a further degree of complexity to the problem: what if the convex polytope has finitely many vertices, so that a priori enumeration of them all is computationally prohibitive? As far as I understood the use of the abovementionted transformations, I need all vertices in order to obtain the normalising constant. I know a way of overcoming it is to use Markov Chain Monte Carlo, so that I could sample the vertices and interior points could be obtained by convex combinations. Is this procedure feasible, or am I missing something?

Dear Anselmo,

Now your problem is becoming more complex. Probably, there is some way out via Markov Chains. However, I have no experience on this and I cannot help you. Sorry.

I thank you for the help, and I will let you know about any successful result.

Dear Anselmo,

I was thinking a bit about your problem. I would recommend you to read about ilr-transformation (from the simplex to R^{n-1}). In many situations it can be computed recursively via sequential binary partitions (SBP) and defining orthonormal coordinates called balances. It can be computed for a limited number of parts (dimension-1) and then new coordinates can be added without modifying the previous ones. These coordinates represent orthogonal projections on simplices of increasing dimension. Also note that normalising constants are not important at all as all used coordinates cancel out these constants...

Some references in (LaTex) bib format follow:

Theory, for citing but not for first reading:

@ARTICLE{EP05,

author = {Egozcue, J. J. and Pawlowsky-Glahn, V.},

title = {Groups of parts and their balances in compositional data analysis},

journal = {Mathematical Geology},

year = {2005},

volume = {37},

number = {7},

pages = {795-828},

}

Theory, most details are here in a simplified mathematical language

@BOOK{EP06a,

AUTHOR = {Egozcue, J. J. and V. Pawlowsky-Glahn},

TITLE = {Simplicial geometry for compositional data},

PUBLISHER = {In: Buccianti, A., Mateu-Figueras, G. and Pawlowsky-Glahn, V., (eds)

\emph{ Compositional Data Analysis in the Geosciences: From Theory to Practice.}

Geological Society, London,

Special Publications, 264, 67--77},

YEAR = {2006},

isbn = {1-86239-205-6},

}

Updated compendium of geometry of the simplex (and references therein)

@BOOK{EB+2011,

AUTHOR = {Egozcue, J. J. and Barcel\'o-Vidal, C. and Mart{\'\i}n-Fern\'andez, J. A. and Jarauta-Bragulat, E. and D{\'\i}az-Barrero, J. L. and Mateu-Figueras, G.},

TITLE = {Elements of simplicial linear algebra and geometry},

PUBLISHER = {In: Pawlowsky-Glahn, V. and Buccianti A. (eds.),

\emph{Compositional Data Analysis: Theory and Applications}, Wiley, Chichester UK},

YEAR = {2011},

isbn = {0-470-71135-3},

}

After some bibliographical research, I have come across some publications which approach the problem of uniform sampling from convex bodies, in particular convex polytopes, through hit-and-run algorithms. The main motivation of these algorithms is to estimate the volume of the convex body. The approach you suggest seems to be completely different, and I will struggle during some time to comprehend it, given my total lack of background in compositional data analysis. Thank you for the useful references, I will look for them.

http://luc.devroye.org/chapter_eleven.pdf

Starting on Page 568, in Particular Theorem 2.1.

Anselmo, would you mind posting some links to these publications where the motivation is to estimate the volume of the convex body? I am very interested in this.

Here it is:

http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf

Compute the bounding box of the polytope (this can be done by solving linear programs). Then do rejection-sampling :)

Hi Anselmo,

I am searching for the same solution to your problem and I found this note on the net which is similar to Juan's guidance but with more details. Hope this helps

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