_imply_ the Markov random field property, which is crucial in the next section
when restricting to properties that are motivated by physics.

######  Theorem 5.14.

Let $r\geq 0$ and $G$ be the abelian group defined in Equation (23). Assume
$M$, the monoid of equivalence classes of discrete random variables on
$\Omega$, acts additively on $G$ by Equation (34), and that $F:M\to G$ is a
function of the form Equation (35) satisfying the chain rule Equation (15).

Now, let $X_{1},\dots,X_{n}$ be discrete random variables on $\Omega$,
$\mathcal{G}$ a graph with vertex set $[n]$, and
$\mathcal{R}=\mathcal{R}\big{(}\mathcal{G};X_{1},\dots,X_{n}\big{)}$ a stable
property that implies the property $\mathcal{MRF}$ from Equation (36):

$\forall\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in\widetilde{\Delta(\Omega)^{r+1}}:\
\
\mathcal{R}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\quad\Longrightarrow\quad\mathcal{MRF}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}.$

Then $X_{1},\dots,X_{n}$ form an ${F}_{\mathcal{R}}$-Markov random field with
respect to $\mathcal{G}$, where ${F}_{\mathcal{R}}$ is defined as in Equation
(33) as a restriction of $F$.

###### Proof.

Let $\mathcal{A},\mathcal{B},\mathcal{C}\subseteq\mathcal{V}=[n]$ be disjoint
vertex sets such that $\mathcal{C}$ separates $\mathcal{A}$ from
$\mathcal{B}$. We need to show the ${F}_{\mathcal{R}}$-independence
$X_{\mathcal{A}}\underset{{F}_{\mathcal{R}}}{\perp\\!\\!\\!\perp}X_{\mathcal{B}}\
|\ X_{\mathcal{C}}$, which, by Proposition 4.3, is equivalent to the equality

$\big{(}X_{\mathcal{C}}X_{\mathcal{B}}\big{)}{.}_{\mathcal{R}}{F}_{\mathcal{R}}(X_{\mathcal{A}})=X_{\mathcal{C}}{.}_{\mathcal{R}}{F}_{\mathcal{R}}(X_{\mathcal{A}}).$
(37)

For all
$\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in{\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}}$,
we obtain:

$\displaystyle\Big{[}$
$\displaystyle\big{(}X_{\mathcal{C}}X_{\mathcal{B}}\big{)}{.}_{\mathcal{R}}{F}_{\mathcal{R}}(X_{\mathcal{A}})\Big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle=\sum_{x_{\mathcal{C}},x_{\mathcal{B}}}P(x_{\mathcal{C}},x_{\mathcal{B}})\cdot\Big{[}{F}_{\mathcal{R}}(X_{\mathcal{A}})\Big{]}\Big{(}P|_{X_{\mathcal{C}}X_{\mathcal{B}}=(x_{\mathcal{C}},x_{\mathcal{B}})}\
\|\
Q_{1}|_{X_{\mathcal{C}}X_{\mathcal{B}}=(x_{\mathcal{C}},x_{\mathcal{B}})},\dots,Q_{r}|_{X_{\mathcal{C}}X_{\mathcal{B}}=(x_{\mathcal{C}},x_{\mathcal{B}})}\Big{)}$
$\displaystyle=\sum_{x_{\mathcal{C}},x_{\mathcal{B}}}P(x_{\mathcal{C}},x_{\mathcal{B}})\sum_{x_{\mathcal{A}}}P\big{(}x_{\mathcal{A}}\mid
x_{\mathcal{C}},x_{\mathcal{B}}\big{)}\cdot h\Big{(}P(x_{\mathcal{A}}\mid
x_{\mathcal{C}},x_{\mathcal{B}}),\ Q_{1}(x_{\mathcal{A}}\mid
x_{\mathcal{C}},x_{\mathcal{B}}),\dots,Q_{r}(x_{\mathcal{A}}\mid
x_{\mathcal{C}},x_{\mathcal{B}})\Big{)}$
$\displaystyle\overset{(\star)}{=}\sum_{x_{\mathcal{C}},x_{\mathcal{B}}}P(x_{\mathcal{C}},x_{\mathcal{B}})\sum_{x_{\mathcal{A}}}P\big{(}x_{\mathcal{A}}\mid
x_{\mathcal{C}},x_{\mathcal{B}}\big{)}\cdot h\Big{(}P(x_{\mathcal{A}}\mid
x_{\mathcal{C}}),\ Q_{1}(x_{\mathcal{A}}\mid
x_{\mathcal{C}}),\dots,Q_{r}(x_{\mathcal{A}}\mid x_{\mathcal{C}})\Big{)}$
$\displaystyle=\sum_{x_{\mathcal{C}},x_{\mathcal{A}}}\bigg{(}\sum_{x_{\mathcal{B}}}P\big{(}x_{\mathcal{A}},x_{\mathcal{C}},x_{\mathcal{B}}\big{)}\bigg{)}\cdot
h\Big{(}P(x_{\mathcal{A}}\mid x_{\mathcal{C}}),\ Q_{1}(x_{\mathcal{A}}\mid
x_{\mathcal{C}}),\dots,Q_{r}(x_{\mathcal{A}}\mid x_{\mathcal{C}})\Big{)}$
$\displaystyle=\sum_{x_{\mathcal{C}}}P(x_{\mathcal{C}})\sum_{x_{\mathcal{A}}}P(x_{\mathcal{A}}\mid
x_{\mathcal{C}})\cdot h\Big{(}P(x_{\mathcal{A}}\mid x_{\mathcal{C}}),\
Q_{1}(x_{\mathcal{A}}\mid x_{\mathcal{C}}),\dots,Q_{r}(x_{\mathcal{A}}\mid
x_{\mathcal{C}})\Big{)}$
$\displaystyle=\sum_{x_{\mathcal{C}}}P(x_{\mathcal{C}})\cdot\Big{[}{F}_{\mathcal{R}}(X_{A})\Big{]}\Big{(}P|_{X_{\mathcal{C}}=x_{\mathcal{C}}}\
\|\
Q_{1}|_{X_{\mathcal{C}}=x_{\mathcal{C}}},\dots,Q_{r}|_{X_{\mathcal{C}}=x_{\mathcal{C}}}\Big{)}$
$\displaystyle=\Big{[}X_{\mathcal{C}}{.}_{\mathcal{R}}{F}_{\mathcal{R}}(X_{A})\Big{]}\big{(}P\|Q_{r},\dots,Q_{r}\big{)}.$

In the calculation, in step $(\star)$ we used the assumption that

$X_{\mathcal{A}}\underset{P}{\perp\\!\\!\\!\perp}X_{\mathcal{B}}\ |\
X_{\mathcal{C}},\quad
X_{\mathcal{A}}\underset{Q_{1}}{\perp\\!\\!\\!\perp}X_{\mathcal{B}}\ |\
X_{\mathcal{C}},\quad\dots\quad
X_{\mathcal{A}}\underset{Q_{r}}{\perp\\!\\!\\!\perp}X_{\mathcal{B}}\ |\
X_{\mathcal{C}},$

which is due to
$\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in{\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}}\subseteq{\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{MRF}}$.
The other steps follow from the definitions. Overall, this shows Equation
(37), and we are done. ∎

###  5.5 The Second Law of Thermodynamics

In this section, we study a weak version of the second law of thermodynamics
and show that it can be represented visually by the degeneracy of a certain
Kullback-Leibler diagram.

We fix random variables $X_{1},\dots,X_{n}$ on $\Omega$. We now work with the
rather special property $\mathcal{P}=\mathcal{P}(X_{1},\dots,X_{n})$ of
probability tuples $\big{(}P\|Q\big{)}\in\Delta(\Omega)^{2}$ defined as
follows: $\mathcal{P}\big{(}P\|Q\big{)}$ holds if and only if

  * •

$P$ is absolutely continuous with respect to $Q$;

  * •

$X_{1},\dots,X_{n}$ forms a $P$-Markov chain and $Q$-Markov chain; and

  * •

for all $i\geq 2$ and all $(x_{i-1},x_{i})$ with $P(x_{i-1})\neq 0$, we have
$P(x_{i}\mid x_{i-1})=Q(x_{i}\mid x_{i-1})$.

The only difference of $P$ and $Q$ then stems from the initial distributions
$P(X_{1})$, $Q(X_{1})$. Intuitively, the letter “P” in the property
$\mathcal{P}=\mathcal{P}(X_{1},\dots,X_{n})$ is supposed to remind of
“Physics”. Namely, let $(P,Q)\in\widetilde{\Delta(\Omega)^{2}}$ with
$\mathcal{P}\big{(}P\|Q\big{)}$, then:

  * •

$i=1,\dots,n$ indexes time points with equal separation;

  * •

The value spaces $E_{X_{i}}$ model the sets of possible micro states at time
point $i$ (in reality, all these spaces are equal to each other, but we need
not make this assumption);

  * •

$P(X_{1})$ and $Q(X_{1})$ are the initial distributions of $P$ and $Q$, which
can be considered as macro states of the universe at some fixed point in time;
later, in the context of the second law of thermodynamics, we will choose
$P(X_{1})$ to be arbitrary and $Q(X_{1})$ to be the uniform distribution;

  * •

$P(x_{i}\mid x_{i-1})=Q(x_{i}\mid x_{i-1})$ models the likelihood that
$x_{i-1}$ evolves to $x_{i}$ according to the “physical laws” described by $P$
and $Q$; In reality, the physical laws are fixed and time independent, which
means there is one transition matrix $T$ such that $P(x_{i}\mid
x_{i-1})=Q(x_{i}\mid x_{i-1})=T(x_{i}\mid x_{i-1})$ for all $i$ and all
$x_{i-1},x_{i}$, but we do not yet make this stronger assumption;

  * •

$P(X_{i})$ and $Q(X_{i})$ are the macro states of the universe at time points
$i$ when evolving $P(X_{1})$ and $Q(X_{1})$ according to the “physical laws”
specified by $P$ and $Q$. These laws are equal to each other by assumption.

In the following, we want to investigate a weak version of the second law of
thermodynamics, which states that under some conditions, entropy cannot
decrease over time. We show this by first investigating the Kullback-Leibler
diagram for the property $\mathcal{P}$ in Theorem 5.15, which will lead to the
desired result in Corollary 5.16.

Formally, let
$D:M\to\operatorname{Meas}\Big{(}\widetilde{\Delta(\Omega)^{2}},\mathds{R}\Big{)}$
be the Kullback-Leibler divergence, see Equation (27). The property
$\mathcal{P}$ is stable under conditioning by Proposition 5.10, and is also
easily seen to be measurable and well-defined. Therefore, by Proposition 5.13,
the restricted Kullback-Leibler divergence

${D}_{\mathcal{P}}:{M}_{\mathcal{P}}\to\operatorname{Meas}\Big{(}{\big{(}\widetilde{\Delta(\Omega)^{2}}\big{)}}_{\mathcal{P}},\mathds{R}\Big{)}\eqqcolon{G}_{\mathcal{P}}$

satisfies the chain rule, where ${M}_{\mathcal{P}}$ is the monoid generated by
$X_{1},\dots,X_{n}$. Accordingly, by Hu’s Theorem 3.2, we obtain a
corresponding ${G}_{\mathcal{P}}$-valued measure
$\widetilde{{D}_{\mathcal{P}}}:2^{\widetilde{X}}\to{G}_{\mathcal{P}}$. The
following theorem shows that this measure degenerates, as visualized in Figure
7:

######  Theorem 5.15 (Structure of the ${D}_{\mathcal{P}}$-diagram).

Let $D:M\to G$ be the Kullback-Leibler divergence from Equation (27). Let
$X_{1},\dots,X_{n}$ be discrete random variables on $\Omega$ and consider the
property $\mathcal{P}=\mathcal{P}(X_{1},\dots,X_{n})$ defined above, leading
to a restriction ${D}_{\mathcal{P}}:{M}_{\mathcal{P}}\to{G}_{\mathcal{P}}$ and
a ${G}_{\mathcal{P}}$-valued measure
$\widetilde{{D}_{\mathcal{P}}}:2^{\widetilde{X}}\to{G}_{\mathcal{P}}$. One has
the following:

  * •

For all atoms $p_{I}$ where $I$ does not only consist of consecutive numbers,
one has $\widetilde{{D}_{\mathcal{P}}}(p_{I})=0$;

  * •

Let $p_{\left[i:k\right]}$ with $1\leq i\leq k\leq n$ be an atom that consists
of only consecutive numbers. If $i\geq 2$, then
$\widetilde{{D}_{\mathcal{P}}}\big{(}p_{\left[i:k\right]}\big{)}=0$.

###### Proof.

By Proposition 2.11 and Theorem 5.14, $X_{1},\dots,X_{n}$ forms a
${D}_{\mathcal{P}}$-Markov random field with respect to the graph
$\mathcal{G}$ with edges $i\scalebox{1.6}[1.0]{$-$}(i+1)$ for $i=1,\dots,n-1$.
By Proposition 2.11 again, we know that this is equivalent to forming a
${D}_{\mathcal{P}}$–Markov chain. Then by Corollary 4.17, one has
$\widetilde{{D}_{\mathcal{P}}}(p_{I})=0$ if $I\subseteq[n]$ does _not_ only
consist of consecutive numbers. Thus, only the atoms $p_{I}$ of the form
$I=\left[i:k\right]$ are of relevance for the ${D}_{\mathcal{P}}$-diagram.

Let $i\geq 2$. Using Corollary 3.4, Corollary 4.18, and Equation (16), we have

$\displaystyle\widetilde{{D}_{\mathcal{P}}}\big{(}p_{\left[i:k\right]}\big{)}$
$\displaystyle=\big{(}X_{[i-1]}X_{\left[k+1:n\right]}\big{)}.{D}_{\mathcal{P}}\big{(}X_{i};\dots;X_{k}\big{)}$
$\displaystyle=\big{(}X_{[i-1]}X_{\left[k+1:n\right]}\big{)}.{D}_{\mathcal{P}}\big{(}X_{i};X_{k}\big{)}$
$\displaystyle=\big{(}X_{[i-1]}X_{\left[k+1:n\right]}\big{)}.{D}_{\mathcal{P}}\big{(}X_{i}\big{)}-\big{(}X_{[i-1]}X_{\left[k:n\right]}\big{)}.{D}_{\mathcal{P}}\big{(}X_{i}\big{)}$
$\displaystyle=\big{(}X_{[i-2]}X_{\left[k+1:n\right]}\big{)}.\Big{(}X_{i-1}.{D}_{\mathcal{P}}\big{(}X_{i}\big{)}\Big{)}-\big{(}X_{[i-2]}X_{\left[k:n\right]}\big{)}.\Big{(}X_{i-1}.{D}_{\mathcal{P}}\big{(}X_{i}\big{)}\Big{)}$

Since the monoid action sends zero elements to zero, it is enough to show the
identity $X_{i-1}.{D}_{\mathcal{P}}(X_{i})=0$. For arbitrary
$\big{(}P\|Q\big{)}\in{\big{(}\widetilde{\Delta(\Omega)^{2}}\big{)}}_{\mathcal{P}}$,
we have

$\displaystyle\big{[}X_{i-1}.{D}_{\mathcal{P}}(X_{i})\big{]}\big{(}P\|Q\big{)}$
$\displaystyle=\sum_{x_{i-1}}P(x_{i-1})\cdot\big{[}{D}_{\mathcal{P}}(X_{i})\big{]}\big{(}{P}|_{X_{i-1}=x_{i-1}}\
\|\ {Q}|_{X_{i-1}=x_{i-1}}\big{)}$
$\displaystyle=\sum_{x_{i-1}}P(x_{i-1})\sum_{x_{i}}P(x_{i}\mid
x_{i-1})\cdot\log\frac{P(x_{i}\mid x_{i-1})}{Q(x_{i}\mid x_{i-1})}$
$\displaystyle=\sum_{x_{i-1}}P(x_{i-1})\sum_{x_{i}}P(x_{i}\mid
x_{i-1})\cdot\log 1$ $\displaystyle=0,$

where in the third step we used the assumptions of equal transition
probabilities, which holds since $\mathcal{P}(P\|Q)$ is true. That was to
show. ∎

Figure 7: If one restricts the set of tuples $(P,Q)$ of probability
distributions to those that have equal transition probabilities and give
individually give rise to a Markov chain $X_{1},\dots,X_{n}$, then this leads
to a restricted Kullback-Leibler divergence ${D}_{\mathcal{P}}$ and the
corresponding measure $\widetilde{{D}_{\mathcal{P}}}$. Theorem 5.15 shows that
in the corresponding ${D}_{\mathcal{P}}$-diagram, only atoms of the form
$p_{12\dots k}$ remain. This is visualized here for the case $n=4$ by omitting
all atoms that are mapped to zero by $\widetilde{{D}_{\mathcal{P}}}$.
_Intuitively, the Kullback-Leibler divergence shrinks over time._ In
particular, this leads by Hu’s Theorem 3.2 to the chain rule
${D}_{\mathcal{P}}(X_{i-1})={D}_{\mathcal{P}}(X_{i})+X_{i}.{D}_{\mathcal{P}}(X_{i-1})$,
which we use in the proof of Corollary 5.16 to deduce a weak version of the
second law of thermodynamics.

We deduce the following weak version of the second law of thermodynamics:

######  Corollary 5.16 (Second Law of Thermodynamics).

Let all notation be as above. Assume that the joint $X_{1}\cdots
X_{n}:\Omega\to E_{X_{1}}\times\dots\times E_{X_{n}}$ is surjective. Let $P$
be a probability distribution on $\Omega$ such that $X_{1},\dots,X_{n}$ forms
a $P$-Markov chain. Assume that $E_{X_{i}}=E_{X_{j}}$ for all $i,j=1,\dots,n$
and that there is a time-independent doubly stochastic transition matrix $T$
such that $P(x_{i}\mid x_{i-1})=T(x_{i}\mid x_{i-1})$ for all $i=2,\dots,n$
and $(x_{i-1},x_{i})$ with $P(x_{i-1})\neq 0$. Let $I:M\to G$ be the Shannon
entropy, as defined in Equation (25). Then for all $i=2,\dots,n$, one has

$\big{[}I(X_{i-1})\big{]}(P)\leq\big{[}I(X_{i})\big{]}(P),$

i.e., entropy cannot decrease.

###### Proof.

The proof is a diagrammatic representation of the reasoning in Cover and
Thomas (2006), Chapter 4.4. Let $Q$ be any probability distribution on
$\Omega$ such that

  * •

$Q_{X_{1}}$ is the uniform distribution on $X_{1}$;

  * •

$Q(x_{i}\mid x_{i-1})=T(x_{i}\mid x_{i-1})$ for all $i=2,\dots,n$ and
$(x_{i-1},x_{i})$.141414To see that this exists, first construct a joint
distribution on $E_{X_{1}}\times\dots\times E_{X_{n}}$ with these properties
by multiplying the initial distribution with all the transitional
distributions. Then, “pull it back” to $\Omega$, for which there is at least
one possible construction since the joint $X_{1}\cdots X_{n}$ is surjective.

Then, as is well-known, the fact that $T$ is doubly stochastic implies that
$Q_{X_{i}}$ is uniform for all $i=1,\dots,n$. Let $D$ be the Kullback-Leibler
divergence. We obtain

$\displaystyle\big{[}D(X_{i-1})\big{]}(P\|Q)$
$\displaystyle=-\sum_{x_{i-1}}P(x_{i-1})\log\frac{Q(x_{i-1})}{P(x_{i-1})}$
$\displaystyle=-\sum_{x_{i-1}}P(x_{i-1})\log\frac{1}{\left|E_{X_{i-1}}\right|}-\big{[}I(X_{i-1})\big{]}(P)$
$\displaystyle=C-\big{[}I(X_{i-1})\big{]}(P),$

where $C$ is a constant, i.e., independent of $i,P$ and $Q$, and where the
uniformity of $Q_{X_{i-1}}$ was used in the second step. Thus, it is enough to
show that $\big{[}D(X_{i-1})\big{]}(P\|Q)$ satisfies the following inequality:

$\big{[}D(X_{i-1})\big{]}(P\|Q)\geq\big{[}D(X_{i})\big{]}(P\|Q).$

Now, note that $P\ll Q$ since $Q$ is nowhere zero. Also, by assumption, $P$
and $Q$ both have equal transition probabilities given by $T$. We obtain
$\big{(}P\|Q\big{)}\in{\Big{(}\widetilde{\Delta(\Omega)^{2}}\Big{)}}_{\mathcal{P}}$.
Thus, Theorem 5.15, as visualized by Figure 7, shows

$\big{[}D(X_{i-1})\big{]}(P\|Q)=\big{[}D(X_{i})\big{]}(P\|Q)+\big{[}X_{i}.D(X_{i-1})\big{]}(P\|Q)\geq\big{[}D(X_{i})\big{]}(P\|Q),$
(38)

where in the last step we used that conditional Kullback-Leibler divergence is
non-negative. That was to show. ∎

##  6 Discussion

###  6.1 Major Findings: Characterizations of $F$–FCMIs, $F$–Markov Random
Fields, and Probabilistic Applications

In this work, we have generalized the main results in Yeung et al. (2002),
which characterize probabilistic full conditional mutual independences and
Markov random fields in terms of $I$-diagrams (Hu, 1962; Yeung, 1991). In
doing so, we replaced the Shannon entropy $I$ with any function $F:M\to G$
from a commutative, idempotent monoid $M$ to an abelian group $G$ that
satisfies the chain rule:

$F(XY)=F(X)+X.F(Y).$

The dot denotes an additive monoid action of $M$ on $G$ that generalizes the
conditioning of information functions on discrete random variables.

Consequently, we also replaced the familiar probabilistic conditional
$P$-independence — which is characterized by a vanishing of conditional mutual
information — by $F$-independence:

$X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z\quad:\Longleftrightarrow\quad
Z.F(X;Y)=0.$

This independence relation gives rise to a separoid (Dawid, 2001), as we have
shown in Proposition 3.11, a powerful framework in which one can study
conditional independence relations. Separoids generally also allow us to study
conditional _mutual_ independences and full conditional mutual independences
(FCMIs). These can be used to characterize Markov random fields by the _cutset
property_ , as was first observed in Yeung et al. (2002) for the classical
case — see Section 2.4. When specializing to the separoid with the
independence relation given by $\perp\\!\\!\\!\perp_{F}$ we obtained the
notions of $F$-FCMIs and $F$-Markov random fields that generalize the
probabilistic counterparts.

By the generalized Hu Theorem 3.2 from Lang et al. (2022), for fixed elements
$X_{1},\dots,X_{n}\in M$, one obtains a $G$-valued measure $\widetilde{F}$
that describes relations of information terms
$X_{J}.F\big{(}X_{L_{1}};\dots;X_{L_{q}}\big{)}$ of arbitrary degree $q$,
where $J,L_{1},\dots,L_{q}\subseteq[n]$ are any subsets. These can then be
visualized in $F$-diagrams, as we show for $n=3$ in Figure 2. The core
question asked in this work — generalizing the investigations in Yeung et al.
(2002) — was how $F$-FCMIs and $F$-Markov random fields can be characterized
in terms of the $F$-diagram. In Theorem 4.11, we found that $F$-FCMIs are
characterized by a vanishing of the $F$-diagram on the atoms in the _image_ of
the corresponding conditional partition, see also Figures 4 and 5.

This results in a characterization of $F$-Markov random fields for a graph
$\mathcal{G}$, Theorem 4.16, that is easy to interpret: an atom
$p_{\mathcal{W}}$ disappears in the $F$-diagram if and only if it is
_disconnected_ , meaning that the vertex set $\mathcal{W}$ is disconnected
when removing the vertices outside of $\mathcal{W}$ from $\mathcal{G}$. We
visualized this result in Figure 1 for Shannon entropy, though the basic
picture applies for arbitrary $F$. A visualization for the special case of a
path-shaped graph — recovering $F$-Markov chains — can be found in Figure 6.

When looking closely at the results, which are always given as an equivalence
of two or more statements, it becomes clear that one direction is always easy
to prove — namely, if one starts assuming that a suitable set of atoms
disappears in the $F$-diagram, then one can easily deduce an $F$-FCMI from it
(possibly in the context of an $F$-Markov random field). After all,
$\widetilde{F}$ is a measure, and so the vanishing of a set of atoms
automatically leads to the vanishing of all sets _composed_ of these atoms,
and this includes by Hu’s Theorem 3.2 precisely the sets encoding the
$F$-FCMIs. However, going in the other direction is harder: why should an
$F$-FCMI induce the vanishing of specific atoms? This problem is addressed by
our main technique “subset determination”, Theorem 3.5. It implies that
whenever $\widetilde{F}(A)=0$ for some set of atoms $A$, then we also have
$\widetilde{F}(B)=0$ for all subsets $B\subseteq A$, and in particular,
$\widetilde{F}(p_{I})=0$ for all atoms $p_{I}\in A$. This is essentially based
on inclusion-exclusion type arguments for $F$-diagrams, and uses the monoid
action from $M$ on $G$. We illustrate how to use subset determination to our
advantage in Figure 3. Essentially, subset determination replaces the use of
inequalities in the original work (Yeung, 2002).

We then applied our results to the case where the information functions apply
to probability distributions. In Lemma 5.12 and Proposition 5.13 we showed
that it is possible to restrict a general notion of information functions to
conditionally stable properties while preserving the monoid action and the
chain rule, which is similar to the use of adapted probability functors in
information cohomology (Vigneaux, 2019). Then, in Theorem 5.14, we restricted
a narrower set of information functions $F$ — including Shannon entropy,
Kullback-Leibler divergence, and cross-entropy — to stable properties
$\mathcal{R}$ that _imply_ the Markov random field property. The restriction
${F}_{\mathcal{R}}$ then gives rise to an ${F}_{\mathcal{R}}$–Markov random
field; consequently, disconnected atoms disappear from the
$F_{\mathcal{R}}$-diagram.

In Theorem 5.15, we applied this to the case of tuples of probability
distributions that give rise to a Markov chain and have the same conditional
distributions — reminiscent of physics, where the conditional distributions
are governed by the physical laws. It turns out that the corresponding
$D$-diagram degenerates even further than the Markov chain property alone
would predict; the Kullback-Leibler divergence of all regions outside the
initial random variable disappears. The reason is that in those regions, one
“conditions” on the initial variable according to Hu’s Theorem 3.2, and since
the conditional distributions are the same, one obtains zero Kullback-Leibler
divergence.

The result is an ever-shrinking151515More precisely: non-increasing. sequence
of Kullback-Leibler divergences across the Markov chain, as we visualize in
Figure 7. This has the following consequence: if one of the two distributions
is uniform, then the other one cannot move further away from it as measured by
the Kullback-Leibler divergence, which means that its entropy cannot decrease
over time. This is a weak version of the second law of thermodynamics, see
Corollary 5.16.

It is important to note that in most of these probabilistic results, we take a
view in which information functions are still _functions_ of yet unspecified
probability distributions. We simply restrict the sets of distributions to
those that satisfy stable properties, and can thereby preserve our general
theory, the monoid action, and the “subset determination” property, Theorem
3.5, that does not generally hold for fixed probability distributions. This
raises the question of whether the $P$-independence results in Yeung et al.
(2002) are actually covered by our work. We answer this affirmatively in
Appendix D. In the corresponding proofs, we use the fact that a
$P$-independence $X\underset{P}{\perp\\!\\!\\!\perp}Y\ |\ Z$ is equivalent to
the vanishing of the conditional mutual $P$-information
$\big{[}Z.I(X;Y)\big{]}(P)$, which is usually proved using Jensen’s
inequality. This reduction is then the only place where inequalities enter the
theory, whereas they take a more central role in the proofs in Yeung et al.
(2002).

#### Further Findings: $F$-(Dual )Total Correlation, Cohomological
Characterizations of Functions $F$, and Further Consequences

Our proof of the $F$-diagram characterization of $F$-FCMIs uses Theorem 4.5,
in which we characterize conditional mutual $F$-independences by the vanishing
of $F$-dual total correlation. This relates to $F$ in the same way that the
classical dual total correlation from Han (1978) relates to Shannon entropy:

$DTC_{F}(X_{1};\dots;X_{n})\coloneqq
F\big{(}X_{[n]}\big{)}-\sum_{i=1}^{n}X_{[n]\setminus i}.F(X_{i}).$

Conditional $F$-dual total correlation
$Y.DTC_{F}\big{(}X_{1},\dots,X_{n}\big{)}$ corresponds by Hu’s Theorem 3.2 to
a set of atoms, which coincide with those that vanish based on a conditional
mutual $F$-independence
$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n}X_{i}\
|\ Y$. Again, we were able to use subset determination, Theorem 3.5, to prove
the characterization.

In Appendix B, we also investigated $F$-total correlation, which generalizes
the classical total correlation from Watanabe (1960). We showed that it can
also usually be used for a characterization of mutual $F$-independences.
However, since it double-counts some atoms, the characterization only works
for torsion-free groups $G$, and we provide a counter example in the case of
torsion, see Example B.5. This is not a strong restriction — all groups that
are used in practice seem to be derived from the real numbers $\mathds{R}$,
and therefore inherit the property to be torsion-free.

Subset determination implies that $F\big{(}X_{[n]}\big{)}$ determines the
whole $F$-diagram for variables $X_{1},\dots,X_{n}$. In Appendix A, this led
to a classification of functions $F:M\to G$ satisfying the chain rule, in the
case that $M$ has a “top element” — similar to how $X_{[n]}$ is “on top” of
all elements $X_{I}$ for $I\subseteq[n]$. We could show that such functions
$F$ correspond precisely to elements in $G$ that are annihilated by the top
element, which we also used in our constructions for Example B.5. In Remark
A.6, we explained a cohomological interpretation of these findings: the first
Hochschild cohomology group of $M$ with coefficients in $G$ disappears. This
is in contrast to information cohomology (Baudot and Bennequin, 2015;
Vigneaux, 2019), where the joint locality property ensures that the first
cohomology group is nontrivial; in fact, it is generated by Shannon entropy!

Finally, in Appendix C, we explain that all results from Yeung et al. (2019)
except those that depend on an order relation also generalize to our setting.
Overall, this means that we have generalized most of the results in Yeung
(1991); Kawabata and Yeung (1992); Yeung et al. (2002, 2019) from Shannon
entropy to general functions $F$ satisfying the chain rule.

###  6.2 Conceivable Extensions of the Theory and Open Questions

####  $K$-Independence and Kolmogorov Complexity

We have set up the theory in such a way that it could in principle be extended
beyond $F$-independence, since Section 2 introduces conditional (mutual)
independences, Markov random fields, and Markov chains in the general context
of separoids. In this context, we also characterized Markov random fields —
defined in terms of the global Markov property — by the _cutset property_
(Proposition 2.9), and showed that Markov chains can be equivalently described
as Markov random fields corresponding to a path-shaped graph (Proposition
2.11).

We can think of one concrete way to potentially go beyond $F$-independence.
Namely, Lang et al. (2022) also studied the case of functions $K:M\times M\to
G$ satisfying the chain rule absent of any monoid action of $M$ on $G$:
$K(XY)=K(X)+K(Y\mid X)$, where $K(Z)\coloneqq K(Z\mid\bm{1})$. One could then
define the $K$-independence by $X\underset{K}{\perp\\!\\!\\!\perp}Y\ |\ Z$ if
$K(X;Y\mid Z)=0$.

One can then ask questions similar to the ones answered in this work: In what
generality is $(M,\perp\\!\\!\\!\perp_{K})$ a separoid? And when it is, does
it allow to characterize conditional mutual $K$-independences and $K$-Markov
random fields in terms of $K$-diagrams? Note that $K$-diagrams do indeed
exist, as proven in Corollary 4.4 in Lang et al. (2022). However, we expect
$\perp\\!\\!\\!\perp_{K}$ to not always satisfy the separoid axioms since our
proof of the separoid axioms in Proposition 3.11 made use of subset
determination, Theorem 3.5, which in turn builds on the monoid action which is
not available in the setting using $K$.

In a specific case of interest, $K$ would be a version of Kolmogorov
complexity (Li and Vitányi, 1997), especially Chaitin’s prefix-free Kolmogorov
complexity (Chaitin, 1987), restricted to sets of strings that satisfy
approximate independence relations. The fact that conditional mutual
Kolmogorov complexity $K(x;y\mid z)$ is approximately non-negative implies
that the separoid rules can be proved in this case, see Steudel et al. (2010).

####  $F$-Bayesian Networks

Additionally, it would be interesting to attempt to go beyond Markov random
fields by studying Bayesian networks. A priori, they can be defined in general
separoids using the d-separation criterion for a directed acyclic graph
(Pearl, 1985). This can then be applied to the case of a separation
$\perp\\!\\!\\!\perp_{F}$ coming from a function $F$ satisfying the chain
rule.

When applying such a theory to the probabilistic case, however, one will
likely encounter problems: $F$-independences can only model conditionally
stable cases, see Proposition 3.12. However, the independences in Bayesian
networks are, due to colliders, not preserved under conditioning, see Remark
3.13. Therefore, this property is not stable, Definition 5.11. When
restricting information functions to such sets of probability distributions,
one thus loses the monoid action that makes use of conditioning. Since the
monoid action is crucially used in our main technique — subset determination,
Theorem 3.5 — we expect such a theory to take a different route from the one
for $F$–Markov random fields. Nevertheless, Steudel et al. (2010), Theorem 1,
provides an information characterization of causal Bayesian networks for
submodular information functions, which can be used as an inspiration.

####  $O$-Information and $S$-Information

In Rosas et al. (2019) and Medina-Mardones et al. (2021), the $O$-information
and $S$-information were defined as the difference and sum of the classical
total correlation and dual total correlation, respectively. We have showed in
this work that $F$-(dual )total correlation preserves its value in studying
conditional mutual $F$-independences, and we therefore expect that
$F$–$O$-information and $F$–$S$-information might provide useful insights into
general characterizations of high-order interdependencies.

#### (Cluster) Cross-Entropies and Kullback-Leibler Divergence

We think it is worthwhile to study the case where $F$ is cross-entropy or
Kullback-Leibler divergence in greater detail. After all, much of machine
learning and deep learning involves the minimization of a cross-entropy, or
equivalently Kullback-Leibler divergence (Bishop, 2007; Bishop and Bishop,
2023). This becomes especially interesting for graphical methods, including
diffusion models (Sohl-Dickstein et al., 2015) that form the basis for
widespread text-to-image generation methods like Dalle (Ramesh et al., 2021),
Imagen (Saharia et al., 2022), and stable diffusion (Rombach et al., 2021).
Diffusion models involve a decomposition of a joint Kullback-Leibler
divergence over a Markov chain as in Figure 6. It could be valuable to analyze
the loss functions of more such graphical methods using Kullback-Leibler and
cross-entropy-diagrams. Similarly, the (cluster) cross-entropies (see Section
5.3) used in adaptive cluster expansion (Cocco and Monasson, 2012) of Ising
models, which form a Markov random field, deserve a further study.

### Conclusion

In this work we showed that it is possible to use the framework of general
$F$-diagrams to study generalized notions of independences and Markov random
fields. In the process, we generalized well-known notions like the (dual)
total correlation and developed new methods such as subset determination. We
were able to apply the general theory to the probabilistic case, and in
particular to Kullback-Leibler diagrams on Markov chains. We think it is
worthwhile to look into research areas such as machine learning, where
graphical models and information functions such as cross-entropy are
widespread, and to apply our generalized information-theoretic insights to
such settings.

##  Appendix A Cohomological Characterization of Functions Satisfying the
Chain Rule

In this appendix we expand on Remark 3.9 and show how functions $F$ satisfying
the chain rule can be classified. We will also interpret that result in terms
of the vanishing of a cohomology group of degree 1. In this whole section, let
$M$ be a commutative, idempotent monoid acting additively on an abelian group
$G$.

######  Definition A.1 (Bounded Monoid, Top Element).

$M$ is called _bounded_ if it contains a _top element_ , i.e., an element
$\top\in M$ such that $X\cdot\top=\top$ for all $X\in M$.

With the relation $\precsim$ on $M$ defined by $X\precsim Y$ if and only if
$X\cdot Y=Y$, we see that a top element is equivalently described as the
greatest element in $M$.

Clearly, top elements are unique.

######  Notation A.2.

We denote by

$\operatorname{CR}(M,G)\coloneqq\Big{\\{}F:M\to G\ \big{|}\ \forall X,Y\in M:\
F(XY)=F(X)+X.F(Y)\Big{\\}}$

the set of functions satisfying the chain rule Equation (15).

Note that $\operatorname{CR}(M,G)$ is itself an abelian group with addition

$(F+F^{\prime})(X)\coloneqq F(X)+F^{\prime}(X).$

Additionally, it carries an induced and well-defined additive monoid action
$.:M\times\operatorname{CR}(M,G)\to\operatorname{CR}(M,G)$ given by

$(X.F)(Y)\coloneqq X.F(Y).$

######  Notation A.3.

Let $X\in M$ be any element. We denote by

$G^{X}\coloneqq\Big{\\{}g\in G\ \big{|}\ X.g=0\Big{\\}}$

the elements in $G$ that are annihilated by $X$. This is a subgroup of $G$.
Furthermore, the action of $M$ on $G$ restricts to a well-defined additive
monoid action $M\times G^{X}\to G^{X}$.

######  Definition A.4 (Module Homomorphism, Module Isomorphism).

Let $G,H$ both be groups carrying an additive monoid action from $M$, which by
abuse of notation we denote with the same symbol:

$\displaystyle.:M\times G\to G,\quad.:M\times H\to H.$

A function $\Phi:G\to H$ is called a _module homomorphism_ if

  * •

$\Phi$ is a group homomorphism: $\Phi(g+g^{\prime})=\Phi(g)+\Phi(g^{\prime})$
for all $g,g^{\prime}\in G$;

  * •

$\Phi$ commutes with the monoid actions: $\Phi(X.g)=X.\Phi(g)$ for all $X\in
M$, $g\in G$.

A _module isomorphism_ is a bijective module homomorphism.

The following proposition shows that the functions $F:M\to G$ that satisfy the
chain rule are, for bounded $M$ with top element $\top$, essentially the same
as the elements in $G$ that are annihilated by $\top$.

######  Proposition A.5.

Let $M$ be a bounded, commutative, idempotent monoid with top element $\top$,
$G$ an abelian group, and $.:M\times G\to G$ an additive monoid action. Define
the pair of functions

${\operatorname{CR}(M,G)}$${G^{\top}}$$\scriptstyle{\Phi}$$\scriptstyle{\Psi}$

as follows:

$\displaystyle\forall F\in\operatorname{CR}(M,G):\quad\Phi(F)\coloneqq
F(\top);$ $\displaystyle\forall g\in G^{\top}:\quad\Psi(g):M\to G,\ \
\big{[}\Psi(g)\big{]}(X)\coloneqq g-X.g.$

Then $\Phi$ and $\Psi$ are mutually inverse module isomorphisms.

###### Proof.

For $\Phi$, we need to check well-definedness, i.e., that $F(\top)\in
G^{\top}$ for all $F\in\operatorname{CR}(M,G)$. Indeed, we have

$F(\top)=F(\top\top)=F(\top)+\top.F(\top)$

by the chain rule, from which $\top.F(\top)=0$ follows. It is clear that
$\Phi$ is a module homomorphism.

For $\Psi$, we also need to check that it is well-defined, i.e., that
$\Psi(g)$ satisfies the chain rule for all $g\in G^{\top}$. Indeed, we have

$\displaystyle\big{[}\Psi(g)\big{]}(XY)$ $\displaystyle=g-(XY).g$
$\displaystyle=g-X.g+X.g-X.(Y.g)$
$\displaystyle=\big{[}\Psi(g)\big{]}(X)+X.\big{[}g-Y.g\big{]}$
$\displaystyle=\big{[}\Psi(g)\big{]}(X)+X.\big{[}\Psi(g)\big{]}(Y).$

That $\Psi$ is a module homomorphism is clear.

It remains to show that $\Psi$ and $\Phi$ are inverse to each other. By
definition of $G^{\top}$, we have for all $g\in G^{\top}$:

$\displaystyle\big{(}\Phi\circ\Psi\big{)}(g)$
$\displaystyle=\Phi\big{(}\Psi(g)\big{)}=\big{[}\Psi(g)\big{]}(\top)=g-\top.g=g.$

In the other direction, let $F\in\operatorname{CR}(M,G)$ arbitrary. For all
$X\in M$, we have $X\cdot\top=\top$ by definition of $\top$ and therefore

$F(\top)=F(X\cdot\top)=F(X)+X.F(\top)$

by the chain rule. It follows

$\Big{[}\big{(}\Psi\circ\Phi\big{)}(F)\Big{]}(X)=\big{[}\Psi\big{(}\Phi(F)\big{)}\big{]}(X)=\big{[}\Psi\big{(}F(\top)\big{)}\big{]}(X)=F(\top)-X.F(\top)=F(X).$

This means $\big{(}\Psi\circ\Phi\big{)}(F)=F$, and we are done. ∎

######  Remark A.6 (Cohomological Interpretation).

For the interested reader, we interpret the preceding result in cohomological
terms. Namely, consider the following cochain complex:

${G=\operatorname{Maps}(M^{0},G)}$${\operatorname{Maps}\big{(}M,G\big{)}}$${\operatorname{Maps}\big{(}M^{2},G\big{)}}$${\dots}$$\scriptstyle{\Psi}$$\scriptstyle{\delta}$

Here, define $\Psi$ as in Proposition A.5 by
$\big{[}\Psi(g)\big{]}(X)\coloneqq g-X.g$ and $\delta$ by

$\big{[}\delta(F)\big{]}(X;Y)\coloneqq X.F(Y)-F(XY)+F(X).$

These are Hochschild coboundary maps, as originally defined in Hochschild
(1945), and also used for information cohomology in Baudot and Bennequin
(2015); Vigneaux (2019). Now, the fact that $\Psi$ is well-defined in
Proposition A.5, i.e. that it only maps to functions satisfying the chain
rule,171717Which, as we remarked, holds for $\Psi$ defined on all of $G$. can
now be expressed equivalently by saying that $\delta\circ\Psi=0$, a crucial
property for cochain complexes. The reason for this is that
$\mathrm{Ker}(\delta)=\operatorname{CR}(M,G)$ is precisely the set of
functions satisfying the chain rule. This allows to define the first
cohomology group of the complex, given by
$\mathrm{Ker}(\delta)/\operatorname{Im}(\Psi)$.

Now, the fact that $\Psi$ is surjective in the preceding proposition — meaning
that it hits every function satisfying the chain rule — can now be expressed
with $\operatorname{Im}(\Psi)=\mathrm{Ker}(\delta)$, meaning the first
cohomology group vanishes: $\mathrm{Ker}(\delta)/\operatorname{Im}(\Psi)=0$.
This is shown by explicitly constructing the inverse $\Phi$.

Finally, the preceding proposition also shows that $\Psi$ is injective when
restricting to $G^{\top}$.

Now, consider the case that $M$ is the monoid of equivalence classes of random
variables on $\Omega$ and
$G=\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$. Then the
preceding discussion would suggest that Shannon entropy $I$ disappears in the
first cohomology group. At first sight, one might think this contradicts the
fundamental result of information cohomology, which shows that the first
cohomology group is non-trivial and generated by Shannon entropy (Baudot and
Bennequin, 2015). The difference is explained by noting that Baudot and
Bennequin (2015) also require their cochains to satisfy the _joint locality_
property, which means that their cochains of degree zero are necessarily
constant.

##  Appendix B Conditional Mutual $F$-Independences and $F$-Total Correlation

In this appendix, we provide a characterization of conditional mutual
$F$-independences using $F$–total correlation. Different from the
characterization using $F$–dual total correlation in Theorem 4.5, this
characterization will only work when imposing an additional assumption on $G$,
namely that it is torsion-free. The reason is that $F$–total correlation
double counts atoms in the $F$-diagram; from a vanishing of the $F$–total
correlation, one can then a priori only conclude that a _multiple_ of each of
the contained atoms disappears, and one needs $G$ to be torsion-free to be
able to reduce the coefficient to $1$.

As in the main text, we fix a commutative, idempotent monoid $M$ acting
additively on an abelian group $G$ and a function $F:M\to G$ satisfying the
chain rule Equation (15).

######  Proposition B.1.

Let $X_{1},\dots,X_{n}\in M$. Then for all $\emptyset\neq I\subseteq[n]$, we
have the following identities relating $F$–total correlation to higher
$F$-interactions:

  1. 1.

$TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}=\sum_{\emptyset\neq L\subseteq
I}\big{(}\left|L\right|-1\big{)}\cdot X_{I\setminus
L}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in L}X_{l}\big{)}$;

  2. 2.

$\big{(}\left|I\right|-1\big{)}\cdot
F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}=\sum_{\emptyset\neq L\subseteq
I}(-1)^{\left|I\right|-\left|L\right|}\cdot X_{I\setminus
L}.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in
L}X_{l}\big{)}$.

###### Proof.

To prove part 1, let the $X_{i}$, $i\in I$ be the fixed elements in Theorem
3.2. Then we obtain

$\displaystyle TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}$ $\displaystyle=\sum_{i\in I}F(X_{i})-F(X_{I})$
$\displaystyle=\sum_{i\in
I}\widetilde{F}\big{(}\widetilde{X}_{i}\big{)}-\widetilde{F}\big{(}\widetilde{X}_{I}\big{)}$
$\displaystyle=\sum_{i\in I}\sum_{L\subseteq I,i\in
L}\widetilde{F}(p_{L})-\sum_{\emptyset\neq L\subseteq I}\widetilde{F}(p_{L})$
$\displaystyle=\sum_{\emptyset\neq L\subseteq I}\sum_{i\in
L}\widetilde{F}(p_{L})-\sum_{\emptyset\neq L\subseteq I}\widetilde{F}(p_{L})$
$\displaystyle=\sum_{\emptyset\neq L\subseteq
I}\big{(}\left|L\right|-1\big{)}\cdot\widetilde{F}(p_{L}).$

Now, note that $\widetilde{F}(p_{L})=X_{I\setminus
L}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in L}X_{l}\big{)}$
by Corollary 3.4. The result follows.

To prove part 2, we evaluate the right-hand-side using part 1 on each summand:

$\displaystyle\sum_{\emptyset\neq L\subseteq
I}(-1)^{\left|I\right|-\left|L\right|}$ $\displaystyle\cdot X_{I\setminus
L}.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in
L}X_{l}\big{)}$ $\displaystyle=\sum_{\emptyset\neq L\subseteq
I}(-1)^{\left|I\right|-\left|L\right|}\cdot X_{I\setminus
L}.\Bigg{(}\sum_{\emptyset\neq K\subseteq
L}\big{(}\left|K\right|-1\big{)}\cdot X_{L\setminus
K}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{k\in
K}X_{k}\big{)}\Bigg{)}$ $\displaystyle=\sum_{\emptyset\neq L\subseteq
I}\sum_{\emptyset\neq K\subseteq
L}(-1)^{\left|I\right|-\left|L\right|}\cdot\big{(}\left|K\right|-1\big{)}\cdot
X_{I\setminus K}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{k\in
K}X_{k}\big{)}$ $\displaystyle=\sum_{\emptyset\neq K\subseteq
I}(-1)^{\left|I\right|}\cdot\big{(}\left|K\right|-1\big{)}\cdot\Bigg{(}\sum_{L:\
K\subseteq L\subseteq I}(-1)^{\left|L\right|}\Bigg{)}\cdot X_{I\setminus
K}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{k\in K}X_{k}\big{)}.$
$\displaystyle=\sum_{\emptyset\neq K\subseteq
I}(-1)^{\left|I\right|}\cdot\big{(}\left|K\right|-1\big{)}\cdot(-1)^{\left|K\right|}\cdot\mathds{1}_{I=K}\cdot
X_{I\setminus K}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{k\in
K}X_{k}\big{)}$
$\displaystyle=(-1)^{2\cdot\left|I\right|}\cdot\big{(}\left|I\right|-1\big{)}\cdot
X_{I\setminus I}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}$ $\displaystyle=\big{(}\left|I\right|-1\big{)}\cdot
F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in I}X_{i}\big{)}.$

In the fourth step, we used Lemma 3.8. ∎

######  Definition B.2 (Torsion-Free Abelian Group).

Let $G$ be an abelian group. Then $G$ is called _torsion-free_ if $0\in G$ is
the only element of finite order. In other words, for all $0\neq g\in G$ and
all $0<k\in\mathds{N}$, we have $k\cdot g\neq 0$. Equivalently, for all
$k\in\mathds{N}$ and $g\in G$, if $k\cdot g=0$ then $k=0$ or $g=0$.

######  Example B.3.

The groups $\mathds{Z}$, $\mathds{R}$,
$\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$ and all other
groups encountered in Section 5 are torsion-free. $\mathds{Z}/k\mathds{Z}$ for
$k\geq 1$ is a prototypical example of an abelian group with torsion: $k\cdot
1=0$.

######  Theorem B.4.

Let $M$ be a commutative, idempotent monoid acting additively on a _torsion-
free_ abelian group $G$. Let $F:M\to G$ be a function satisfying the chain
rule Equation (15). Let $X_{1},\dots,X_{n},Y\in M$. Then the following
properties are equivalent:

  1. 1.

$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n}X_{i}\
|\ Y$;

  2. 2.

$Y.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in[n]}X_{i}\big{)}=0$;

  3. 3.

$(YX_{[n]\setminus
I}).TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}=0$ for all $\emptyset\neq I\subseteq[n]$.

###### Proof.

Assume 1. To prove 2, we use that by Proposition 2.4, we have
$X_{i}\underset{F}{\perp\\!\\!\\!\perp}X_{[i-1]}\ |\ Y$ for all $i=1,\dots,n$.
By Proposition 4.3, this implies
${Y.F\big{(}X_{[i]}\big{)}=Y.F\big{(}X_{[i-1]}\big{)}+Y.F(X_{i})}$.
Inductively, we obtain ${Y.F\big{(}X_{[n]}\big{)}=\sum_{i=1}^{n}Y.F(X_{i})}$
and therefore
$Y.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in[n]}X_{i}\big{)}=0$.

Now assume 2. To prove 3, we note

$\displaystyle 0$ $\displaystyle=X_{[n]\setminus
I}.\Big{(}Y.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in[n]}X_{i}\big{)}\Big{)}$
$\displaystyle=Y.\Bigg{(}X_{[n]\setminus
I}.\bigg{(}\sum_{i=1}^{n}F(X_{i})-F\big{(}X_{[n]}\big{)}\bigg{)}\Bigg{)}$
$\displaystyle=Y.\Bigg{(}\sum_{i=1}^{n}X_{[n]\setminus
I}.F(X_{i})-X_{[n]\setminus I}.F\big{(}X_{[n]}\big{)}\Bigg{)}$
$\displaystyle\overset{(\star)}{=}Y.\Bigg{(}\sum_{i\in I}X_{[n]\setminus
I}.F(X_{i})-X_{[n]\setminus I}.F(X_{I})\Bigg{)}$
$\displaystyle=\big{(}YX_{[n]\setminus I}\big{)}.\Bigg{(}\sum_{i\in
I}F(X_{i})-F(X_{I})\Bigg{)}$ $\displaystyle=\big{(}YX_{[n]\setminus
I}\big{)}.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}.$

Step $(\star)$ can easily be seen using Hu’s Theorem 3.2. That was to show.

Finally, assume 3. For proving 1, we can alternatively prove the equivalent
property 3 of Theorem 4.5. We note that for all $\emptyset\neq I\subseteq[n]$,
Proposition B.1 implies:

$\displaystyle\big{(}\left|I\right|-1\big{)}\cdot\big{(}YX_{[n]\setminus
I}\big{)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}$ $\displaystyle=\big{(}YX_{[n]\setminus
I}\big{)}.\Big{(}\big{(}\left|I\right|-1\big{)}\cdot
F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}\Big{)}$ $\displaystyle=\big{(}YX_{[n]\setminus
I}\big{)}.\Bigg{(}\sum_{\emptyset\neq L\subseteq
I}(-1)^{\left|I\right|-\left|L\right|}\cdot X_{I\setminus
L}.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in
L}X_{l}\big{)}\Bigg{)}$ $\displaystyle=\sum_{\emptyset\neq L\subseteq
I}(-1)^{\left|I\right|-\left|L\right|}\cdot\big{(}YX_{[n]\setminus
L}\big{)}.TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in
L}X_{l}\big{)}$ $\displaystyle=0.$

If $\left|I\right|=1$ then the factor $\left|I\right|-1$ vanishes and what we
showed is vacuous. If $\left|I\right|\geq 2$, then what we showed implies

$\big{(}YX_{[n]\setminus
I}\big{)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}=0$

since $G$ is torsion-free, and we are done. ∎

We now show in an example that we cannot omit the assumption that $G$ is
torsion-free in the preceding theorem. More precisely, if $G$ is not torsion-
free, then property 2 does not necessarily imply property 1 anymore.

######  Example B.5.

Let $M=\big{(}\mathds{Z}/2\mathds{Z},\cdot\big{)}$, where
$\mathds{Z}/2\mathds{Z}=\\{0,1\\}$. This is a commutative, idempotent monoid
with the following multiplication rules:

$1\cdot 1=1;\quad 1\cdot 0=0;\quad 0\cdot 1=0;\quad 0\cdot 0=0.$

Furthermore, define $G\coloneqq\big{(}\mathds{Z}/2\mathds{Z},+\big{)}$, which
is an abelian group with the following addition rules:

$0+0=0;\quad 0+1=1;\quad 1+0=1;\quad 1+1=0.$

The last rule implies that $G$ has torsion. We define the action of $M$ on $G$
by $X.g\coloneqq X\cdot g$ for all $X\in M$ and $g\in G$. That is, the action
is simply the usual multiplication in the ring
$\big{(}\mathds{Z}/2\mathds{Z},+,\cdot\big{)}$ and therefore clearly an
additive monoid action. Finally, define

$F:M\to G,\quad F(X)\coloneqq 1-X.$

We have

$F(XY)=1-XY=1-X+X-XY=1-X+X\cdot(1-Y)=F(X)+X.F(Y),$

implying that $F$ satisfies the chain rule. Thus, $F$ satisfies all the
properties of Hu’s Theorem 3.2.

Now, set $X_{1}\coloneqq X_{2}\coloneqq X_{3}\coloneqq 0\in M$. Then we have

$TC_{F}(X_{1};X_{2};X_{3})=F(0)+F(0)+F(0)-F(0\cdot 0\cdot 0)=1+1=0.$

However, we have

$F(X_{3};X_{1}X_{2})=F(0;0)=F(0)=1.$

This means that the $F$-independence
$\big{(}X_{1}X_{2}\big{)}\perp\\!\\!\\!\perp_{F}X_{3}$ does _not_ hold,
implying that $X_{1},X_{2},X_{3}$ are _not_ mutually independent. Thus we
cannot omit the assumption of torsion-freeness in the Theorem.

Note that in light of Proposition A.5, the construction of $F$ can be
explained as follows: $M$ is a bounded monoid with top element $0\in M$. Then,
$G^{\top}=G$, and so $1\in G$ is one of the annihilated elements. We then see:

$\big{[}\Psi(1)\big{]}(X)=1-X.1=1-X=F(X),$

showing that $F=\Psi(1)$. The only other function satisfying the chain rule,
$\Psi(0)$, is trivial, and does therefore not give rise to a counter example.

##  Appendix C General Consequences of Section 4

In this appendix, we take a look at Yeung et al. (2019) and explain which
results generalize to our setting. As it turns out, all these results
generalize without problem with the same proofs, or otherwise cannot even be
formulated in our case since the formulations are based on inequalities, which
does not make sense in the context of general abelian groups.

Fix a commutative, idempotent monoid $M$ acting on an abelian group $G$ and a
function $F:M\to G$ satisfying the chain rule. We fix elements
$X_{1},\dots,X_{n}\in M$, giving rise to $\widetilde{F}:2^{\widetilde{X}}\to
G$ by Hu’s Theorem 3.2, and a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$
with $\mathcal{V}=[n]$.

#### Smallest Graph Representations

######  Terminology C.1.

If $X_{1},\dots,X_{n}$ form an $F$-Markov random field with respect to
$\mathcal{G}$, then we also say that $\mathcal{G}$ is a (graph)
_representation_ for $X_{1},\dots,X_{n}$ with respect to $F$.

######  Definition C.2 (Subgraph).

If $\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ is a
second graph with $\mathcal{V}^{\prime}\subseteq\mathcal{V}$ and
$\mathcal{E}^{\prime}\subseteq\mathcal{E}$, then we say that
$\mathcal{G}^{\prime}$ is a _subgraph_ of $\mathcal{G}$.

######  Definition C.3 (Smallest Graph Representation).

$\mathcal{G}^{\prime}$ is said to be the _smallest graph representation_ for
$X_{1},\dots,X_{n}$ (with respect to $\perp\\!\\!\\!\perp_{F}$) if
$\mathcal{G}^{\prime}$ is a representation for $X_{1},\dots,X_{n}$ and a
subgraph of all other representations for $X_{1},\dots,X_{n}$.

######  Theorem C.4 (Smallest Graph Representation).

Define $\widehat{\mathcal{G}}\coloneqq\big{(}[n],\widehat{\mathcal{E}}\big{)}$
with $\\{i,j\\}\in\widehat{\mathcal{E}}$ if and only if

$X_{[n]\setminus\\{i,j\\}}.F(X_{i};X_{j})=\widetilde{F}\big{(}p_{\\{i,j\\}}\big{)}\neq
0.$ (39)

If $X_{1},\dots,X_{n}$ has a smallest graph representation, then it equals
$\widehat{\mathcal{G}}$.

###### Proof.

This is simply Yeung et al. (2019), Theorem 3, generalized to our setting.
Note that the first equality in Equation (39) is simply Corollary 3.4 and
always holds. The original proof can be copied word for word. Only once, an
“inequality sign” needs to be replaced by an “unequal sign”. ∎

#### Smallest Graphs for Subfields of Markov Random Fields

######  Definition C.5 (Marginalization of Graph).

Let $\mathcal{V}^{\prime}\subseteq\mathcal{V}$. Then the Marginalization of
$\mathcal{G}$ for $\mathcal{V}^{\prime}$ is defined as
$\mathcal{G}^{*}(\mathcal{V}^{\prime})\coloneqq(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$
with $\\{i,j\\}\in\mathcal{E}^{\prime}$ if and only if there is a walk from
$i$ to $j$ in $\mathcal{G}$ with all intermediate vertices in
$\mathcal{V}\setminus\mathcal{V}^{\prime}$.

######  Notation C.6.

Let $\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ be a
graph with $\mathcal{V}^{\prime}\subseteq\mathcal{V}=[n]$. Then we write
$\mathcal{G}\Longrightarrow\mathcal{G}^{\prime}$ if for all
$Y_{1},\dots,Y_{n}$ that form an $F$-Markov random field with respect to
$\mathcal{G}$, $Y_{i},i\in\mathcal{V}^{\prime}$ form an $F$-Markov random
field with respect to $\mathcal{G}^{\prime}$. Note that
“$\mathcal{G}\Longrightarrow\mathcal{G}^{\prime}$” is not a statement about
graphs alone, as it depends on $F:M\to G$.

######  Theorem C.7 (Graphs for Subfields).

Assume that there is at least one element $Z\in M$ with $F(Z)\neq 0$. Let
$\mathcal{V}^{\prime}\subseteq\mathcal{V}$ be a subset. Then
$\mathcal{G}^{*}(\mathcal{V}^{\prime})$ is the smallest graph
$\mathcal{G}^{\prime}$ such that
$\mathcal{G}\Longrightarrow\mathcal{G}^{\prime}$.

###### Proof.

This is precisely Yeung et al. (2019), Theorem 8. The proof is exactly the
same, except that the condition $I(Z)>0$ from the original paper is replaced
by $F(Z)\neq 0$, and the constant random variable is replaced by $\bm{1}\in
M$. ∎

######  Remark C.8.

If we drop the condition that there is $Z\in M$ with $F(Z)\neq 0$, then the
conclusion is wrong. Indeed, if $F$ is trivial, then all $F$-independences
always hold, meaning that the graph
$\mathcal{G}^{\prime}\coloneqq(\mathcal{V}^{\prime},\emptyset)$ with empty
edge set would be the smallest graph with
$\mathcal{G}\Longrightarrow\mathcal{G}^{\prime}$. The existence of $Z$ with
$F(Z)\neq 0$ ensures that we can for all edges in
$\mathcal{G}^{*}\big{(}\mathcal{V}^{\prime}\big{)}$ construct an $F$-Markov
random field for $\mathcal{G}$ that is _faithful_ to that edge by having a
corresponding dependence.

#### Rewriting the Values of Atoms in $F$-Markov Random Fields

Section 5 in Yeung et al. (2019) discusses a characterization for forests of
paths. Namely, $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is a forest of paths if
and only if for all probability distributions $P$ and all discrete random
variables $X_{1},\dots,X_{n}$ that form a Markov random field with respect to
$\mathcal{G}$ and $P$, the corresponding $I$-diagram is nonnegative. These
results cannot be stated in our generalized setting since $F$ takes values in
an unspecified abelian group $G$ that may not have an associated order
relation to begin with. However, that section still contains an interesting
result worth stating in our generalized setting:

######  Theorem C.9 (Atoms in Markov Random Fields).

Assume that $X_{1},\dots,X_{n}$ form an $F$-Markov random field with respect
to $\mathcal{G}$. Let $p_{\mathcal{I}}$ be a connected atom, where
$\mathcal{I}\subseteq[n]$ has at least two elements. Define

$\mathcal{B}\coloneqq\Big{\\{}i\in\mathcal{I}\ \big{|}\
p_{\mathcal{I}\setminus i}\text{ is connected}\Big{\\}}.$

Then one has

$\widetilde{F}(p_{\mathcal{I}})=X_{\mathcal{V}\setminus\mathcal{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in\mathcal{I}}X_{i}\big{)}=X_{\mathcal{V}\setminus\mathcal{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in\mathcal{B}}X_{i}\big{)}.$

###### Proof.

Note that the first equality is simply Corollary 3.4. The second equality is
Yeung et al. (2019), Theorem 11. The original proof generalizes word for word
to our setting. ∎

######  Remark C.10.

The preceding theorem deals with connected atoms. For disconnected atoms
$p_{\mathcal{I}}$, Theorem 4.16 shows $\widetilde{F}(p_{\mathcal{I}})=0$.

Furthermore, note that Theorem C.9 generalizes a special case of Corollary
4.18: that corollary implies that for an $F$-Markov chain $X_{1},\dots,X_{n}$
and an “interval” $I=\left[i:j\right]\subseteq[n]$ for $i<j$, one has

$X_{[n]\setminus I}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}=X_{[n]\setminus I}.F(X_{i};X_{j}).$

#### Trees and Drawing $F$-Diagrams for $F$-Markov Random Fields

The remaining results in Yeung et al. (2019) are essentially graph theoretic
in nature and not dependent on $F$. In Theorem 9, they discuss when the
marginalization of a graph is a tree. Finally, in Section 6, they discuss an
algorithm for drawing an $I$-diagram, with two requirements relating to the
graph $\mathcal{G}$: connected atoms are depicted as nonempty and disconnected
atoms as empty. These diagrams are then suitable to express any $F$-diagram of
any $F$-Markov random field corresponding to $\mathcal{G}$, as Theorem 4.16
shows. For the case of path-shaped graphs corresponding to Markov chains, we
saw examples of such depictions in Figure 6. The algorithm in Section 6 of
Yeung et al. (2019) works for any graph $\mathcal{G}$.

##  Appendix D Slices of $I$-Diagrams

Our generalizations of the main results from Yeung et al. (2002), Theorems
4.11 and 4.16, work in the framework of $F$-independence, where $F$ satisfies
the full set of assumptions in Hu’s Theorem 3.2. In contrast, the original
results were formulated for the $P$-independence with respect to a fixed
probability distribution $P$, thus engaging only with one “slice” of the
$I$-diagrams, as we’ll explain soon. A priori, it may seem unclear whether
these original results can actually be deduced from our supposed
generalizations. In this subsection, we prove that this is indeed possible.

Let $M$ be the monoid of (equivalence classes of) discrete random variables on
$\Omega$, and
$I:M\to\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$ the entropy
function, as defined in Equation (25). In this whole section, let
$X_{1},\dots,X_{n}$ be fixed discrete random variables on the sample space
$\Omega$. Let
$\widetilde{I}:2^{\widetilde{X}}\to\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$
be the measure resulting from Hu’s Theorem 3.2. For any probability
distribution $P\in\Delta(\Omega)$, we then obtain the “slice”

$\widetilde{I}^{P}:2^{\widetilde{X}}\to\mathds{R},\quad
A\mapsto\big{[}\widetilde{I}(A)\big{]}(P).$ (40)

This is a signed measure with values in the real numbers instead of functions.

######  Theorem D.1 (Characterization of $P$-FCMIs).

Let $I:M\to\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$ be the
Shannon entropy function. Let $X_{1},\dots,X_{n}$ be discrete random variables
on $\Omega$ and $P\in\Delta(\Omega)$ a probability distribution, giving rise
to $\widetilde{I}^{P}:2^{\widetilde{X}}\to\mathds{R}$ by Equation (40). Let
$K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ be a conditional partition of $[n]$
with $q\geq 2$. Then the following two statements are equivalent:

  * •

$K$ induces a $P$-FCMI:
$P:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$;

  * •

For all $p_{W}\in\operatorname{Im}(K)$: $\widetilde{I}^{P}(p_{W})=0$.

###### Proof.

Let $\mathcal{R}$ be the following property on elements
$P^{\prime}\in\Delta(\Omega)$:

$\mathcal{R}(P^{\prime})\quad:\Longleftrightarrow\quad
P^{\prime}:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}.$

Then by Proposition 5.8, and using that it is also well-defined and
measurable, this is stable property. Consequently, we can define the
restricted entropy function
${I}_{\mathcal{R}}:{M}_{\mathcal{R}}\to\operatorname{Meas}\big{(}{\Delta(\Omega)}_{\mathcal{R}},\mathds{R}\big{)}$,
which satisfies the chain rule according to Proposition 5.13. Now, we claim
that the following conditional mutual independence holds:

${I}_{\mathcal{R}}:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}.$ (41)

By definition, conditional mutual independences are given by a set of pairwise
independences, and these in turn by the vanishing of conditional mutual
information. Thus, the claim reduces to the following: for all $i\in[q]$, we
have

$X_{J}.{I}_{\mathcal{R}}\big{(}X_{L_{i}};X_{L_{\setminus i}}\big{)}=0,$

where $L_{\setminus i}\coloneqq\bigcup_{k\neq i}L_{k}$. But this is clear
since for all $P^{\prime}$ with $\mathcal{R}(P^{\prime})$, we have
$X_{L_{i}}\underset{P^{\prime}}{\perp\\!\\!\\!\perp}X_{L_{\setminus i}}\ |\
X_{J}$ and thus, as is well known, the vanishing of the corresponding
conditional mutual information follows:

$\Big{[}X_{J}.{I}_{\mathcal{R}}\big{(}X_{L_{i}};X_{L_{\setminus
i}}\big{)}\Big{]}\big{(}P^{\prime}\big{)}=\Big{[}X_{J}.I\big{(}X_{L_{i}};X_{L_{\setminus
i}}\big{)}\Big{]}\big{(}P^{\prime}\big{)}=0.$

This proves the claim, Equation (41).

Now, assume that the first statement holds, i.e.,
$P:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$. Then $\mathcal{R}(P)$ holds. From Equation (41), we obtain by
Theorem 4.11 that for all $p_{W}\in\operatorname{Im}(K)$:
$\widetilde{{I}_{\mathcal{R}}}(p_{W})=0$. It follows

$\widetilde{I}^{P}(p_{W})=\big{[}\widetilde{I}(p_{W})\big{]}(P)=\big{[}\widetilde{{I}_{\mathcal{R}}}(p_{W})\big{]}(P)=0,$

which proves one direction.

For the other direction, assume that $\widetilde{I}^{P}(p_{W})=0$ for all
$p_{W}\in\operatorname{Im}(K)$. We want to show
$P:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$. As is well-known, this amounts to showing the following for all
$i\in[q]$:

$\Big{[}X_{J}.I\big{(}X_{L_{i}};X_{L_{\setminus i}}\big{)}\Big{]}(P)=0.$

By Hu’s Theorem 3.2, we thus need to show
$\widetilde{I}^{P}\big{(}\widetilde{X}_{L_{i}}\cap\widetilde{X}_{L_{\setminus
i}}\setminus\widetilde{X}_{J}\big{)}=0$. But note that, clearly, we have
$\widetilde{X}_{L_{i}}\cap\widetilde{X}_{L_{\setminus
i}}\setminus\widetilde{X}_{J}\subseteq\operatorname{Im}(K)$. Thus, the claim
follows from the assumption that $\widetilde{I}^{P}(p_{W})=0$ for all
$p_{W}\in\operatorname{Im}(K)$, together with the fact that
$\widetilde{I}^{P}$ is a signed measure and therefore additive over disjoint
unions. ∎

######  Theorem D.2 (Characterization of $P$-Markov Random Fields).

Let $I:M\to\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$ be the
Shannon entropy function. Let $X_{1},\dots,X_{n}$ be discrete random variables
on $\Omega$ and $P\in\Delta(\Omega)$ a probability distribution, giving rise
to $\widetilde{I}^{P}:2^{\widetilde{X}}\to\mathds{R}$ by Equation (40). Let
$\mathcal{G}$ be a graph with vertex set $[n]$. Then the following two
statements are equivalent:

  * •

$X_{1},\dots,X_{n}$ form a $P$-Markov random field with respect to
$\mathcal{G}$;

  * •

$\widetilde{I}^{P}(p_{\mathcal{W}})=0$ for all atoms $p_{\mathcal{W}}$ that
are disconnected with respect to $\mathcal{G}$.

###### Proof.

Let the property $\mathcal{R}$ be given by
$\mathcal{R}\coloneqq\mathcal{MRF}\big{(}\mathcal{G};X_{1},\dots,X_{n}\big{)}$,
see the discussion after Equation (36). Note that in our application of that
definition, we have $r=0$. Now, assume the first statement, i.e.,
$\mathcal{R}(P)$ holds. We also know from Theorem 5.14 that
$X_{1},\dots,X_{n}$ form an ${I}_{\mathcal{R}}$-Markov random field with
respect to $\mathcal{G}$. Then Theorem 4.16 implies that
$\widetilde{{I}_{\mathcal{R}}}(p_{\mathcal{W}})=0$ for all disconnected atoms
$p_{\mathcal{W}}$. For these atoms, we then obtain

$\widetilde{I}^{P}(p_{\mathcal{W}})=\Big{[}\widetilde{I}(p_{\mathcal{W}})\Big{]}(P)=\Big{[}\widetilde{{I}_{\mathcal{R}}}(p_{\mathcal{W}})\Big{]}(P)=0,$

which proves one direction.

For the other direction, assume that $\widetilde{I}^{P}(p_{\mathcal{W}})=0$
for all disconnected atoms $p_{\mathcal{W}}$. By Proposition 2.9, we need to
show that $X_{1},\dots,X_{n}$ satisfies the cutset property with respect to
$\mathcal{G}$ and $\perp\\!\\!\\!\perp_{P}$. Thus, let $\mathcal{U}$ be a
cutset of $\mathcal{G}$ and
$K\coloneqq\big{(}\mathcal{U},\mathcal{V}_{i}(\mathcal{U}),1\leq i\leq
s\left(\mathcal{U}\right)\big{)}$ the corresponding conditional partition. We
need to show
$P:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{s\left(\mathcal{U}\right)}X_{\mathcal{V}_{i}(\mathcal{U})}\
|\ X_{\mathcal{U}}$. By Theorem D.1, we need to show that
$\widetilde{I}^{P}(p_{\mathcal{W}})=0$ for all atoms
$p_{\mathcal{W}}\in\operatorname{Im}(K)$. All such $p_{\mathcal{W}}$ are
disconnected by Lemma 4.15, and so the result follows from the assumption. ∎

## References

  * Amari [2001] S.-I. Amari.  Information Geometry on Hierarchy of Probability Distributions.  _IEEE Transactions on Information Theory_ , 47(5):1701–1711, 2001.  10.1109/18.930911.
  * Baudot and Bennequin [2015] Pierre Baudot and Daniel Bennequin.  The Homological Nature of Entropy.  _Entropy_ , 17(5):3253–3318, 2015.  ISSN 10994300.  10.3390/e17053253.
  * Baudot et al. [2019] Pierre Baudot, Monica Tapia, Daniel Bennequin, and Jean Marc Goaillard.  Topological Information Data Analysis.  _Entropy_ , 21(9):1–38, 2019.  ISSN 10994300.  10.3390/e21090869.
  * Bishop [2007] Christopher M. Bishop.  _Pattern Recognition and Machine Learning (Information Science and Statistics)_.  Springer, 1 edition, 2007.  ISBN 0387310738.
  * Bishop and Bishop [2023] Christopher Michael Bishop and Hugh Bishop.  _Deep Learning - Foundations and Concepts_.  1 edition, 2023.  ISBN 978-3-031-45468-4.  https://doi.org/10.1007/978-3-031-45468-4.
  * Chaitin [1987] Gregory. J. Chaitin.  _Algorithmic Information Theory_.  Cambridge University Press, oct 1987.  ISBN 9780521343060.  10.1017/CBO9780511608858.  URL https://www.cambridge.org/core/product/identifier/9780511608858/type/book.
  * Cocco and Monasson [2012] S. Cocco and R. Monasson.  Adaptive Cluster Expansion for the Inverse Ising Problem: Convergence, Algorithm and Tests.  _Journal of Statistical Physics_ , 147(2):252–314, April 2012.  10.1007/s10955-012-0463-4.
  * Cover and Thomas [2006] Thomas M. Cover and Joy A. Thomas.  _Elements of Information Theory_.  Wiley-Interscience, 2006.  ISBN 9780471241959.  10.1002/047174882X.
  * Dawid [2001] A P Dawid.  Separoids: A Mathematical Framework for Conditional Independence and Irrelevance.  _Annals of Mathematics and Artificial Intelligence_ , 32(1):335–372, 2001.  ISSN 1573-7470.  10.1023/A:1016734104787.  URL https://doi.org/10.1023/A:1016734104787.
  * Forré [2021] Patrick Forré.  Transitional Conditional Independence.  _arXiv e-prints_ , page arXiv:2104.11547, apr 2021.  URL http://arxiv.org/abs/2104.11547.
  * Hammersley and Clifford [1971] John M Hammersley and Peter Clifford.  Markov Fields on Finite Graphs and Lattices, 1971.
  * Han [1978] Te Sun Han.  Nonnegative Entropy Measures of Multivariate Symmetric Correlations.  _Information and Control_ , 36(2):133–156, 1978\.  ISSN 0019-9958.  https://doi.org/10.1016/S0019-9958(78)90275-9.  URL https://www.sciencedirect.com/science/article/pii/S0019995878902759.
  * Hochschild [1945] Gerhard Hochschild.  On the Cohomology Groups of an Associative Algebra.  _Annals of Mathematics_ , 46(1):58–67, 1945.  ISSN 0003486X.  URL http://www.jstor.org/stable/1969145.
  * Hu [1962] Kuo Ting Hu.  On the Amount of Information.  _Theory of Probability & Its Applications_, 7(4):439–447, 1962.  10.1137/1107041.  URL https://doi.org/10.1137/1107041.
  * Kawabata and Yeung [1992] T Kawabata and R W Yeung.  The structure of the I-measure of a Markov chain.  _IEEE Transactions on Information Theory_ , 38(3):1146–1149, 1992.  10.1109/18.135658.
  * Lang et al. [2022] Leon Lang, Pierre Baudot, Rick Quax, and Patrick Forré.  Information Decomposition Diagrams Applied beyond Shannon Entropy: A Generalization of Hu’s Theorem.  _arXiv e-prints_ , page arXiv:2202.09393, 2022.  URL http://arxiv.org/abs/2202.09393.
  * Li and Vitányi [1997] Ming Li and Paul Vitányi.  _An Introduction to Kolmogorov Complexity and Its Applications_.  Springer, 1997.  ISBN 9783030112974.  10.1007/978-1-4757-3860-5.
  * Medina-Mardones et al. [2021] Anibal M. Medina-Mardones, Fernando E. Rosas, Sebastián E. Rodríguez, and Rodrigo Cofré.  Hyperharmonic analysis for the study of high-order information-theoretic signals.  _Journal of Physics: Complexity_ , 2(3), 2021.  ISSN 2632072X.  10.1088/2632-072X/abf231.
  * Pearl [1985] Judea Pearl.  _Bayesian Networks: A Model of Self-activated Memory for Evidential Reasoning_.  Report (University of California, Los Angeles. Computer Science Dept.). UCLA Computer Science Department, 1985.  URL https://books.google.nl/books?id=1sfMOgAACAAJ.
  * Preston [1976] C Preston.  _Random Fields_.  Lecture Notes in Mathematics. Springer, 1976.  ISBN 9780387078526.  URL https://books.google.nl/books?id=107MoQEACAAJ.
  * Ramesh et al. [2021] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever.  Zero-Shot Text-to-Image Generation.  _arXiv e-prints_ , art. arXiv:2102.12092, February 2021.  10.48550/arXiv.2102.12092.
  * Rombach et al. [2021] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models, 2021.
  * Rosas et al. [2019] Fernando E. Rosas, Pedro A.M. Mediano, Michael Gastpar, and Henrik J. Jensen.  Quantifying High-Order Interdependencies via Multivariate Extensions of the Mutual Information.  _Physical Review E_ , 100(3):1–17, 2019.  ISSN 24700053.  10.1103/PhysRevE.100.032305.
  * Saharia et al. [2022] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S. Sara Mahdavi, Rapha Gontijo Lopes, Tim Salimans, Jonathan Ho, David J Fleet, and Mohammad Norouzi.  Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding.  _arXiv e-prints_ , art. arXiv:2205.11487, May 2022.  10.48550/arXiv.2205.11487.
  * Sohl-Dickstein et al. [2015] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In Francis Bach and David Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 2256–2265, Lille, France, 07–09 Jul 2015. PMLR.  URL https://proceedings.mlr.press/v37/sohl-dickstein15.html.
  * Spitzer [1971] F Spitzer.  _Random Fields and Interacting Particle Systems_.  Mathematical Association of America, 1971.  URL https://books.google.nl/books?id=qv8-AAAAIAAJ.
  * Steudel et al. [2010] Bastian Steudel, Dominik Janzing, and Bernhard Schölkopf.  Causal Markov condition for submodular information measures.  _COLT 2010 - The 23rd Conference on Learning Theory_ , pages 464–476, 2010.
  * Vigneaux [2019] Juan Pablo Vigneaux.  _Topology of Statistical Systems — A Cohomological Approach to Information Theory_.  Phd dissertation, Université de Paris, 2019.
  * Watanabe [1960] Satosi Watanabe.  Information Theoretical Analysis of Multivariate Correlation.  _IBM Journal of Research and Development_ , 4(1):66–82, 1960.  10.1147/rd.41.0066.
  * Yeung [1991] Raumond W. Yeung.  A New Outlook on Shannon’s Information Measures.  _IEEE Transactions on Information Theory_ , 37(3):466–474, 1991.  ISSN 21915776.  10.1109/18.79902.
  * Yeung [2002] Raymond W Yeung.  _A First Course in Information Theory_.  Springer-Verlag, Berlin, Heidelberg, 2002.  ISBN 9781461346456.
  * Yeung [2008] Raymond W Yeung.  _Information Theory and Network Coding_ , volume 46.  Springer Publishing Company, Incorporated, 1 edition, 2008.  ISBN 0387792333.  10.5860/choice.46-5079.
  * Yeung et al. [2002] Raymond W. Yeung, Tony T. Lee, and Zhongxing Ye.  Information-Theoretic Characterizations of Conditional Mutual Independence and Markov Random Fields.  _IEEE Transactions on Information Theory_ , 48(7):1996–2011, 2002.  ISSN 00189448.  10.1109/TIT.2002.1013139.
  * Yeung et al. [2019] Raymond W. Yeung, Ali Al-Bashabsheh, Chao Chen, Qi Chen, and Pierre Moulin.  On Information-Theoretic Characterizations of Markov Random Fields and Subfields.  _IEEE Transactions on Information Theory_ , 65(3):1493–1511, 2019.  ISSN 00189448.  10.1109/TIT.2018.2866564.