# Extreme points of intersection of the orthant (quadrant) with an Hyperplane in finite dimension vectorial space

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.

• 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)? – Vincent Apr 15 '16 at 9:40
• affine subspace with a set of equations $\sum{a_i^j.x_i}=c^j$ – Arnaud Mégret Apr 15 '16 at 10:12
• 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. – Arnaud Mégret Apr 19 '16 at 17:46
• I would be interested - this combines linear programming and probability, correct? The extreme points are supposed to be the ergodic distributions? – Chill2Macht Apr 19 '16 at 18:51