The Hammersley-Clifford theorem says that any positive probability distribution satisfies one of the Markov properties with respect to an undirected graph G if and only if its density can be factorized over the cliques of the graph. Any edge in a graph is a clique. Every distribution trivially satisfies the local Markov property with respect to the complete graph. It seems to follow that any positive distribution must factor pairwise: $$f(x\_1,\dots,x\_N)=\prod\_{N\ge i>j\ge 1}f\_{ij}(x\_i,x\_j)$$ if $f$ is a positive distribution. This should hold regardless of whether the various $x\_i$ are discrete or continuous or from some more exotic measurable space.


That seems surprising to me. A tabular representation of the distribution over $N$ binary variables has $2^N-1$ free parameters, one per configuration less one to make the distribution normalize. But if the distribution must factor into $\frac{N(N+1)}{2}$ pairwise terms, each of which can be represented in tabular form with four parameters, we can represent any distribution with no more than $2N(N+1)\ll 2^N-1$ parameters. Have I missed something subtle (or something obvious)? If the claim that all distributions on $N$ variables must factor pairwise is true, is there a more direct or intuitive proof than invoking Hammersley-Clifford as I did?



Do all positive distributions on $N$ variables factor pairwise?
You're misinterpreting the Hammersley-Clifford theorem. Every edge is a clique, but not every clique is an edge. You need to factor over **all** the cliques, including the complete graph itself.


