A generalization of the Hammersley-Clifford theorem

Let \((P, \preceq)\) be a locally-finite poset, and let \((\mathcal{A}, +)\) be an Abelian group. Define \(F_G(P)\) to be the set of functions, \[F_G(P) = \{f: P \times P \rightarrow \mathcal{A} | x \npreceq y \Rightarrow f(x, y) = 0_{\mathcal{A}}\}.\] The set \(F_G(P)\) also inherits the group structure of \(\mathcal{A}\) by pointwise extension of '\(+\)'.

• Incidence Algebras If \((\mathcal{A}, +, \cdot)\) is a commutative semi-ring, the \('*'\) operator given by the Dirichlet convolution, forms the basis for the algebra on \(F_G(P)\).
  • Dirichlet convolution \[(f * g)(x, z) = \sum_{x \preceq y \preceq z} f(x, y) \cdot g(y, z).\] Properties
    • Bilinear \[(f * g)(x, z) = \sum_{x \preceq y \preceq z} f(x, y) \cdot g(y, z).\]
    • Associative \[((f * g) * h)(x, z) = \sum_{x \preceq y \preceq y' \preceq z} f(x, y) \cdot g(y, y') \cdot h(y', z) = (f * (g * h))(x, z) = (f * g * h)(x, z).\]

    • \(\zeta\) function, Möbius inversion lemma Let \(\mathcal{A}\) be a commutative ring with identity, and let, \[\zeta(x, y) = \begin{cases}1_{\mathcal{A}} & x \preceq y \\ 0_{\mathcal{A}} & \mbox{otherwise}\end{cases},\quad \delta(x, y) = \begin{cases} 1_{\mathcal{A}} & x = y \\ 0_{\mathcal{A}} & \mbox{otherwise}\end{cases}.\] So that, \[(f * \zeta)(x, z) = \sum_{x \preceq y \preceq z} f(x, y).\] Define the Möbius function, on \((P, \mathcal{A})\), to be the inverse of the \(\zeta\)-function. \[(\zeta * \mu)(x, z) = (\mu * \zeta)(x, z) = \delta(x, z).\] Hence -via \(\preceq\)-DAG inversion- \[\mu(x, z) = \begin{cases} 1_{\mathcal{A}} & x = z \\ - \sum_{x \preceq y \prec z} \mu(x, y) = - \sum_{x \prec y \preceq z} \mu(y, z) & \mbox{otherwise}\end{cases}.\] It is easy to see that, \(\mu(x, y) \in \langle 1_{\mathcal{A}} \rangle\).

      Hence, \[g = f * \zeta \Leftrightarrow f = g * \mu,\] \[g = \zeta * f \Leftrightarrow f = \mu * g.\]

Let \(\mathcal{A}\) be an Abelian group, and let,

\begin{equation} \label{eqn:gmob} f(x, z) = \sum_{x \preceq y \preceq z} g(x, y) \Leftrightarrow g(x, z) = \sum_{x \preceq y \preceq z} f(x, y) \mu(y, z) \end{equation}

where \(\mu(\cdot, \cdot)\) is the Möbius function on \((P, \mathbb{Z})\), the scalar multiplication given by the canonical power operation; proof follows as before that,

\begin{equation} \mu(x, y) = \begin{cases} 1, & y \preceq x,\\ - \sum_{x\preceq y \prec z} \mu(x, y), & \mbox{otherwise}. \end{cases} \end{equation}

• Application: Inclusion-Exclusion principle \[|\cup_{i \in I} A_i| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| \dots - (-1)^{n} |\cap_i A_i|, \quad |I| < \infty.\] Proof Consider the partial order given by \((2^I, \subseteq)\), the Möbius function is given by, \(\mu(A, B) = (-1)^{B \backslash A}\) {Proof: Induction + Binomial theorem}.

  Let \(f(S) = m(\cap_{i \in S} A_i \backslash \cup_{i \in I \backslash S} A_i)\), where \(m(\cdot)\) is an additive set function, and, \[g(S) = \sum_{K \supseteq S} f(K),\quad f(S) = \sum_{K \supseteq S} g(K) (-1)^{|K \backslash S|}.\] Each of the sets \(\cap_{i \in S} A_i \backslash \cup_{i \in I \backslash S} A_i\) is disjoint. Hence, \[g(S) = m(\cap_{i \in S} A_i), \quad S \neq \emptyset,\] \[g(\emptyset) = m(\cup_{i \in I} A_i).\]

  \[0 = f(\emptyset) = g(\emptyset) + \sum_{S \subsetneq I} (-1)^{|S|} m(\cap_{i \in S} A_i),\] \[\therefore m(\cup_{i \in I} A_i) = \sum_{S \subsetneq I} (-1)^{|S| - 1} m(\cap_{i \in S} A_i).\]

Let \((\mathcal{A}, \cdot)\) be an Abelian group, and let \(G\) be an undirected graph. Let \(\psi_{S} : \prod_{u \in S \subset V(G)} X_u \rightarrow \mathcal{A}\) be a family of maps such that, \[A \perp B | S, V \backslash (A \cup B \cup S) \Rightarrow \psi_{A \cup B \cup S} \cdot \psi_{S} = \psi_{A \cup S} \cdot \psi_{B \cup S}.\]

The map \(\psi_V\) has a max-clique factorization, \[\psi_V = \prod_{C \in \mathcal{C}} \phi(x_C).\]

Proof Consider the partial order given by \((2^V, \subseteq)\), so that, \[\phi_S = \prod_{T \subseteq S} \psi_T^{\mu(T, S)}, \quad \psi_S = \prod_{T\subseteq S} \phi_T,\] and, \(\mu(T, S) = (-1)^{|S \backslash T|}\). Suppose, \(S \subseteq V\) is not a clique, so that \(\exists a, b \in S, ab \not \in E\), \[\phi_{S} = \prod_{T \subseteq S} \psi_T^{\mu(T, S)} = \prod_{T \subseteq S \backslash \{a, b\}} \psi_T^{\mu(T, S)} \cdot \psi_{T\cup a}^{-\mu(T, S)} \cdot \psi_{T\cup b}^{-\mu(T, S)} \cdot \psi_{T\cup \{a, b\}}^{-\mu(T, S)} = \prod_{T \subseteq S \backslash \{a, b\}} (\psi_T \cdot \psi_{T \cup \{a, b\}} \cdot \psi_{T\cup b}^{-1} \cdot \psi_{T \cup a}^{-1})^{\mu(T, S)} = 1_{\mathcal{A}}.\] The last inequality follows from the independence condition.

If we define, \(\psi_S = \mathbb{P}(x_S, \tilde{x}_{V \backslash S})\) - for some fixed \(\tilde{x}\) - then this gives the desired result for MRFs.

Moreover -since \(\mathbb{R} \backslash \{0\}\) is an abelian group under multiplication- it generalizes to non-zero distributions with the given independence conditions (that's not to say they exist for every graph).