5
$\begingroup$

Let $\mathcal{P}$ be the convex hull of a point set $p_1, \dotsc, p_n$ (for simplicity, assume that no $p \in P$ lies in the convex hull of the other points.) Now, pick a point uniformly at random from the simplex $x_1 + \dotsc + x_n = 1, x_i \geq 0,$ and take $\phi=\sum x_i p_i.$ The point $\phi$ will be contained in $\mathcal{P}$ and in the simple case where $\mathcal{P}$ is a triangle, $\phi$ is uniformly distributed. In general, however, it is not: The two graphics are for the case $\mathcal{P}$ is a square. The first is a simple plot of a million points sampled from the distribution - the distribution looks like it is trying to be supported on the quadrangle spanned by the midpoints of the sides of the square.

enter image description here

The second is the density histogram: enter image description here

which seems to indicate that the distribution has a bit of a peak at the center of gravity.

Any deep thoughts?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ For the square, the density seems to be proportional to $\min\{x+y,2-x-y\}-\max\{x-y,y-x\}=2\min\{x,y,1-x,1-y\}$ (take the uniform distribution in the tetrahedron spanned by $(0,0,0)$, $(1,1,0)$, $(1,0,1)$, $(0,1,1)$ and project it on the $xy$ plane), which does not agree with your plots. What did I miss? $\endgroup$
    – Mateusz Kwaśnicki
    Mar 24, 2018 at 19:50
  • $\begingroup$ Linearity of expectation implies that $E(\sum X_i P_i)=\sum E(X_i)P_i =\sum \frac{1}{n}P_i=G,$ where $G$ is the center of gravity. Also, you should have a look at this paper: dtic.mil/dtic/tr/fulltext/u2/273207.pdf $\endgroup$
    – Donatien Bénéat
    Mar 25, 2018 at 7:20
  • $\begingroup$ Maybe the fact that barycentric coordinates aren't equal to the $x_i$ for polygons, that are not triangles, plays a rôle, c.f. uniqueness issues for barycentric coordinates $\endgroup$
    – Manfred Weis
    Mar 25, 2018 at 18:18

1 Answer 1

Reset to default
2
$\begingroup$

The problem seems to lie in the way you sample the unit simplex. Let $(U_i)_{1\leq i\leq n}$ be a sequence of i.i.d. uniform random variables, $S=\sum U_i$ and define $X_i=U_i/S.$ Then non-intuitively, $(X_1,\dots,X_n)$ is not uniformly distributed over the unit simplex. The following plot shows 300000 points on the unit square with barycentric coordinates generated using this method:

First method

The method can easily be fixed: if the $U_i$s defined above are i.i.d. exponential random variables, then $(X_1,\dots,X_n)$ is uniformly distributed over the simplex. Again, the following plot shows 300000 points generated according to this second method:

Second method

It should be noted that uniformly distributed $X_i$s doesn't imply uniformly distributed $\phi,$ as said by Mateusz Kwaśnicki in a comment.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ As a side remark: Another simple method is to generate $X_1,X_2,\ldots,X_n$ is to arrange $U_1,U_2,\ldots,U_{n-1}$ in a non-decreasing order, $V_1\leqslant V_2\leqslant \ldots \leqslant V_{n-1}$, and set $X_i = V_{i+1}-V_i$ for $i = 1, 2,\ldots, n - 1$, $X_n = 1 + X_1 - X_n$. $\endgroup$
    – Mateusz Kwaśnicki
    Mar 26, 2018 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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