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