Do all positive distributions on $N$ variables factor pairwise?

Question

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?

Answer 1

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.

Answer 2

Well, the uniform distribution on $\{(0,1,1), (1,0,1), (1,1,0)\} $ does not factor like that, since it would imply $$0=f(1,1,1)=\prod_{i, j} f_{i, j}(1,1)\ne 0,$$ a contradiction.

To get a positive example, let the probability of $(0,1,1)$, $(1,1,0)$, and $(1,0,1)$ each be $\frac{1-\epsilon}{3}$, and the probability of each of the other 5 elements of $\{0,1\}^3$ be $\epsilon/5$. Then $$\frac\epsilon{5}=f(1,1,1)=\prod_{i, j} f_{i, j}(1,1)\ge \left(\frac{1-\epsilon}3\right)^3,$$ which is a contradiction for small enough $\epsilon$.