2
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Ah, that would explain things! This might be beyond the scope of a comment question, but is there a simple way of characterizing the difference in expressive power between distributions that do factor pairwise, and those that don't? I'm wondering if we can always get 'close', for some definition of close, to an arbitrary positive distribution using a distribution which factors pairwise, or triplet-wise, etc $\endgroup$
    – wrvb
    Apr 9, 2015 at 21:02
  • $\begingroup$ Bjørn's example shows you can't get arbitrarily close with pairwise factors, and easily generalizes to $k$-wise factors. $\endgroup$ Apr 9, 2015 at 21:53
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The constructive example is really helpful. I'm keeping Robert's answer accepted, because he pointed out the flaw in my reasoning; if I had the reputation to upvote your answer, though, I would. $\endgroup$
    – wrvb
    Apr 9, 2015 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.