5
$\begingroup$

Note : Having spent some time over the original problem below, I saw that it can be boiled down to a simpler problem.

Here is that simpler problem :

In a vectorial space (over $\mathbb{R}$) of dimension n, consider the intersection of an hyperplane H of dimension m < n with an orthant (extension of a quadrant to several dimensions).

First question : how many extreme points (vertices) can I have ? I would be happy with only the maximum of that number depending on n and m.

Second question : find a efficient algorithm to enumerate the coordinates of those extreme points having the linear equation linked with the hyperplane.

I tried to reason in the simple case where the intersection of the hyperplane with any facet of the orthant (dimension n-1) is an hyperplane of dimension m-1. In that case, we can prove that extreme points have all m coordinates equal to 0.

element of proof :

The intersection of p facets with H is of dimension m-p So, extrema points (hyperplanes of dimension 0) are intersection of m facets with H.

Furthermore, it is clear We can have only one extrema point when m coordinates are set to 0. So, the number of extrema points is less than or equal to $n \choose m$.

But in dimension 3, for instance, if H is of dimension 1 (a line), the number of extrema points is 2 or less (while ${3 \choose 1} =3$)

So the maximum is less than the found upper bound.

=================== Original problem ========

Extreme points of a probability distribution subject to marginal constraints

Suppose that I have a probability distribution over N binary variables $\chi=(X_i)_{1 \leq i \leq n}$.

That distribution can be seen as a point on the simplex [$\sum_{x \in val(\chi)}{P(x)}=1$ and $\forall x \in val(\chi), P(x) \ge 0$] where the P(x) are the coordinates of my distribution and $val(\chi)$ is the different outcomes for the variables of $\chi$.

Suppose, now, that I know a set of (coherent) marginal constraints over subsets of $\chi$ Thus, for each constraint $P(X_i=x_i,X_j=x_j, \dots ,X_k=x_k)=C$, I would have additional linear constraints $\sum_{x \in S}(P(x)=C)$ where S is the subset of $val(\chi)$ compatible with $X_i=x_i,X_j=x_j, \dots ,X_k=x_k$

The space that is valid for all my constraints is a convex polytope. Its dimension is $card(val(\chi))-1-N=2^n-1-N$ where N is the number of additional linear constraints.

The question is how find the extreme points of that polytope, the number of those points (or an upper bound of that number) and (that would be great) an algorithm enabling to find neighbour extreme point from any extreme point.

So far, I have devised a simple but fastidious way to identify extreme point :

  • create counters for each marginal constraints

  • Repeat for each ordering of $x \in val(\chi)$

  • sort the $x \in val(\chi)$ in that order.

  • attribute to each x in turn the highest valid probability P(x)

  • decrement the counters accordingly

e.g

Suppose I have 2 variables $X_1$ and $X_2$ and 2 marginal constraints :

$P(X_1=0)=0.3$

$P(X_2=0)=0.6$

I create 2 pairs of counters :

P($X_1$) = [0.3, 0.7]

P($X_2$) = [0.6, 0.4]

Then, I start with the natural ordering for $x=(x_1,x_2)$ : (0,0), (0,1),(1,0),(1,1)

I set P(0,0)=0.3 and decrements my counters :

P($X_1$) = [0, 0.7]

P($X_2$) = [0.3, 0.4]

The I have no choice for P(0,1)=0

Then I set P(1,0)=0.4 and decrements my counters :

P($X_1$) = [0, 0.3]

P($X_2$) = [0.3, 0]

Then it comes P(1,1)=0.3

and I continue with different orderings.

well, I have no proved that this method provides only and all extreme points. Furthermore, it requires to do the job for each ordering so the complexity is not polynomial.

$\endgroup$
  • $\begingroup$ By hyperplane do you mean a linear subspace (i.e. passing through the origin) or an affine subspace (i.e. not necessarily passing through the origin)? $\endgroup$ – Vincent Apr 15 '16 at 9:40
  • $\begingroup$ affine subspace with a set of equations $\sum{a_i^j.x_i}=c^j$ $\endgroup$ – Arnaud Mégret Apr 15 '16 at 10:12
  • 1
    $\begingroup$ Well, it seems that the Simplex algorithm should be the right way of dealing with the problem ! At least, it provides a way to iterate through the vertices. I will provide further information if someone is interested. $\endgroup$ – Arnaud Mégret Apr 19 '16 at 17:46
  • $\begingroup$ I would be interested - this combines linear programming and probability, correct? The extreme points are supposed to be the ergodic distributions? $\endgroup$ – Chill2Macht Apr 19 '16 at 18:51
  • $\begingroup$ For the intersection of $k$ halfspaces not planes (which comes up in various guises), see how-many-vertices-can-a-convex-polytope-have $\endgroup$ – denis Sep 6 at 14:50
0
$\begingroup$

The maximum possible number of vertices would be m+1 (for example we can always define an n-1 dimensional hyperplane using n-points on the boundary of the octant). In degenerate cases we could also have fewer vertices.

The intersection of the m-dimensional hyperplane with the octant would generically be an m-dimensional manifold with boundary, in particular an m-simplex, which has m+1 vertices. https://en.wikipedia.org/wiki/Simplex

Again, in degenerate cases (e.g. if one of the directions of the hyperplane is parallel to one of the sides of the orthant), we could expect fewer vertices, but these instances are "negligible" compared to the generic case.

It isn't surprising that the simplex algorithm is applicable here given the geometrical interpretation of the problem as enumerating the vertices of a simplex.

$\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.