[todonotes] [caption, subcaption]

††thanks: Main contributing author.

# Abstract Markov Random Fields

Leon Lang<EMAIL_ADDRESS>Informatics Institute, University of Amsterdam
Clélia de Mulatier<EMAIL_ADDRESS>Informatics Institute, University
of Amsterdam  Institute for Theoretical Physics, University of Amsterdam  Rick
Quax<EMAIL_ADDRESS>Informatics Institute, University of Amsterdam  Patrick
Forré<EMAIL_ADDRESS>Informatics Institute, University of Amsterdam

###### Abstract

Markov random fields are known to be fully characterized by properties of
their information diagrams, or $I$-diagrams. In particular, for Markov random
fields, regions in the $I$-diagram corresponding to disconnected vertex sets
in the graph vanish. Recently, $I$-diagrams have been generalized to
$F$-diagrams, for a larger class of functions $F$ satisfying the chain rule
beyond Shannon entropy, such as Kullback-Leibler divergence and cross-entropy.
In this work, we generalize the notion and characterization of Markov random
fields to this larger class of functions $F$ and investigate preliminary
applications.

We define $F$-independences, $F$-mutual independences, and $F$-Markov random
fields and characterize them by their $F$-diagram. In the process, we also
define $F$-dual total correlation and prove that its vanishing is equivalent
to $F$-mutual independence. We then apply our results to information functions
$F$ that are applied to probability distributions. We show that if the
probability distributions are Markov random fields for the same graph, then we
formally recover the notion of an $F$-Markov random field for that graph. We
then study the Kullback-Leibler divergence on specific Markov chains, leading
to a visual representation of the second law of thermodynamics.

###### Contents

  1. 1 Introduction
  2. 2 Markov Random Fields in Separoids
    1. 2.1 Separoids
    2. 2.2 Conditional Mutual Independences in Separoids
    3. 2.3 Graph Terminology
    4. 2.4 Markov Random Fields in Separoids
    5. 2.5 Markov Chains in Separoids
  3. 3 General Information Diagrams and their Properties
    1. 3.1 Background: the Generalized Hu Theorem and $F$-Diagrams
    2. 3.2 Subset Determination
    3. 3.3 $F$-Independence Satisfies the Separoid Axioms
  4. 4 Characterizing $F$-Independences and $F$-Markov Random Fields
    1. 4.1 Conditional Mutual $F$-Independences and $F$-Dual Total Correlation
    2. 4.2 Full Conditional Mutual $F$-Independences
    3. 4.3 $F$-Markov Random Fields and $F$-Markov Chains
  5. 5 Probabilistic Independences and Markov Random Fields
    1. 5.1 Background: Probabilistic Independence and Monoids of Random Variables
    2. 5.2 Stability under Conditioning
    3. 5.3 Information Functions Satisfying the Chain Rule
    4. 5.4 Restricting Information Measures to Stable Probability Sets
    5. 5.5 The Second Law of Thermodynamics
  6. 6 Discussion
    1. 6.1 Major Findings: Characterizations of $F$–FCMIs, $F$–Markov Random Fields, and Probabilistic Applications
    2. 6.2 Conceivable Extensions of the Theory and Open Questions
  7. A Cohomological Characterization of Functions Satisfying the Chain Rule
  8. B Conditional Mutual $F$-Independences and $F$-Total Correlation
  9. C General Consequences of Section 4
  10. D Slices of $I$-Diagrams

##  1 Introduction

Entropy, mutual information, and higher-order information terms between
several random variables can be visualized in information diagrams, also known
as $I$-diagrams. This is known as Hu’s Theorem (Hu, 1962; Yeung, 1991). These
diagrams become especially interesting when the visualized variables obey
conditional independences, which then implies that some regions in these
diagrams vanish. A series of papers (Kawabata and Yeung, 1992; Yeung et al.,
2002, 2019) exploited this idea to study Markov random fields, which according
to the global Markov property satisfy a set of conditional independences
determined by an underlying graph (Preston, 1976; Spitzer, 1971; Hammersley
and Clifford, 1971). This then implies that all intersections in the
$I$-diagram corresponding to _disconnected vertex sets_ in the graph vanish, a
result we visualize for simple graphs in Figure 1.

Recently, Hu’s theorem has been generalized from entropy $I$ to more general
functions $F$ satisfying a chain rule (Lang et al., 2022). Examples for $F$
are Kullback-Leibler divergence, cross-entropy, Tsallis entropy, and even
Kolmogorov complexity. The resulting $F$-diagrams show structurally the same
relations as $I$-diagrams, and thus allow higher-order $F$-terms to be
visualized and reasoned about in a unified way — see Figure 2.

Functions such as the cross-entropy or Kullback-Leibler divergence are
important in the context of statistical modeling of multivariate data, in
which one aims to find a probabilistic model able to reproduce the information
structure of the data. For instance, the $F$-diagram for cross-entropy allows
us to visualize how the cross-entropy between a model probability distribution
and the data distribution is decomposed into higher-order terms. Cocco and
Monasson (2012) used these higher-order terms (which they called cluster
(cross)-entropies) in their adaptive cluster expansion approach to statistical
modeling of data with Ising models. Kullback-Leibler divergence has been
studied in the context of decompositions of joint entropy and information
(Amari, 2001) and is ubiquitous in machine learning. In other contexts, for
example Kolmogorov complexity, the precise meaning of the higher-order terms
is not yet clear.

In this work, we take the generalization of $I$-diagrams to $F$-diagrams as a
motivation to generalize the results from (Kawabata and Yeung, 1992; Yeung et
al., 2002, 2019). We define $F$-independences by vanishing $F$-terms of degree
two, similar to how the probabilistic independence of random variables is
characterized by vanishing mutual information. We then define $F$-mutual
independences and $F$-dual total correlation. We show that an $F$-mutual
independence is characterized by a vanishing $F$-dual total correlation. We
then define $F$-Markov random fields by the global Markov property and fully
characterize them in terms of the $F$-diagram: The global Markov property
holds if and only if regions corresponding to disconnected vertex sets in the
graph vanish.

We then apply this theory to the case where $F$ is a function like entropy,
Kullback-Leibler divergence, or cross-entropy that is applied to probability
distributions. We show that when applying $F$ to sets of probability
distributions that form a Markov random field with respect to the same graph,
then the underlying random variables form an $F$-Markov random field. In
particular, when applying our $F$-diagram characterization of $F$-Markov
random fields, this implies that regions in the $F$-diagram corresponding to
disconnected vertex sets disappear. We then apply this result to the case of
two joint distributions that form a Markov chain with equal transition
probabilities from one time-step to the next, and the specific case that $F$
is Kullback-Leibler divergence. This leads to a degeneracy of the Kullback-
Leibler diagram in which the Kullback-Leibler divergence progressively shrinks
“over time” — a diagrammatric visualization of a weak version of the second
law of thermodynamics.

Figure 1: We show the effect of the graph structure of simple Markov random
fields on the corresponding $I$-diagrams. The $I$-diagram visualizes the
relationships of the entropy, mutual information, and interaction information
of the variables. The figure is based on Yeung et al. (2002), who proved that
a set of discrete random variables forms a Markov random field corresponding
to a graph if and only if all atoms in the $I$-diagram corresponding to
disconnected sets of vertices in the graph disappear.
Concretely, to a set of vertices $J$, the corresponding atom in the
$I$-diagram is the intersection of all circles with indices $j\in J$ setminus
the union of all the other circles. For the lower left panel, the three sets
of vertices $\\{1,2\\}$, $\\{2,3\\}$, and $\\{1,2,3\\}$ are disconnected,
giving rise to three disappearing atoms in the $I$-diagram. Consequently,
$I(X_{2})$ can be drawn to not intersect with the other circles. However, the
other four sets of vertices $\\{1\\},\\{2\\},\\{3\\},\\{1,3\\}$ are clearly
connected, which means that we cannot infer their corresponding atoms to
vanish. Similar reasoning applies to the other three panels.

### An Outline of this Work

We now outline the rest of this work by explaining the general structure and
highlighting our main theorems and ideas. Briefly, Section 2 studies
independences and Markov random fields in general separoids. Section 3 reviews
the generalized Hu theorem from Lang et al. (2022), defines $F$-independences,
and shows that this forms a separoid. Section 4 presents our generalizations
of the results from Kawabata and Yeung (1992); Yeung et al. (2002, 2019),
including the $F$-diagram characterization of $F$-Markov random fields.
Section 5 studies functions like Kullback-Leibler divergence and the
corresponding Markov random fields, and concludes with a KL-diagram
representation of a weak version of the second law of thermodynamics. Section
6 concludes with a discussion on related work and open questions. In
Appendices A, B, C, and D we collect additional results that are not necessary
to follow the flow of the theory.

What follows now is a more detailed outline. Since all concepts and results we
explain here are explained more completely in later sections, it is possible
to skip ahead to Section 2.

In Section 2, we take a step back from independences induced by a function $F$
by studying independences in general separoids. Thus, we start with a general
commutative, idempotent monoid $M$ and independence relation
$\perp\\!\\!\\!\perp$ over $M^{2}\times M$, written $X\perp\\!\\!\\!\perp Y\
\mid\ Z$ for $X,Y,Z\in M$. We assume that it satisfies the so-called separoid
axioms from Dawid (2001), which hold for both classical probabilistic
independences and the $F$-independences that we define in Section 3. We also
define conditional mutual independences
$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n}{X_{i}}\
|\ Y$ and prove a simple characterization.

Then, we study Markov random fields in separoids using the global Markov
property: We say that elements $X_{1},\dots,X_{n}$ form a Markov random field
with respect to the independence relation $\perp\\!\\!\\!\perp$ and a graph
$\mathcal{G}$ with vertex set $\mathcal{V}=[n]=\\{1,\dots,n\\}$ if for all
disjoint $\mathcal{A},\mathcal{B},\mathcal{C}\subseteq[n]$ for which
$\mathcal{C}$ _separates_ $\mathcal{A}$ from $\mathcal{B}$ in $\mathcal{G}$,
we have $X_{\mathcal{A}}\perp\\!\\!\\!\perp X_{\mathcal{B}}\ |\
X_{\mathcal{C}}$. We then characterize Markov random fields equivalently by
the _cutset property_ ; It states that if a vertex set $\mathcal{U}$ is a
“cutset” that, when removed, cuts the rest of the graph into components
$\mathcal{V}_{1},\dots,\mathcal{V}_{q}$, then this leads to a corresponding
mutual independence
$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}{X_{\mathcal{V}_{i}}}\
|\ X_{\mathcal{U}}$. Finally, we define Markov chains and provide a simple
characterization.

Figure 2: A depiction of the $I$-diagram and the $F$-diagram from the
(generalized) Hu theorem. On the left, it shows the interplay of (conditional)
Shannon entropy, mutual information, and interaction information for three
discrete random variables $X,Y,Z$. On the right, $X,Y$ and $Z$ are elements of
a commutative, idempotent monoid, generalizing the collection of equivalence
classes of random variables together with their joint operation, and the
higher-order terms are all derived from a function $F$ satisfying the chain
rule $F(XY)=F(X)+X.F(Y)$.

In Section 3, we explain the generalized Hu theorem from Lang et al. (2022)
and important consequences. Namely, we work with a commutative, idempotent
monoid $M$ acting additively on an abelian group $G$, with the action written
$X.g\in G$ for $X\in M$ and $g\in G$, and a function $F:M\to G$ that satisfies
the chain rule of information:

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

This is analogous to the chain rule of entropy, often written as
$I(XY)=I(X)+I(Y\mid X)$. In the general setting, one can define higher-order
information terms $F\coloneqq F_{q}:M^{q}\to G$, written
$F(X_{1};\dots;X_{q})$, inductively, in the same way in which mutual
information and interaction information relate to Shannon entropy. Hu’s
theorem, Theorem 3.2, then provides a way to visualize these functions in
$F$-diagrams, see also Figure 2. We also define $F$-independences by
$X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z$ if $Z.F(X;Y)=0$, in analogy to the
characterization of probabilistic independences in terms of mutual
information. In Proposition 3.11, we show that this satisfies the separoid
axioms, and so all results from Section 2 apply in this context.

One crucial property that is used in the proof of Proposition 3.11 and later
in Section 4 is what we call _subset determination_. It states that when the
value of a region in an $F$-diagram is known, this fully determines the value
of all subregions. In particular, if a region in an $F$-diagram vanishes, then
all subsets vanish as well. A precise formulation is given in Theorem 3.5.
Crucially, this replaces the repeated usage of inequalities in the proofs in
(Yeung, 2002), which we could not make use of in our general context. As an
aside, in Appendix A, we show that the basic idea of subset determination
implies a characterization of all functions $F$ satisfying the chain rule, as
long as $M$ contains a “top element” $\top$ such that $X\cdot\top=\top$ for
all $X\in M$ — which is the case for finitely generated $M$. The functions $F$
then correspond to elements in $G$ that are _annihilated_ by $\top$, by the
simple mapping $F\mapsto F(\top)$. We also provide a cohomological
interpretation of this result.

To avoid misunderstandings, we mention a subtlety with subset determination:
it only applies to $F$-diagrams for functions $F:M\to G$ from a monoid to an
abelian group _on which the monoid additively acts_ , a viewpoint that was
pioneered in information cohomology (Baudot and Bennequin, 2015; Vigneaux,
2019; Baudot et al., 2019). Formally, for information functions such as
entropy or Kullback-Leibler divergence, it becomes invalid when _fixing the
underlying probability distribution_. For example, the joint entropy
$I^{P}(XY)$ does not determine the mutual information $I^{P}(X;Y)$.
Nevertheless, we will manage to apply our results to classical information
functions in Section 5 and can deduce Yeung’s results for fixed distributions,
as we demonstrate in Appendix D.

In Section 4, we generalize the results from Kawabata and Yeung (1992); Yeung
et al. (2002). We start by a simple characterization of pairwise
$F$-independences via the $F$-diagram. Motivated by this special case, and
generalizing the classical case (Han, 1978), we define $F$-dual total
correlation by

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

where $X_{[n]}=X_{1}\cdots X_{n}$. In Theorem 4.5, we then characterize
conditional mutual $F$-independences
$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n}X_{i}\
|\ Y$ by the vanishing of (conditional) $F$-dual total correlation
$Y.DTC_{F}(X_{1};\dots;X_{n})$. The theorem also uses Hu’s theorem to
characterize this by the vanishing of the corresponding atomic regions. This
crucially uses subset determination, Theorem 3.5, as visualized in Figure 3.
Notably, we also study $F$-total correlation $TC_{F}$, generalizing classical
total correlation (Watanabe, 1960), and find that it also provides a
characterization of mutual $F$-independences, albeit only if the abelian group
$G$ is _torsion-free_ ; The reason is that the total correlation double-counts
atoms. This is studied in Appendix B.

Figure 3: One key ingredient in the $F$-diagram characterization of $F$-Markov
random fields is the characterization of $F$-mutual independences, Theorem
4.5, here visualized for three elements $X_{1},X_{2},X_{3}\in M$. The
characterization shows that the mutual independence is equivalent to the
vanishing of $F$-dual total correlation $DTC_{F}(X_{1};X_{2};X_{3})$, which,
by Hu’s theorem, Theorem 3.2, corresponds to the vanishing of a region of four
atoms in the $F$-diagram, visualized as gray. Subset determination, Theorem
3.5, then allows to conclude that every _individual_ atom in this region
vanishes, as shown in the rightmost part of the figure. The implication from
right to left again follows from Hu’s theorem and the fact that $F$-diagrams
visualize a _measure_ , meaning that larger regions are the sum of their
atoms.

We then define $F$-Markov random fields by reference to the definition in
Section 2, i.e., as Markov random fields corresponding to the independence
relation $\perp\\!\\!\\!\perp_{F}$ coming from a function $F$. In Theorem
4.16, we then show that this is fully characterized by the vanishing of atoms
in the $F$-diagram that correspond to disconnected vertex sets in the
underlying graph. This characterization uses the cutset property of Markov
random fields proved in Section 2, which formulates Markov random fields by
the vanishing of a collection of so-called _full conditional mutual
$F$-independences_ — i.e., conditional mutual independences consisting of
variables $X_{1},\dots,X_{n}$ in which each variable appears exactly once, but
where the variables can also be bundled together into joint variables. One
ingredient of Theorem 4.16 is thus Theorem 4.11, the characterization of full
conditional mutual $F$-independences in terms of the $F$-diagram. Finally, in
Appendix C, we explain which results from Yeung et al. (2019) generalize to
our setting.

In Section 5, we then study the case where the information functions are
applies to probability distributions. In particular, $M$ is then a monoid of
equivalence classes of random variables acting additively on the abelian group
$G=\operatorname{Meas}(\Delta(\Omega)^{r+1},\mathds{R})$ of measurable
functions from tuples of $r+1$ probability distributions over a finite sample
space $\Omega$ to the real numbers. $F:M\to G$ is from a specific class of
functions such as entropy (for $r=0$), cross-entropy, or Kullback-Leibler
divergence (for $r=1$). To give meaning to the resulting functions, we briefly
explain how the higher-order cross-entropy and Kullback-Leibler divergence
relate to the cluster cross-entropy from Cocco and Monasson (2012). We then
adapt $G$ to only contain functions on _subsets_ of probability distributions
that are conditionally stable, which allows to restrict $F$ without losing the
monoid action from $M$ to $G$. As we show, the property “is a probabilistic
Markov random field” is conditionally stable, and so we can restrict
information functions $F$ to this and similar properties.

In Theorem 5.14, we obtain an important result: When restricting $F$ to tuples
of probability distributions that satisfy a conditionally stable property that
implies the Markov random field property, then the underlying random variables
formally form an $F$-Markov random field as in Section 4.111Importantly, there
is no reverse of this statement. E.g., if two distributions $P$ and $Q$ give
rise to a Kullback-Leibler diagram with vanishing regions corresponding to the
graph of a Markov random field, it does _not_ imply that $P$ and $Q$ factorize
according to the graph. For example, whenever $P=Q$, the whole Kullback-
Leibler diagram vanishes trivially, but we can’t conclude anything nontrivial
about $P$ or $Q$ from it. In particular, using Theorem 4.16, this leads to the
vanishing of regions in the $F$-diagram that correspond to disconnected vertex
sets. We apply this to the case that $F$ is the Kullback-Leibler divergence
restricted to tuples of joint probability distributions on a Markov chain with
equal transition probabilities from one time-step to the next. In Theorem 5.15
and Figure 7, we obtain a degeneracy of the Kullback-Leibler diagram that can
be interpreted as a diagram-representation of a weak version of the second law
of thermodynamics: The Kullback-Leibler divergence progressively “shrinks over
time”.

Finally, in Section 6, we summarize our results and discuss possible
extensions of the theory and open questions.

### Notation

For $i,k\in\mathds{N}$, we set $\left[i:k\right]\coloneqq\\{i,i+1,\dots,k\\}$
if $i\leq k$ and $\left[i:k\right]=\emptyset$, else. As a special case, we set
$[k]\coloneqq\left[1:k\right]$. If $I$ is a set and $i\in I$, we often write
$I\setminus i$ for $I\setminus\\{i\\}$. For a set $\Sigma$, we denote by
$2^{\Sigma}$ its power set, i.e., the set of its subsets. If $W_{i}$ are sets
indexed with $i\in I$, then $W_{I}$ denotes $\bigcup_{i\in I}W_{i}$. If
$X_{i},i\in I$ are elements of a commutative monoid and $A\subseteq I$, then
we set $X_{A}\coloneqq\prod_{a\in A}X_{a}$. If $X_{1},\dots,X_{n}$ are
elements of a separoid that form a Markov chain, then we will write $X_{1}\to
X_{2}\to\dots\to X_{n}$. We will denote the trivial measurable space by
$\mathop{\scalebox{1.5}{\raisebox{-0.86108pt}{$\ast$}}}$, which contains
precisely one element denoted
$\ast\in\mathop{\scalebox{1.5}{\raisebox{-0.86108pt}{$\ast$}}}$.

##  2 Markov Random Fields in Separoids

In this section, we study Markov random fields in general separoids to prepare
for our generalizations of information characterizations of Markov random
fields. In Section 2.1, we define separoids, which generalize collections of
random variables and their conditional independence relations. In Section 2.2,
we define conditional _mutual_ independences in separoids and present three
equivalent descriptions. They are used in the _cutset_ description of Markov
random fields, which we prove in Section 2.4 to be equivalent to the usual
global Markov property. In Section 2.3, we introduce the necessary graph
terminology. Finally, Section 2.5 defines Markov chains in separoids and
characterizes them as Markov random fields corresponding to a path-shaped
graph.

###  2.1 Separoids

Recall that a commutative, idempotent monoid $M=(M,\cdot,\bm{1})$ consists of
a set $M$ together with a multiplication rule $\cdot:M\times M\to M$ that is
associative, commutative, has $\bm{1}$ as its neutral element, and is
idempotent: $X\cdot X=X$ for all $X\in M$. Commutative, idempotent monoids
generalize sets of equivalence classes of random variables.

Let $M$ be a commutative, idempotent monoid. For $X,Y\in M$, write $X\precsim
Y$ if $X\cdot Y=Y$. With this definition, $(M,\precsim)$ becomes a _join-
semilattice_ , which is an equivalent description of a commutative, idempotent
monoid — but we will not make use of that viewpoint. We now define separoids,
introduced in Dawid (2001). We use the slightly adapted but equivalent version
of the separoid axioms from Forré (2021), Appendix A.4:

######  Definition 2.1 (Separoid, Separoid Axioms).

Let $M$ be a commutative, idempotent monoid. Let $\perp\\!\\!\\!\perp$ be a
relation on $M^{2}\times M$, written for $X,Y,Z\in M$ by

$X\perp\\!\\!\\!\perp Y\ |\ Z.$

The tuple $(M,\perp\\!\\!\\!\perp)$ is called a _separoid_ if
$\perp\\!\\!\\!\perp$ satisfies the following _separoid axioms_ for all
$X,Y,Z,W\in M$:

$\displaystyle\mathrm{(S1)\ symmetry}:X\perp\\!\\!\\!\perp Y\ |\ Z\ \
\Longrightarrow\ \ Y\perp\\!\\!\\!\perp X\ |\ Z;$ $\displaystyle\mathrm{(S2)\
redundancy}:W\precsim Z\ \ \Longrightarrow\ \ W\perp\\!\\!\\!\perp Y\ |\ Z;$
$\displaystyle\mathrm{(S3)\ decomposition}:WX\perp\\!\\!\\!\perp Y\ |\ Z\ \
\Longrightarrow\ \ X\perp\\!\\!\\!\perp Y\ |\ Z;$ $\displaystyle\mathrm{(S4)\
weak\ union}:WX\perp\\!\\!\\!\perp Y\ |\ Z\ \ \Longrightarrow\ \
W\perp\\!\\!\\!\perp Y\ |\ XZ;$ $\displaystyle\mathrm{(S5)\
contraction}:\big{(}W\perp\\!\\!\\!\perp Y\ |\ XZ\mathrm{\ and\
}X\perp\\!\\!\\!\perp Y\ |\ Z\big{)}\ \ \Longrightarrow\ \
WX\perp\\!\\!\\!\perp Y\ |\ Z.$

In this paper, if a relation $X\perp\\!\\!\\!\perp Y\ |\ Z$ holds, then we
also say “$X$ and $Y$ are independent given $Z$”, or “$X$ and $Y$ are
independent conditioned on $Z$”, and often append “with respect to
$\perp\\!\\!\\!\perp$” to clarify the independence relation.

Note that properties (S2)–(S5) have obvious “right-handed versions” as well
due to symmetry (S1). When we refer to one of the properties (S2)–(S5), then
we mean one of the two versions depending on the context. We will later need
the following simple lemma:

######  Lemma 2.2 (Dawid (2001), Lemma 1.1).

Let $(M,\perp\\!\\!\\!\perp)$ be a separoid. For $X,Y,Z\in M$, we have the
following equivalence:

$X\perp\\!\\!\\!\perp Y\ |\ Z\quad\Longleftrightarrow\quad
XZ\perp\\!\\!\\!\perp YZ\ |\ Z.$

###  2.2 Conditional Mutual Independences in Separoids

Fix a separoid $(M,\perp\\!\\!\\!\perp)$. For $i,k\in\mathds{N}$, we set
$\left[i:k\right]\coloneqq\\{i,i+1,\dots,k\\}$ if $i\leq k$ and
$\left[i:k\right]=\emptyset$, otherwise. As a special case, set
$[k]\coloneqq\left[1:k\right]$. For a set $I$, set $I\setminus i\coloneqq
I\setminus\\{i\\}$. For elements $X_{1},\dots,X_{n}\in M$ and $A\subseteq[n]$,
we write $X_{A}\coloneqq\prod_{i\in A}X_{i}$.

######  Definition 2.3 (Conditional Mutual Independence).

Let $X_{1},\dots X_{n},Y\in M$. We say $X_{1},\dots,X_{n}$ are _mutually
independent given $Y$_, written

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

if for all $i=1,\dots,n$, the following pairwise independence holds:

$X_{i}\perp\\!\\!\\!\perp X_{[n]\setminus i}\ |\ Y.$

Note: in some contexts we may also write

$\Big{(}X_{1}\perp\\!\\!\\!\perp
X_{2}\perp\\!\\!\\!\perp\dots\perp\\!\\!\\!\perp X_{n}\Big{)}\ |\
Y\quad\text{or}\quad
X_{1}\perp\\!\\!\\!\perp\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=2}^{n}X_{i}\
|\ Y$

for the mutual independence of $X_{1},\dots,X_{n}$ given $Y$.

######  Proposition 2.4.

For $X_{1},\dots,X_{n},Y\in M$, the following statements are equivalent:

  1. 1.

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

  2. 2.

For all $i=1,\dots,n$, the following pairwise independence holds:

$X_{i}\perp\\!\\!\\!\perp X_{[i-1]}\ |\ Y;$

  3. 3.

$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n-1}X_{i}\
|\ Y$ and $X_{n}\perp\\!\\!\\!\perp X_{[n-1]}\ |\ Y$;

  4. 4.

for all disjoint $I_{1},I_{2}\subseteq[n]$, one has
$X_{I_{1}}\perp\\!\\!\\!\perp X_{I_{2}}\ |\ Y$.

###### Proof.

1 immediately implies 2 by using decomposition (S3). Assume 2 holds. We want
to prove $1$. Let $i\in[n]$. Assume by induction that we already know

$X_{i}\perp\\!\\!\\!\perp X_{[l]\setminus i}\ |\ Y$ (1)

for some $l\geq i$, where the case $l=i$ holds by assumption. If we can show
the same with $l+1$ replacing $l$, then induction shows the statement for
$l=n$, which then results in mutual independence since $i$ was arbitrary. For
the induction step, note that

$X_{l+1}\perp\\!\\!\\!\perp X_{[l]}\ |\ Y,$ (2)

which, using symmetry (S1) and weak union (S4), implies

$X_{i}\perp\\!\\!\\!\perp X_{l+1}\ |\ YX_{[l]\setminus i}.$ (3)

Contraction (S5) applied to Equations (1) and (3) gives

$X_{i}\perp\\!\\!\\!\perp X_{[l+1]\setminus i}\ |\ Y,$

which shows the induction step.

Knowing that 1 and 2 are equivalent then immediately implies that both are
equivalent to 3.

It is also clear that 4 implies 1. Finally, we show that 1 implies 4: let
$I_{1},I_{2}\subseteq[n]$ be disjoint. The case $I_{1}=\emptyset$ is trivial
by redundancy $(S2)$. Thus, assume $\emptyset\neq
I_{1}=\big{\\{}i_{1},\dots,i_{k}\big{\\}}$ with pairwise different elements
$i_{l}$. Then from decomposition (S3) applied to the independence
$X_{i_{1}}\perp\\!\\!\\!\perp X_{[n]\setminus i_{1}}\ |\ Y$ we obtain

$X_{i_{1}}\perp\\!\\!\\!\perp X_{I_{2}}\ |\ Y.$

By induction, we can assume

$X_{I_{1}\setminus i_{k}}\perp\\!\\!\\!\perp X_{I_{2}}\ |\ Y$ (4)

and want to show that we can add $X_{i_{k}}$ to the left-hand-side. By
decomposition (S3) applied to the independence $X_{i_{k}}\perp\\!\\!\\!\perp
X_{[n]\setminus i_{k}}\ |\ Y$ we obtain

$X_{i_{k}}\perp\\!\\!\\!\perp X_{I_{1}\cup I_{2}\setminus i_{k}}\ |\ Y,$

and thus by weak union (S4)

$X_{i_{k}}\perp\\!\\!\\!\perp X_{I_{2}}\ |\ YX_{I_{1}\setminus i_{k}}.$ (5)

Contraction (S5) applied to Equations (4) and (5) shows

$X_{I_{1}}\perp\\!\\!\\!\perp X_{I_{2}}\ |\ Y,$

which is the independence we wanted to show. ∎

###  2.3 Graph Terminology

######  Definition 2.5 (Graph).

A _graph_ is a tuple $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where

  * •

$\mathcal{V}$ is a finite set, called the set of _vertices_ ;

  * •

$\mathcal{E}\subseteq\big{\\{}\\{i,j\\}\subseteq\mathcal{V}\mid i\neq
j\big{\\}}$, which we call the set of _edges_.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a graph. Instead of
$\\{i,j\\}\in\mathcal{E}$, we also write $i\scalebox{1.6}[1.0]{$-$}j$, or
$i\scalebox{1.6}[1.0]{$-$}j\in\mathcal{E}$.

Note that edges are non-oriented, as indicated by them being sets instead of
tuples. Furthermore, we have $i\neq j$ for every edge
$i\scalebox{1.6}[1.0]{$-$}j$, which means that there are no _loops_ (i.e.,
edges from a vertex to itself) in the graph. However, there can be _cycles_ ,
i.e., walks from a vertex to itself passing through other vertices.

For a subset $\mathcal{U}\subseteq\mathcal{V}$, we can define
${\mathcal{G}}^{\setminus\mathcal{U}}$ as the graph obtained from
$\mathcal{G}$ by removing all the vertices in $\mathcal{U}$ and all the edges
that have at least one endpoint in $\mathcal{U}$. Formally, one can write

${\mathcal{G}}^{\setminus\mathcal{U}}\coloneqq(\mathcal{V}\setminus\mathcal{U},{\mathcal{E}}^{\setminus\mathcal{U}}),\quad\text{where}\quad{\mathcal{E}}^{\setminus\mathcal{U}}\coloneqq\big{\\{}\\{i,j\\}\in\mathcal{E}\mid
i,j\in\mathcal{V}\setminus\mathcal{U}\big{\\}}.$

A _walk_ in $\mathcal{G}$ from $i$ to $j$ is a sequence of edges
$i\scalebox{1.6}[1.0]{$-$}i_{1},i_{1}\scalebox{1.6}[1.0]{$-$}i_{2},\dots,i_{n}\scalebox{1.6}[1.0]{$-$}j$
in $\mathcal{E}$. We write such a walk as
$i\scalebox{1.6}[1.0]{$-$}i_{1}\scalebox{1.6}[1.0]{$-$}\dots\scalebox{1.6}[1.0]{$-$}i_{n}\scalebox{1.6}[1.0]{$-$}j$.
The empty sequence is considered to be a walk from a vertex $i$ to itself, and
walks are allowed to have the same vertices twice. A vertex set
$\mathcal{U}\subseteq\mathcal{V}$ is called _connected in $\mathcal{G}$_ if
for all $i\neq j\in\mathcal{U}$ there is a walk in $\mathcal{G}$ from $i$ to
$j$.222Note that in Figure 1, we also have a notion of connectedness. That
notion, however, is about connectedness in
${\mathcal{G}}^{\setminus\big{(}\mathcal{V}\setminus\mathcal{U}\big{)}}$, see
Definition 4.14. A set $\mathcal{U}\subseteq\mathcal{V}$ is called a
_component_ if it is a maximal connected set, that is:

  * •

$\mathcal{U}$ is connected in $\mathcal{G}$;

  * •

if $\mathcal{U}\subseteq\mathcal{W}$ and $\mathcal{W}$ is connected in
$\mathcal{G}$, then $\mathcal{U}=\mathcal{W}$.

It is easy to see that the set of components of $\mathcal{G}$ forms a
partition of $\mathcal{V}$: formally, the components are the equivalence
classes under the equivalence relation $\sim$ on $\mathcal{V}$ that is defined
by $i\sim j$ if there is a walk from $i$ to $j$ in $\mathcal{G}$. For a vertex
set $\mathcal{U}\subseteq\mathcal{V}$, we define $s\left(\mathcal{U}\right)$
as the number of components in the graph
${\mathcal{G}}^{\setminus\mathcal{U}}$. In general, we denote by
$\mathcal{V}_{1}(\mathcal{U}),\dots,\mathcal{V}_{s\left(U\right)}(\mathcal{U})$
these components. We call $\mathcal{U}$ a _cutset_ if $s\left(U\right)>1$.
Note that cutsets do not necessarily need to “cut” anything: if $\mathcal{G}$
already contains several components, then $\mathcal{U}=\emptyset$ is a cutset.
Finally, for disjoint subsets
$\mathcal{A},\mathcal{B},\mathcal{C}\subseteq\mathcal{V}$, we say that
$\mathcal{C}$ _separates_ $\mathcal{A}$ from $\mathcal{B}$ if _every_ walk
from _any_ vertex in $\mathcal{A}$ to _any_ vertex in $\mathcal{B}$ passes
through _some_ vertex in $\mathcal{C}$. Note: if
$\mathcal{A}\neq\emptyset\neq\mathcal{B}$ in this definition, then
$\mathcal{C}$ is automatically a cutset.

###  2.4 Markov Random Fields in Separoids

Fix again a general separoid $(M,\perp\\!\\!\\!\perp)$. In this part, we
define Markov random fields by the global Markov property and prove the
equivalence to the cutset property.

######  Definition 2.6 (Global Markov Property, Markov Random Field).

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a graph with $\mathcal{V}=[n]$.
A sequence of elements $X_{1},\dots,X_{n}\in M$ is called a _Markov Random
Field_ with respect to $\perp\\!\\!\\!\perp$ and $\mathcal{G}$ if it satisfies
the _global Markov property_ , that is: for all disjoint
$\mathcal{A},\mathcal{B},\mathcal{C}\subseteq\mathcal{V}$ such that
$\mathcal{C}$ separates $\mathcal{A}$ from $\mathcal{B}$, we have

$X_{\mathcal{A}}\perp\\!\\!\\!\perp X_{\mathcal{B}}\ |\ X_{\mathcal{C}}.$

######  Definition 2.7 (Full Conditional Mutual Independence (FCMI)).

Let $X_{1},\dots,X_{n}\in M$. A conditional mutual independence

$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J},$

where $L_{1},\dots,L_{q},J\subseteq[n]$ are pairwise disjoint sets whose union
is $[n]$, is called a _full conditional mutual independence_ (with respect to
n and $X_{1},\dots,X_{n}$) — or FCMI for short.

The term “full” indicates that each of the variables $X_{i}$, $i=1,\dots,n$,
appears exactly ones.

######  Definition 2.8 (Cutset Property).

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ a graph with $\mathcal{V}=[n]$. A
sequence of elements $X_{1},\dots,X_{n}\in M$ is said to satisfy the _cutset
property_ with respect to $\perp\\!\\!\\!\perp$ and $\mathcal{G}$ if for all
cutsets $\mathcal{U}\subseteq\mathcal{V}$, the FCMI

$\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}}$

holds.

The following proposition shows that both definitions are equivalent. For the
special case of probabilistic independence, this was also stated in the
introduction of Yeung et al. (2002).

######  Proposition 2.9.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ a graph with $\mathcal{V}=[n]$. A
sequence of elements $X_{1},\dots,X_{n}\in M$ form a Markov random field if
and only if they satisfy the cutset property (with respect to
$\perp\\!\\!\\!\perp$ and $\mathcal{G}$).

###### Proof.

Assume $X_{1},\dots,X_{n}$ satisfy the cutset property with respect to
$\perp\\!\\!\\!\perp$ and $\mathcal{G}$. Let
$\mathcal{A},\mathcal{B},\mathcal{C}\subseteq\mathcal{V}$ disjoint such that
$\mathcal{C}$ separates $\mathcal{A}$ from $\mathcal{B}$. Without loss of
generality, we can assume that $\mathcal{A}$ and $\mathcal{B}$ are both
nonempty, since otherwise the independence $X_{\mathcal{A}}\perp\\!\\!\\!\perp
X_{\mathcal{B}}\ |\ X_{\mathcal{C}}$ follows from redundancy (S2) and we are
done. This, together with the separation assumption, implies that
$\mathcal{C}$ is a cutset. Let
$\mathcal{V}_{1}(\mathcal{C}),\dots,\mathcal{V}_{s\left(\mathcal{C}\right)}(\mathcal{C})$
be the components of ${\mathcal{G}}^{\setminus\mathcal{C}}$. Since
$\mathcal{A},\mathcal{B}\subseteq\mathcal{V}\setminus\mathcal{C}=\bigcup_{i=1}^{s\left(\mathcal{C}\right)}\mathcal{V}_{i}(\mathcal{C})$,
we have

$\mathcal{A}=\bigcup_{i=1}^{s\left(\mathcal{C}\right)}\mathcal{V}_{i}^{\mathcal{A}}(\mathcal{C}),\quad\mathcal{B}=\bigcup_{i=1}^{s\left(\mathcal{C}\right)}\mathcal{V}_{i}^{\mathcal{B}}(\mathcal{C}),$

where
$\mathcal{V}_{i}^{\mathcal{A}}(\mathcal{C})\coloneqq\mathcal{A}\cap\mathcal{V}_{i}(\mathcal{C})$
and
$\mathcal{V}_{i}^{\mathcal{B}}(\mathcal{C})\coloneqq\mathcal{B}\cap\mathcal{V}_{i}(\mathcal{C})$.
Now, we claim that for all $i$, we have
$\mathcal{V}_{i}^{\mathcal{A}}(\mathcal{C})=\emptyset$ or
$\mathcal{V}_{i}^{\mathcal{B}}(\mathcal{C})=\emptyset$: indeed, if there were
elements $a\in\mathcal{V}_{i}^{\mathcal{A}}(\mathcal{C})$ and
$b\in\mathcal{V}_{i}^{\mathcal{B}}(\mathcal{C})$, then they would both be in
$\mathcal{V}_{i}(\mathcal{C})$ and thus connected by a walk that lies
completely within
$\mathcal{V}_{i}(\mathcal{C})\subseteq\mathcal{V}\setminus\mathcal{C}$, a
contradiction to the assumption that $\mathcal{C}$ separates $\mathcal{A}$
from $\mathcal{B}$.

Thus, we can write

$\mathcal{A}=\bigcup_{i\in
I_{1}}\mathcal{V}_{i}^{\mathcal{A}}(\mathcal{C}),\quad\mathcal{B}=\bigcup_{i\in
I_{2}}\mathcal{V}_{i}^{\mathcal{B}}(\mathcal{C})$ (6)

with $I_{1}\cap I_{2}=\emptyset$. Since $X_{1},\dots,X_{n}$ satisfy the cutset
property and $\mathcal{C}$ is a cutset, we obtain the FCMI
$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{s\left(\mathcal{C}\right)}X_{\mathcal{V}_{i}(\mathcal{C})}\
|\ X_{\mathcal{C}}$, from which, by the equivalence of parts $1$ and $4$ in
Proposition 2.4, we obtain

$X_{\big{[}\bigcup_{i\in
I_{1}}\mathcal{V}_{i}(\mathcal{C})\big{]}}\perp\\!\\!\\!\perp
X_{\big{[}\bigcup_{i\in I_{2}}\mathcal{V}_{i}(\mathcal{C})\big{]}}\ |\
X_{\mathcal{C}}.$ (7)

Equation (6) and decomposition (S3) applied to both the left and right side of
Equation (7) implies $X_{\mathcal{A}}\perp\\!\\!\\!\perp X_{\mathcal{B}}\ |\
X_{\mathcal{C}}$ and thus the global Markov property. Therefore,
$X_{1},\dots,X_{n}$ form a Markov random field with respect to
$\perp\\!\\!\\!\perp$ and $\mathcal{G}$.

For the other direction, assume the global Markov property holds. Let
$\mathcal{U}\subseteq\mathcal{V}$ be a cutset and let
$\mathcal{V}_{1}(\mathcal{U}),\dots,\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})$
be the components of ${\mathcal{G}}^{\setminus\mathcal{U}}$. We know that
$\mathcal{U}$ separates $\mathcal{V}_{1}(\mathcal{U})$ from
$\mathcal{V}_{2}(\mathcal{U})$, which by the global Markov property implies
$X_{\mathcal{V}_{1}(\mathcal{U})}\perp\\!\\!\\!\perp
X_{\mathcal{V}_{2}(\mathcal{U})}\ |\ X_{\mathcal{U}}$. This can be interpreted
as the conditional mutual independence
$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{2}X_{\mathcal{V}_{i}(\mathcal{U})}\
|\ X_{\mathcal{U}}$. Assume by induction that we know

$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{m}X_{\mathcal{V}_{i}(\mathcal{U})}\
|\ X_{\mathcal{U}}.$ (8)

Note that $\mathcal{U}$ also separates
$\bigcup_{i=1}^{m}\mathcal{V}_{i}(\mathcal{U})$ from
$\mathcal{V}_{m+1}(\mathcal{U})$, which by the global Markov property implies

$X_{\mathcal{V}_{m+1}(\mathcal{U})}\perp\\!\\!\\!\perp\prod_{i=1}^{m}X_{\mathcal{V}_{i}(\mathcal{U})}\
|\ X_{\mathcal{U}}.$

This, together with Equation (8) and the equivalence of parts 1 and 3 in
Proposition 2.4, implies
$\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{m+1}X_{\mathcal{V}_{i}(\mathcal{U})}\
|\ X_{\mathcal{U}}$. By induction, this shows the FCMI

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

Overall, this shows that $X_{1},\dots,X_{n}$ satisfies the cutset property
with respect to $\perp\\!\\!\\!\perp$ and $\mathcal{G}$. ∎

###  2.5 Markov Chains in Separoids

Again, we fix a general separoid $(M,\perp\\!\\!\\!\perp)$.

######  Definition 2.10 (Markov Chain).

Let $n\geq 0$. A sequence of elements $X_{1},\dots,X_{n}$ in $M$ is called a
_Markov Chain_ (with respect to $\perp\\!\\!\\!\perp$) if for all $2\leq i\leq
n$, the following independence holds:

$X_{i}\perp\\!\\!\\!\perp X_{[i-2]}\ |\ X_{i-1}.$

We also write $X_{1}\to X_{2}\to\dots\to X_{n}$ to indicate that the sequence
$X_{1},\dots,X_{n}$ forms a Markov chain.

For $n=0,1$ or $2$, all sequences form a Markov chain. The first interesting
case is $n=3$. The only non-vacuous condition for a Markov chain is then
$X_{3}\perp\\!\\!\\!\perp X_{1}\ |\ X_{2}$.

######  Proposition 2.11 (Characterization of Markov Chains).

Let $X_{1},\dots,X_{n}\in M$. Let
$\mathcal{G}=\big{(}\mathcal{V},\mathcal{E}\big{)}$ be the graph with
$\mathcal{V}=[n]$ and $\mathcal{E}=\big{\\{}\\{i,i+1\\}\mid
i=1,\dots,n-1\big{\\}}$. The following properties are equivalent:

  1. 1.

$X_{1}\to X_{2}\to\dots\to X_{n}$, i.e., the sequence forms a Markov chain;

  2. 2.

$X_{[i-1]}\to X_{i}\to X_{\left[i+1:n\right]}$ for all $i=1,\dots,n-1$;

  3. 3.

$X_{1},\dots,X_{n}$ form a Markov random field with respect to $\mathcal{G}$
and $\perp\\!\\!\\!\perp$.

###### Proof.

Assume 1. To prove 2, let $i\in\\{1,\dots,n-1\\}$. We need to show the
independence

$X_{\left[i+1:n\right]}\perp\\!\\!\\!\perp X_{[i-1]}\ |\ X_{i}.$ (9)

We already know that the independence $X_{i+1}\perp\\!\\!\\!\perp X_{[i-1]}\
|\ X_{i}$ holds. Assume by induction that

$X_{\left[i+1:l\right]}\perp\\!\\!\\!\perp X_{[i-1]}\ |\ X_{i}$ (10)

for some $l\geq i+1$. If $l=n$, then we are done. Otherwise, note that the
independence $X_{l+1}\perp\\!\\!\\!\perp X_{[l-1]}\ |\ X_{l}$ gives us, by
weak union (S4), the property

$X_{l+1}\perp\\!\\!\\!\perp X_{[i-1]}\ |\ X_{i}X_{[i+1:l]}.$ (11)

Contraction (S5) applied to Equations (10) and (11) results in
$X_{\left[i+1:l+1\right]}\perp\\!\\!\\!\perp X_{[i-1]}\ |\ X_{i}$. By
induction, we obtain the result, Equation (9).

Now assume 2. To prove 3, by Proposition 2.9 it is enough to show the cutset
property. For this, let $\mathcal{U}\subseteq\mathcal{G}$ a cutset and
$\mathcal{V}_{1}(\mathcal{U})$, …,
$\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})$ the corresponding
components in ${\mathcal{G}}^{\setminus\mathcal{U}}$. A component in
$\mathcal{G}$ necessarily consists of consecutive elements, and we can thus
assume that they are ordered in such a way that
$v_{1}<\dots<v_{s\left(\mathcal{U}\right)}$ for all vertices
$v_{1}\in\mathcal{V}_{1}(\mathcal{U})$, …,
$v_{s\left(U\right)}\in\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})$.

Now, let $i\in\\{2,\dots,s\left(\mathcal{U}\right)\\}$ be arbitrary. Let
$u\in\mathcal{U}$ be any element such that $v<u<w$ for all
$v\in\bigcup_{k=1}^{i-1}\mathcal{V}_{k}(\mathcal{U})$ and
$w\in\bigcup_{k=i}^{s\left(\mathcal{U}\right)}\mathcal{V}_{k}(\mathcal{U})$;
this clearly exists since otherwise we could merge the components with indices
$i-1$ and $i$. Let $\mathcal{U}_{u-}$ and $\mathcal{U}_{u+}$ be the sets of
elements of $\mathcal{U}$ that are smaller and larger than $u$, respectively.
Then by 2, we obtain

$\big{(}X_{\mathcal{V}_{i}(\mathcal{U})}\cdots
X_{\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})}X_{\mathcal{U}_{u+}}\big{)}\perp\\!\\!\\!\perp\big{(}X_{\mathcal{V}_{1}(\mathcal{U})}\cdots
X_{\mathcal{V}_{i-1}(\mathcal{U})}X_{\mathcal{U}_{u-}}\big{)}\ |\ X_{u}.$

With weak union (S4) applied to both sides, we obtain

$\big{(}X_{\mathcal{V}_{i}(\mathcal{U})}\cdots
X_{\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})}\big{)}\perp\\!\\!\\!\perp\big{(}X_{\mathcal{V}_{1}(\mathcal{U})}\cdots
X_{\mathcal{V}_{i-1}(\mathcal{U})}\big{)}\ |\ X_{\mathcal{U}}.$

Decomposition (S3) applied to the left side gives

$X_{\mathcal{V}_{i}(\mathcal{U})}\perp\\!\\!\\!\perp\big{(}X_{\mathcal{V}_{1}(\mathcal{U})}\cdots
X_{\mathcal{V}_{i-1}(\mathcal{U})}\big{)}\ |\ X_{\mathcal{U}}.$

Since $i$ was arbitrary, by the equivalence of 1 and 2 in Proposition 2.4, we
obtain the FCMI
$\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}}$, showing the cutset property and thus 3.

Since $\\{i-1\\}$ separates $\\{i\\}$ from $\\{1,\dots,i-2\\}$ in
$\mathcal{G}$, the global Markov property shows that 3 implies 1. ∎

##  3 General Information Diagrams and their Properties

Before we come to our generalizations of the main results of Yeung et al.
(2002, 2019) in Section 4, we clarify the generalized setting. In Section 3.1,
we state the generalized Hu theorem, Theorem 3.2, from Lang et al. (2022).
This gives rise to $F$-diagrams for general functions $F$ satisfying the chain
rule.

In Section 3.2, we then state a main technique used in our proofs, Theorem
3.5, which we term _subset determination_. It states that the value of a
region in an $F$-diagram always fully determines the value of all subregions,
including the atomic parts. This result will replace the use of inequalities
in Yeung et al. (2002).

Finally, in Section 3.3, we then introduce the notion of $F$-independence,
which generalizes the characterization of probabilistic conditional
independence in terms of a vanishing of conditional mutual information. We
show that $F$-independence satisfies the separoid axioms, and so all results
from Section 2 apply.

###  3.1 Background: the Generalized Hu Theorem and $F$-Diagrams

We now work towards a presentation of the generalized Hu theorem from Lang et
al. (2022), which generalizes Hu (1962) and the $I$-diagrams from Yeung
(1991).

Recall that an abelian group $G=(G,+,0)$ consists of a set $G$ together with
an addition rule $+:G\times G\to G$ that is associative and commutative, has
$0$ as its neutral element, and has “negative” elements: $g+(-g)=(-g)+g=0$.
Abelian groups generalize the sets of information functions in the context of
classical information theory.

Let $G$ be an abelian group and $M$ a commutative, idempotent monoid. Then an
additive monoid action (or monoid action for short) is a function $.:M\times
G\to G$ for which $\bm{1}\in M$ acts trivially ($\bm{1}.g=g$), that is
associative ($X.(Y.g)=(X\cdot Y).g$) and additive ($X.(g+h)=X.g+X.h$).
Additive monoid actions generalize the conditioning operation of information
functions on random variables.

For a set $\Sigma$, denote by $2^{\Sigma}$ its power set, i.e., the set of its
subsets.

######  Definition 3.1 (($G$-Valued) Measure).

Let $G$ be an abelian group and $\Sigma$ a set.333We only make use of the case
$\Sigma=\widetilde{X}$ as defined below in Equation (13). A _$G$ -valued
measure_ is a function $\mu:2^{\Sigma}\to G$ with the property

$\mu(A_{1}\cup A_{2})=\mu(A_{1})+\mu(A_{2})$

for all disjoint $A_{1},A_{2}\subseteq\Sigma$. One automatically obtains
$\mu(\emptyset)=0$, and $\mu$ turns arbitrary finite disjoint unions into the
corresponding finite sums.

Let $M$ be a commutative, idempotent monoid. Additionally, fix an abelian
group $G$ and an additive monoid action $.:M\times G\to G$.

We now fix elements $X_{1},\dots,X_{n}\in M$, $n\geq 0$. These are the
elements for which we want to obtain a $F$-diagram later on. Since $M$ is
commutative, every product of these elements (of arbitrary order and
multiplicity) can be reordered such that all $X_{i}$ with the same index $i$
are next to each other. Then, since $M$ is idempotent, we can reduce the
product further until each $X_{i}$ appears maximally once. This means that
general products of the $X_{i}$ are of the form

$X_{I}\coloneqq\prod_{i\in I}X_{i}\coloneqq X_{i_{1}}X_{i_{2}}\cdots
X_{i_{q}}$ (12)

for some possibly empty subset
$I=\\{i_{1}<i_{2}<\dots<i_{q}\\}\subseteq[n]=\\{1,\dots,n\\}$. Furthermore, we
have $X_{I}X_{J}\coloneqq X_{I}\cdot X_{J}=X_{I\cup J}$.

##### Definition of $\widetilde{X}$

For each $\emptyset\neq I\subseteq[n]$, we denote by $p_{I}$ an abstract
“atom”. The only property we require of them is to be pairwise different,
i.e., $p_{I}\neq p_{J}$ if $I\neq J$. Then, set $\widetilde{X}$ as the set of
all these atoms:

$\widetilde{X}\coloneqq\widetilde{X}(n)\coloneqq\Big{\\{}p_{I}\ \big{|}\
\emptyset\neq I\subseteq[n]\Big{\\}}.$ (13)

For $i\in[n]$, we denote by
$\widetilde{X}_{i}\coloneqq\big{\\{}p_{I}\in\widetilde{X}\ \ |\ \ i\in
I\big{\\}}$ a set which we can imagine to be depicted by a "circle"
corresponding to the variable $X_{i}$. With
$\widetilde{X}_{I}\coloneqq\bigcup_{i\in I}\widetilde{X}_{i}$ we denote the
union of the “circles” corresponding to the joint variable $X_{I}$. Clearly,
we have $\widetilde{X}=\widetilde{X}_{[n]}$. This is actually the simplest
construction that leads to the $\widetilde{X}_{i}$ being in “general
position”, meaning that for each choice of a set of circles, there is a point
inside all of them and not in any of the others:

$\bigcap_{i\in I}\widetilde{X}_{i}\ \ \setminus\ \ \widetilde{X}_{[n]\setminus
I}=\\{p_{I}\\}$ (14)

In the following, we will also be flexible with our notation. For example, if
we have a commutative, idempotent monoid $M$ and fixed elements $X,Y,Z,W\in
M$, then we can also define

$\widetilde{XYZW}=\widetilde{X}\cup\widetilde{Y}\cup\widetilde{Z}\cup\widetilde{W}$

as above. The atom $p_{XZ}$ would then be characterized by

$\\{p_{XZ}\\}=\Big{(}\widetilde{X}\cap\widetilde{Z}\Big{)}\setminus\Big{(}\widetilde{Y}\cup\widetilde{W}\Big{)}.$

######  Theorem 3.2 (Generalized Hu Theorem, Lang et al. (2022)).

Let $M$ be a commutative, idempotent monoid, $G$ an abelian group, and
$.:M\times G\to G$ an additive monoid action.

Assume $F_{1}:M\to G$ is a function that satisfies the following chain rule:
for all $X,Y\in M$, one has

$F_{1}(XY)=F_{1}(X)+X.F_{1}(Y).$ (15)

Construct $F_{q}:M^{q}\to G$ for $q\geq 2$ inductively by

$F_{q}(Y_{1};\dots;Y_{q})\coloneqq
F_{q-1}(Y_{1};\dots;Y_{q-1})-Y_{q}.F_{q-1}(Y_{1};\dots;Y_{q-1})$ (16)

for all $Y_{1},\dots,Y_{q}\in M$.

Fix elements $X_{1},\dots,X_{n}\in M$, $n\geq 0$. Set
$\widetilde{X}=\widetilde{X}(n)$ as in Equation (13). Then there exists a
$G$-valued measure $\widetilde{F}:2^{\widetilde{X}}\to G$ such that for all
$q\geq 1$ and $J,L_{1},\dots,L_{q}\subseteq[n]$, the following identity holds:

$X_{J}.F_{q}\big{(}X_{L_{1}};\dots;X_{L_{q}}\big{)}=\widetilde{F}\Bigg{(}\bigcap_{k=1}^{q}\widetilde{X}_{L_{k}}\setminus\widetilde{X}_{J}\Bigg{)}.$
(17)

Note that in the preceding theorem, the $G$-valued measure $\widetilde{F}$
depends on the fixed elements $X_{1},\dots,X_{n}$. For ease of notation, we
write every $F_{q}$ simply as $F$. Thus, in an expression of the form
$F(X;Y;Z)$, $F$ is necessarily $F_{3}$. We refer back to Figure 2 for a
depiction of the $F$-diagram that results from the generalized Hu theorem. For
figures that explain how to use Hu’s theorem to visualize identities involving
$F$, we refer to Lang et al. (2022).

######  Notation 3.3.

For all $\emptyset\neq I=\big{\\{}i_{1}<\dots<i_{q}\big{\\}}\subseteq[n]$, we
write

$F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}\coloneqq F\big{(}X_{i_{1}};\dots;X_{i_{q}}\big{)}.$

######  Corollary 3.4.

For all $\emptyset\neq I\subseteq[n]$, one has

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

###### Proof.

This follows directly from Equation (14) and Hu’s Theorem. ∎

###  3.2 Subset Determination

The following theorem, which did not appear in Lang et al. (2022), highlights
a property that we call _subset determination_. This crucial property lies at
the heart of the proofs of the main results in this work.

######  Theorem 3.5 (Subset Determination).

Let $M$ be a commutative, idempotent monoid acting additively on an abelian
group $G$ and $F:M\to G$ be a function satisfying the chain rule Equation
(15). Fix elements $X_{1},\dots,X_{n}\in M$ and let
$\widetilde{X}\coloneqq\widetilde{X}(n)$ be defined as in Equation (13),
resulting in the $G$-valued measure $\widetilde{F}:2^{\widetilde{X}}\to G$
from Theorem 3.2.

Then for any $A\subseteq\widetilde{X}$ and any atom $p_{I}\in A$, one has

$\widetilde{F}(p_{I})=\sum_{K\subseteq
I}(-1)^{\left|K\right|-\left|I\right|}\cdot X_{[n]\setminus
K}.\widetilde{F}(A).$

In particular, if $\widetilde{F}(A)=0$, then $\widetilde{F}(p_{I})=0$ for all
atoms $p_{I}\in A$, and consequently $\widetilde{F}(B)=0$ for all $B\subseteq
A$.

######  Remark 3.6.

It is important to note that this theorem is _not_ true if we work in the
setting of information functions that apply to probability distributions and
restrict our attention to a fixed probability distribution $P$. For example,
the total entropy $I^{P}(XY)$ of a joint variable $XY$ does not determine the
mutual information $I^{P}(X;Y)$ between the two. Nevertheless, we are able to
apply our results also to fixed distribution, as we explain in Appendix D on
_slices_ of $I$-diagrams.

We first need two lemmas:

######  Lemma 3.7.

Assume $p_{L}$ is an atom and $K\subseteq[n]$. Then

$X_{[n]\setminus K}.\widetilde{F}(p_{L})=\begin{cases}\widetilde{F}(p_{L}),\
L\subseteq K,\\\ 0,\ \mathrm{else}.\end{cases}$

###### Proof.

By Corollary 3.4, we have

$X_{[n]\setminus K}.\widetilde{F}(p_{L})=X_{[n]\setminus
K}.\Big{(}X_{[n]\setminus
L}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in
L}X_{l}\big{)}\Big{)}=X_{[n]\setminus(L\cap
K)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l\in
L}X_{l}\big{)}.\\\ $

From this, we immediately see the result for the case $L\subseteq K$. If
$L\nsubseteq K$, then there is $l\in L\setminus K$. Then
$l\in[n]\setminus(L\cap K)$ and consequently, with $Y\coloneqq
X_{\big{(}[n]\setminus{l}\big{)}\setminus(L\cap K)}$:

$X_{[n]\setminus
K}.\widetilde{F}(p_{L})=Y.\Big{(}X_{l}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{l^{\prime}\in
L}X_{l^{\prime}})\Big{)}=Y.\widetilde{F}\Bigg{(}\bigcap_{l^{\prime}\in
L}\widetilde{X}_{l^{\prime}}\setminus\widetilde{X}_{l}\Bigg{)}=Y.\widetilde{F}(\emptyset)=0,$

where we have used Hu’s Theorem 3.2 in the second step. That was to show. ∎

######  Lemma 3.8.

Let $L\subseteq I$ be two sets. Then

$\sum_{K:\ L\subseteq K\subseteq
I}(-1)^{\left|K\right|}=(-1)^{\left|L\right|}\cdot\mathds{1}_{I=L}.$

###### Proof.

We have:

$\displaystyle\sum_{K:\ L\subseteq K\subseteq I}(-1)^{\left|K\right|}$
$\displaystyle=\sum_{k=\left|L\right|}^{\left|I\right|}(-1)^{k}\cdot\left|\Big{\\{}K\
\big{|}\ L\subseteq K\subseteq I,\ \left|K\right|=k\Big{\\}}\right|$
$\displaystyle=\sum_{k=\left|L\right|}^{\left|I\right|}(-1)^{k}\cdot\binom{\left|I\right|-\left|L\right|}{k-\left|L\right|}$
$\displaystyle=(-1)^{\left|L\right|}\cdot\sum_{k=0}^{\left|I\right|-\left|L\right|}\binom{\left|I\right|-\left|L\right|}{k}\cdot
1^{\left|I\right|-\left|L\right|-k}\cdot(-1)^{k}$
$\displaystyle\overset{(\star)}{=}(-1)^{\left|L\right|}\cdot(1-1)^{\left|I\right|-\left|L\right|}$
$\displaystyle=(-1)^{\left|L\right|}\cdot\mathds{1}_{I=L}.$

In $(\star)$, we used the well-known binomial theorem and in the final step
that $0^{0}=1$.444If one is not comfortable with the definition $0^{0}=1$, one
can also directly verify the overall result in the case $L=I$. ∎

###### Proof of Theorem 3.5.

We have

$\displaystyle\sum_{K\subseteq I}(-1)^{\left|K\right|-\left|I\right|}\cdot
X_{[n]\setminus K}.\widetilde{F}(A)$ $\displaystyle=\sum_{K\subseteq
I}(-1)^{\left|K\right|-\left|I\right|}\cdot X_{[n]\setminus
K}.\Bigg{(}\sum_{p_{L}\in A}\widetilde{F}(p_{L})\Bigg{)}$
$\displaystyle=\sum_{p_{L}\in A}(-1)^{-\left|I\right|}\sum_{K\subseteq
I}(-1)^{\left|K\right|}\cdot X_{[n]\setminus K}.\widetilde{F}(p_{L})$
$\displaystyle=\sum_{p_{L}\in A}(-1)^{-\left|I\right|}\cdot\Bigg{(}\sum_{K:\
L\subseteq K\subseteq
I}(-1)^{\left|K\right|}\Bigg{)}\cdot\widetilde{F}(p_{L})$
$\displaystyle\big{(}\mathrm{Lemma}\leavevmode\nobreak\
\ref{lem:atoms_annihilated}\big{)}$ $\displaystyle=\sum_{p_{L}\in
A}(-1)^{-\left|I\right|}\cdot(-1)^{\left|L\right|}\cdot\mathds{1}_{L=I}\cdot\widetilde{F}(p_{L})$
$\displaystyle\big{(}\mathrm{Lemma}\leavevmode\nobreak\
\ref{lem:pure_combinatorics}\big{)}$
$\displaystyle=(-1)^{-\left|I\right|}\cdot(-1)^{\left|I\right|}\cdot\widetilde{F}(p_{I})$
$\displaystyle\big{(}p_{I}\in A\big{)}$ $\displaystyle=\widetilde{F}(p_{I}).$

∎

######  Remark 3.9.

For the special case that $A=\widetilde{X}$, the theorem says that
$F\big{(}X_{[n]}\big{)}$ determines $\widetilde{F}(p_{I})$ for all atoms
$p_{I}\in\widetilde{X}$. If $M$ is generated by the $X_{1},\dots,X_{n}$, this
means that $F\big{(}X_{[n]}\big{)}$ entirely determines $F$. In Appendix A, we
generalize this observation and show that if $\top\in M$ is any so-called _top
element_ , then $F(\top)$ determines $F$ entirely. This leads to a one-to-one
correspondence between elements of $G$ that are _annihilated_ by $\top$ and
functions $F:M\to G$ satisfying the chain rule. We also interpret this result
as the vanishing of a cohomology group of degree one.

###  3.3 $F$-Independence Satisfies the Separoid Axioms

Let $M$ again be a commutative, idempotent monoid acting on an abelian group
$G$, and $F:M\to G$ a function satisfying the chain rule Equation (15). We now
define $F$-independence and show that it satisfies the separoid axioms. This
is the main notion of independence that we will work with in Section 4. The
definition is analogous to the conditional independence relation defined for
general submodular information functions in Steudel et al. (2010).

######  Definition 3.10 ($F$-independence).

We define the relation $\perp\\!\\!\\!\perp_{F}$ on $M^{2}\times M$ by

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

If $X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z$, then $X$ is called
$F$-independent from $Y$ given $Z$.

Our proof of the following proposition, which shows that
$(M,\perp\\!\\!\\!\perp_{F})$ is a separoid, makes extensive use of Hu’s
Theorem 3.2 and the subset determination property, Theorem 3.5.

######  Proposition 3.11.

Let $M$ be a commutative, idempotent monoid acting on the abelian group $G$
and $F:M\to G$ a function satisfying the chain rule Equation (15). Let
$\perp\\!\\!\\!\perp_{F}$ be the $F$-independence relation on $M$ from
Definition 3.10. Then $(M,\perp\\!\\!\\!\perp_{F})$ is a separoid.

###### Proof.

We need to prove the five separoid axioms from Definition 2.1. In proving each
axiom, we will use the elements of $M$ appearing in the formulas as the
“fixed” elements in Hu’s Theorem 3.2, which were in the general formulation
denoted by $X_{1},\dots,X_{n}$.

  1. 1.

Symmetry: for any $X,Y,Z\in M$, we have

$Z.F(X;Y)=\widetilde{F}\big{(}\widetilde{X}\cap\widetilde{Y}\setminus\widetilde{Z}\big{)}=\widetilde{F}\big{(}\widetilde{Y}\cap\widetilde{X}\setminus\widetilde{Z}\big{)}=Z.F(Y;X),$

showing symmetry $X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z\ \
\Longrightarrow\ \ Y\underset{F}{\perp\\!\\!\\!\perp}X\ |\ Z$.

  2. 2.

Redundancy: assume $W\precsim Z$, i.e., $WZ=Z$. It follows

$\widetilde{F}\big{(}\widetilde{W}\setminus\widetilde{Z}\big{)}=Z.F(W)\overset{\text{Eq.\leavevmode\nobreak\
\eqref{eq:cocycle_equationn}}}{=}F(ZW)-F(Z)=F(Z)-F(Z)=0.$

Since
$\widetilde{W}\cap\widetilde{Y}\setminus\widetilde{Z}\subseteq\widetilde{W}\setminus\widetilde{Z}$,
subset determination Theorem 3.5 shows

$Z.F(W;Y)=\widetilde{F}\big{(}\widetilde{W}\cap\widetilde{Y}\setminus\widetilde{Z}\big{)}=0$

and thus $W\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z$.

  3. 3.

Decomposition and weak union: assume $WX\underset{F}{\perp\\!\\!\\!\perp}Y\ |\
Z$. Then we have

$\displaystyle\widetilde{F}\big{(}\widetilde{WX}\cap\widetilde{Y}\setminus\widetilde{Z}\big{)}=Z.F(WX;Y)=0.$

Note that

$\widetilde{X}\cap\widetilde{Y}\setminus\widetilde{Z}\subseteq\widetilde{WX}\cap\widetilde{Y}\setminus\widetilde{Z}\supseteq\widetilde{W}\cap\widetilde{Y}\setminus\widetilde{XZ}.$

Thus, subset determination Theorem 3.5 shows

$\displaystyle
Z.F(X;Y)=\widetilde{F}\big{(}\widetilde{X}\cap\widetilde{Y}\setminus\widetilde{Z}\big{)}=0,$
$\displaystyle(XZ).F(W;Y)=\widetilde{F}\big{(}\widetilde{W}\cap\widetilde{Y}\setminus\widetilde{XZ}\big{)}=0,$

which shows $X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z$ and
$W\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ XZ$ and thus both decomposition and
weak union.

  4. 4.

Contraction: assume $W\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ XZ$ and
$X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z$. We obtain from Hu’s Theorem:

$\displaystyle Z.F(WX;Y)$
$\displaystyle=\widetilde{F}\big{(}\widetilde{WX}\cap\widetilde{Y}\setminus\widetilde{Z}\big{)}$
$\displaystyle=\widetilde{F}\big{(}\widetilde{W}\cap\widetilde{Y}\setminus\widetilde{XZ}\big{)}+\widetilde{F}\big{(}\widetilde{X}\cap\widetilde{Y}\setminus\widetilde{Z}\big{)}$
$\displaystyle=(XZ).F(W;Y)+Z.F(X;Y)$ $\displaystyle=0+0=0.$

Thus, we have proven $WX\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z$. In the
calculation, the second step uses that $\widetilde{F}$ is additive over
disjoint unions.

∎

In the following proposition, we show that $F$-independences are preserved
under conditioning:

######  Proposition 3.12.

Let $(M,\perp\\!\\!\\!\perp_{F})$ be the separoid from above. Let $X,Y,Z,W\in
M$. Then the following implication holds:

$X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ Z\quad\Longrightarrow\quad
X\underset{F}{\perp\\!\\!\\!\perp}Y\ |\ WZ.$

###### Proof.

The claim follows from subset determination Theorem 3.5 and Hu’s Theorem 3.2
by using that
$\widetilde{X}\cap\widetilde{Y}\setminus\widetilde{WZ}\subseteq\widetilde{X}\cap\widetilde{Y}\setminus\widetilde{Z}$.
∎

######  Remark 3.13.

Note that the preceding proposition is incorrect when working in the
probabilistic setting and fixing the probability distribution. For example,
the case of a collider

${X}$${Y}$${W}$

in a Bayesian network shows that it is possible that the probabilistic
independence $X\perp\\!\\!\\!\perp_{P}Y$ is true, while
$X\perp\\!\\!\\!\perp_{P}Y\mid W$ is not. Nevertheless, we will be able to
apply our theory to the probabilistic case in Sections 5 and D.

##  4 Characterizing $F$-Independences and $F$-Markov Random Fields

In this section we generalize the work Yeung et al. (2002) on information
characterizations of (full) conditional mutual independences and Markov random
fields from Shannon entropy to general $F$. The reader may also compare with
Yeung (2008), Chapter 12, which contains the same content as Yeung et al.
(2002) with more explanations.

In Section 4.1, we define conditional mutual $F$-independences and show in
Theorem 4.5 a characterization by the vanishing of a conditional $F$–dual
total correlation and its corresponding atoms. In Section 4.2, with Theorem
4.11, we then generalize this to a characterization of full conditional mutual
$F$-independences. By Proposition 2.9, Markov random fields in a separoid are
equivalently characterized by the cutset property, and thus by a set of full
conditional mutual independences. Thus, the previous results imply a
characterization of $F$-Markov random fields in terms of the $F$-diagram, see
Theorem 4.16. We also specialize this to $F$-Markov chains. Finally, in
Appendix C, we briefly look at Yeung et al. (2019), which builds on Yeung et
al. (2002), and explain which of the results transfer to our generalized
setting. We put this into the appendix since no later results build on this.

Let in this whole section $M$ be a commutative, idempotent monoid acting
additively on an abelian group $G$ and $F:M\to G$ a function satisfying the
chain rule Equation (15). $F$ then induces the $F$-independence relation
$\perp\\!\\!\\!\perp_{F}$, and $(M,\perp\\!\\!\\!\perp_{F})$ becomes a
separoid by Proposition 3.11.

###  4.1 Conditional Mutual $F$-Independences and $F$-Dual Total Correlation

The following definition specializes conditional mutual independences,
Definition 2.3, to the case that the independence relation is given by
$\perp\\!\\!\\!\perp_{F}$:

######  Definition 4.1 (Conditional Mutual $F$-Independence).

Let $X_{1},\dots,X_{n},Y\in M$. If $X_{1},\dots,X_{n}\in M$ are mutually
independent given $Y\in M$ with respect to $\perp\\!\\!\\!\perp_{F}$, then we
write

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

We call this a _conditional mutual $F$-independence_, and we say
$X_{1},\dots,X_{n}$ are mutually $F$-independent given $Y$.

As in Proposition 3.12, we get the following peculiar implication which we
will later use:

######  Proposition 4.2.

Let $X_{1},\dots,X_{n},Y,W\in M$. Then we have the following implication:

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

###### Proof.

This follows immediately from Proposition 3.12 using that conditional mutual
$F$-independences are defined as a combination of conditional pairwise
$F$-independences. ∎

As in Remark 3.13, we mention that the preceding proposition does not hold in
the probabilistic setting when _fixing_ the underlying probability
distribution.

#### Warmup: Characterizing Pairwise Conditional $F$-Independence

######  Proposition 4.3.

Let $X_{1},X_{2},Y\in M$. Then the following are equivalent:

  1. 1.

$X_{1}\underset{F}{\perp\\!\\!\\!\perp}X_{2}\ |\ Y$;

  2. 2.

$Y.F(X_{1}X_{2})=Y.F(X_{1})+Y.F(X_{2})$;

  3. 3.

$Y.F(X_{1}X_{2})=(YX_{2}).F(X_{1})+(YX_{1}).F(X_{2})$;

  4. 4.

$Y.F(X_{1})=(YX_{2}).F(X_{1})$;

  5. 5.

$Y.F(X_{2})=(YX_{1}).F(X_{2})$.

###### Proof.

Using Hu’s Theorem 3.2 with fixed elements $X_{1},X_{2},Y$, we generally have

$\displaystyle Y.F(X_{1}X_{2})$
$\displaystyle=\widetilde{F}\Big{(}\widetilde{X}_{1}\cup\widetilde{X}_{2}\setminus\widetilde{Y}\Big{)}$
$\displaystyle=\widetilde{F}\Big{(}\widetilde{X}_{1}\setminus\widetilde{Y}\Big{)}+\widetilde{F}\Big{(}\widetilde{X}_{2}\setminus\widetilde{Y}\Big{)}-\widetilde{F}\Big{(}\widetilde{X}_{1}\cap\widetilde{X}_{2}\setminus\widetilde{Y}\Big{)}$
$\displaystyle=Y.F(X_{1})+Y.F(X_{2})-Y.F(X_{1};X_{2}).$

This shows the equivalence of 1 and 2. Similarly, one can show the
decomposition

$Y.F(X_{1}X_{2})=(YX_{2}).F(X_{1})+(YX_{1}).F(X_{2})+Y.F(X_{1};X_{2}),$

which shows the equivalence of 1 and 3. Finally, we similarly obtain
decompositions

$\displaystyle Y.F(X_{1})$ $\displaystyle=(YX_{2}).F(X_{1})+Y.F(X_{1};X_{2});$
$\displaystyle Y.F(X_{2})$ $\displaystyle=(YX_{1}).F(X_{2})+Y.F(X_{1};X_{2}).$

The first decomposition shows the equivalence of 1 and 4, and the second the
one of 1 and 5. ∎

Of interest to us are especially properties 2 and 3, which can equivalently be
expressed as the following vanishing conditions:

$\displaystyle Y.\Big{[}F(X_{1})+F(X_{2})-F(X_{1}X_{2})\Big{]}=0;$
$\displaystyle
Y.\Big{[}F(X_{1}X_{2})-\big{(}X_{2}.F(X_{1})+X_{1}.F(X_{2})\big{)}\Big{]}=0.$

The concepts of $F$–total correlation and $F$–dual total correlations provide
natural generalizations of the quantities at the left-hand-sides of these
conditions. These generalize total correlation (Watanabe, 1960) and dual total
correlation (Han, 1978) by replacing Shannon entropy $I$ in the defining
expressions by $F$:

######  Definition 4.4 ($F$–(Dual )Total Correlation).

Let $X_{1},\dots,X_{n}\in M$. Then their _$F$ –total correlation_ is given by

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

Similarly, the _$F$ –dual total correlation_ is given by

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

where $[n]\setminus i\coloneqq[n]\setminus\\{i\\}$. If
$I=\big{\\{}i_{1}<\dots<i_{q}\big{\\}}\subseteq[n]$, then we also write

$\displaystyle TC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}$ $\displaystyle\coloneqq TC_{F}(X_{i_{1}};\dots;X_{i_{q}}),$
$\displaystyle DTC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}$ $\displaystyle\coloneqq DTC_{F}(X_{i_{1}};\dots;X_{i_{q}}).$

Similarly to Proposition 4.3, we want to use $F$–total correlation and
$F$–dual total correlation to characterize conditional _mutual_
$F$-independences. We will focus on the case of $F$–dual total correlation,
which is slightly easier and works in full generality. For the interested
reader, we consider the case of $F$–total correlation in Appendix B. This only
provides a valid characterization in the case that the group $G$ is _torsion-
free_ , as Example B.5 will demonstrate.

#### Characterization using $F$-Dual Total Correlation

Let $X_{1},\dots,X_{n}\in M$. For
$I=\big{\\{}i_{1}<\dots<i_{q}\big{\\}}\subseteq[n]$, we can then consider the
interaction term $F(X_{i_{1}};\dots;X_{i_{q}})$. Recall the notation
$F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}\coloneqq F\big{(}X_{i_{1}};\dots;X_{i_{q}}\big{)}$.

######  Theorem 4.5.

Let $M$ be a commutative, idempotent monoid acting additively on an abelian
group $G$, and $F:M\to G$ 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.DTC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in[n]}X_{i}\big{)}=0$;

  3. 3.

$\big{(}YX_{[n]\setminus
I}\big{)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}=0$ for all $I\subseteq[n]$ with $\left|I\right|\geq 2$;

  4. 4.

$Y.F\big{(}X_{i};X_{[n]\setminus i}\big{)}=0$ for all $i=1,\dots,n$.

###### Proof.

Assume 1. We prove 2 by induction over $n$, with the case $n=2$ corresponding
to the equivalence of 1 and 3 in Proposition 4.3. Let $n\geq 3$. By
Proposition 2.4 we have

$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n-1}X_{i}\
|\ Y,\quad X_{n}\underset{F}{\perp\\!\\!\\!\perp}X_{[n-1]}\ |\ Y.$

The first $F$-independence implies by Proposition 4.2 the following:
$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{n-1}X_{i}\
|\ YX_{n}.$ By induction, first using the pairwise and then the mutual
case,555Similarly to Proposition 4.3, we write the vanishing of the $F$–dual
total correlation as a different equality by bringing a term to the other
side. we then obtain:

$\displaystyle Y.F\big{(}X_{[n]}\big{)}$
$\displaystyle=(YX_{n}).F\big{(}X_{[n-1]}\big{)}+\big{(}YX_{[n-1]}\big{)}.F(X_{n})$
$\displaystyle=\sum_{i=1}^{n-1}\big{(}YX_{n}X_{[n-1]\setminus
i}\big{)}.F(X_{i})+\big{(}YX_{[n-1]}\big{)}.F(X_{n})$
$\displaystyle=Y.\bigg{(}\sum_{i=1}^{n}X_{[n]\setminus i}.F(X_{i})\bigg{)}.$

That shows 2.

For the rest of the proof, write $X_{n+1}\coloneqq Y$ and assume that
$X_{1},\dots,X_{n+1}$ are the fixed elements in Hu’s Theorem 3.2.

Now assume 2. Note that

$\displaystyle
0=Y.DTC_{F}\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in[n]}X_{i}\big{)}$
$\displaystyle=X_{n+1}.F\big{(}X_{[n]}\big{)}-\sum_{i=1}^{n}X_{[n+1]\setminus
i}.F(X_{i})$
$\displaystyle=\widetilde{F}\Big{(}\widetilde{X}_{[n]}\setminus\widetilde{X}_{n+1}\Big{)}-\sum_{i=1}^{n}\widetilde{F}(p_{i})$
$\displaystyle=\widetilde{F}\Big{(}\big{\\{}p_{I}\mid
I\subseteq[n],\left|I\right|\geq 2\big{\\}}\Big{)},$

where we used Corollary 3.4 in the second step. Let $I\subseteq[n]$ with
$\left|I\right|\geq 2$. Then, subset determination Theorem 3.5 and the same
corollary again imply:

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

That is precisely 3.

Now, assume 3. To prove 4, for symmetry reasons it is enough to show that
$Y.F\big{(}X_{n},X_{[n-1]}\big{)}=0$. We have

$\displaystyle Y.F\big{(}X_{n};X_{[n-1]}\big{)}$
$\displaystyle=X_{n+1}.F\big{(}X_{n};X_{[n-1]}\big{)}$
$\displaystyle=\widetilde{F}\Big{(}\widetilde{X}_{n}\cap\widetilde{X}_{[n-1]}\setminus\widetilde{X}_{n+1}\Big{)}$
$\displaystyle=\sum_{\begin{subarray}{c}I\subseteq[n]:\ n\in I,\\\
I\cap[n-1]\neq\emptyset\end{subarray}}\widetilde{F}(p_{I})$
$\displaystyle=\sum_{\begin{subarray}{c}I\subseteq[n]:\ n\in I,\\\
I\cap[n-1]\neq\emptyset\end{subarray}}X_{[n+1]\setminus
I}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in I}X_{i}\big{)}$
$\displaystyle=\sum_{\begin{subarray}{c}I\subseteq[n]:\ n\in I,\\\
I\cap[n-1]\neq\emptyset\end{subarray}}\big{(}YX_{[n]\setminus
I}\big{)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{i}\big{)}$ $\displaystyle=0,$

where the fourth step used Corollary 3.4. The last step follows since for all
$I$ over which we sum, we necessarily have $\left|I\right|\geq 2$.

Assuming 4, 1 follows immediately by the definitions of conditional mutual and
pairwise $F$-independences. ∎

###  4.2 Full Conditional Mutual $F$-Independences

We now build on Section 4.1. We will consider mutual $F$-independences of
variables that are _themselves_ products of several variables. The main result
of this section, Theorem 4.11, will generalize the equivalence between
properties 1 and 3 in Theorem 4.5.

Fix $n\geq 0$ and $X_{1},\dots,X_{n}\in M$. This gives rise to a set
$\widetilde{X}=\widetilde{X}(n)$ of $2^{n}-1$ atoms according to Equation (13)
and a $G$-valued measure $\widetilde{F}:2^{\widetilde{X}}\to G$ according to
Hu’s Theorem 3.2.

In the following, if $W_{i}$ are sets indexed with $i\in I$, then $W_{I}$
denotes $\bigcup_{i\in I}W_{i}$. We now define $F$-FCMIs, specializing the
notion of FCMIs from Definition 2.7 to the setting with the independence
relation given as $\perp\\!\\!\\!\perp_{F}$. We will, however, first define
the notion of a conditional partition, since this will prove valuable when
studing the effect of $F$-FCMIs on $F$-diagrams:

######  Definition 4.6 (Conditional Partition).

Let $q\geq 1$, $L_{i}\subseteq[n]$ for all $i\in[q]$ and $J\subseteq[n]$. Set
$L\coloneqq L_{[q]}=\bigcup_{i=1}^{q}L_{i}$. Assume that the $L_{i}$ and $J$
are all pairwise disjoint and cover $[n]$. Then the family
$K\coloneqq\big{(}J,L_{i},1\leq i\leq q\big{)}$ is called a _conditional
partition_ of $[n]$.666We allow $J$ and the $L_{i}$ to be empty, different
from usual partitions.

######  Definition 4.7 (Full Conditional Mutual $F$-Independence ($F$-FCMI)).

Let $K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ be a conditional partition with
$q\geq 2$. Then an FCMI of the form

$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$ (18)

is called a full conditional mutual $F$-independence (with respect to the
previously fixed elements $X_{1},\dots,X_{n}$) — or $F$-FCMI for short. If
this $F$-FCMI holds, then we also say that the conditional partition
$K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ _induces_ an $F$-FCMI (with respect to
the previously fixed elements $X_{1},\dots,X_{n}$).

######  Definition 4.8 (Image of a Conditional Partition).

Let $K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ be a conditional partition of
$[n]$ with $q\geq 2$. Then its image is defined as

$\operatorname{Im}(K)\coloneqq\bigg{\\{}p_{W}\in\widetilde{X}(n)\ \Big{|}\
\exists I\subseteq[q],\left|I\right|\geq 2,\forall i\in I\ \
\exists\emptyset\neq W_{i}\subseteq L_{i}:W=W_{I}=\bigcup_{i\in
I}W_{i}\bigg{\\}},$

i.e., as a certain set of atoms in $\widetilde{X}(n)$.

######  Lemma 4.9.

Let $q\geq 1$ and $K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ a conditional
partition of $[n]$. Let $\emptyset\neq I\subseteq[q]$. Then the equality

$A_{I}\coloneqq\bigcap_{i\in I}\widetilde{X}_{L_{i}}\ \setminus\
\widetilde{X}_{J\cup L\setminus L_{I}}=\bigg{\\{}p_{W}\in\widetilde{X}(n)\
\Big{|}\ \forall i\in I\ \exists\emptyset\neq W_{i}\subseteq
L_{i}:W=W_{I}=\bigcup_{i\in I}W_{i}\bigg{\\}}$

holds. Furthermore, if $q\geq 2$, then we have
$\operatorname{Im}(K)=\bigcup_{I\subseteq[q]:\ \left|I\right|\geq 2}A_{I}$.

###### Proof.

Let $p_{W}$ be an atom, where by definition $\emptyset\neq W\subseteq[n]=J\cup
L$. Then we have

$\displaystyle p_{W}\in A_{I}\quad$
$\displaystyle\Longleftrightarrow\quad\forall i\in I\ \ \exists l\in
L_{i}:p_{W}\in\widetilde{X}_{l}\ \ \wedge\ \ \forall l\in J\cup L\setminus
L_{I}:p_{W}\notin\widetilde{X}_{l}$
$\displaystyle\Longleftrightarrow\quad\forall i\in I:\emptyset\neq W\cap
L_{i}\ \ \wedge\ \ W\cap\big{(}J\cup L\setminus L_{I}\big{)}=\emptyset.$

Now, assume $p_{W}\in A_{I}$ and let $W_{i}\coloneqq W\cap L_{i}\neq\emptyset$
for $i\in I$. Then from the preceding characterization, we obtain:

$W=W\cap(J\cup L)=W\cap L_{I}=W\cap\bigcup_{i\in I}L_{i}=\bigcup_{i\in
I}W_{i}=W_{I}$

and thus $p_{W}=p_{W_{I}}$ is in the set at the right-hand-side.

If, vice versa, $p_{W}=p_{W_{I}}$ is of the stated form of the set at the
right-hand-side, then $W\cap L_{i}=W_{i}\neq\emptyset$ for all $i\in I$ and
$W\cap\big{(}J\cup L\setminus L_{I}\big{)}=\emptyset$, and thus $p_{W}\in
A_{I}$.

The last statement follows immediately from the definition of
$\operatorname{Im}(K)$ and what we just showed. ∎

Before we state the following proposition, we remind of the fact that, by
Corollary 3.4, we have

$F\big{(}X_{[n]}\big{)}=\widetilde{F}\big{(}\widetilde{X}\big{)}=\sum_{p_{I}\in\widetilde{X}}\widetilde{F}(p_{I})=\sum_{\emptyset\neq
I\subseteq[n]}X_{[n]\setminus
I}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in I}X_{i}\big{)}.$

The following proposition generalizes this to the case that the left-hand-side
is itself a “term of higher degree”:

######  Proposition 4.10.

Let $q\geq 1$, and let $L_{1},\dots,L_{q}\subseteq[n]$ be pairwise disjoint
sets. For any $\emptyset\neq I\subseteq[q]$, we have

$F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{L_{i}}\big{)}=\sum_{\begin{subarray}{c}(W_{i})_{i\in I}:\\\ \forall i:\
\emptyset\neq W_{i}\subseteq L_{i}\end{subarray}}X_{L_{I}\setminus
W_{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{w\in
W_{I}}X_{w}\big{)}.$

###### Proof.

Assume without loss of generality that $I=[q]$ and $L_{I}=[n]$. Then, applying
Hu’s Theorem 3.2 and Lemma 4.9, we obtain:

$F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{L_{i}}\big{)}=\widetilde{F}\Bigg{(}\bigcap_{i\in
I}\widetilde{X}_{L_{i}}\Bigg{)}=\sum_{\begin{subarray}{c}\emptyset\neq
W\subseteq L_{I}:\\\ p_{W}\in\bigcap_{i\in
I}\widetilde{X}_{L_{i}}\end{subarray}}\widetilde{F}(p_{W})=\sum_{\begin{subarray}{c}(W_{i})_{i\in
I}:\\\ \forall i:\ \emptyset\neq W_{i}\subseteq
L_{i}\end{subarray}}\widetilde{F}(p_{W_{I}}).$

The result follows from $\widetilde{F}(p_{W_{I}})=X_{L_{I}\setminus
W_{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{w\in
W_{I}}X_{w}\big{)}$, see Corollary 3.4. ∎

The following Theorem generalizes Theorem 5 of Yeung et al. (2002). We
illustrate it in Figures 4 and 5. The reader may also compare with Figures 1
and 3 from the introduction, which illustrates the effect of simple $F$-FCMIs
for the case that $F=I$ and general $F$, respectively. In the first of those
figures, the FCMIs come from the graph-structure of a Markov random field.

Figure 4: In this illustration, we visualize the full conditional mutual
$F$-independence ($F$-FCMI)
$X_{L_{1}}\underset{F}{\perp\\!\\!\\!\perp}X_{L_{2}}\ |\ X_{J}$ for the case
$n=4$, $J=\\{4\\}$, $L_{1}=\\{1\\}$, and $L_{2}=\\{2,3\\}$. The independence
is by Hu’s Theorem 3.2 given by
$\widetilde{F}\big{(}\widetilde{X}_{L_{1}}\cap\widetilde{X}_{L_{2}}\setminus\widetilde{X}_{J}\big{)}=X_{J}.F(X_{L_{1}};X_{L_{2}})=0$.
That is, $\widetilde{F}$ vanishes on the gray region. Subset determination
Theorem 3.5 results in $\widetilde{F}$ vanishing even on all the atoms
_within_ that region — namely $p_{12},p_{123}$, and $p_{13}$. Defining the
conditional partition $K=\big{(}J,L_{1},L_{2}\big{)}$, these atoms are
precisely the elements in $\operatorname{Im}(K)$, thus confirming the
characterization of $F$-FCMIs in terms of $\widetilde{F}$ given in Theorem
4.11.

######  Theorem 4.11.

Let $M$ be a commutative, idempotent monoid acting additively on an abelian
group $G$ and $F:M\to G$ a function satisfying the chain rule Equation (15).
We assume fixed elements $X_{1},\dots,X_{n}\in M$, giving rise to a $G$-valued
measure $\widetilde{F}:2^{\widetilde{X}}\to G$ according to Hu’s Theorem 3.2.

Let $K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ be a conditional partition of
$[n]$ with $q\geq 2$. Set $L\coloneqq L_{[q]}$. Then the following properties
are equivalent:

  1. 1.

$K$ induces an $F$-FCMI with respect to $X_{1},\dots,X_{n}$, i.e.
$F:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$;

  2. 2.

for all $I\subseteq[q]$ with $\left|I\right|\geq 2$: $\big{(}X_{J\cup
L\setminus
L_{I}}\big{)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{L_{i}}\big{)}=0$;

  3. 3.

for all $I\subseteq[q]$ with $\left|I\right|\geq 2$ and all $(W_{i})_{i\in I}$
with $\emptyset\neq W_{i}\subseteq L_{i}$ for all $i\in I$, we have $X_{J\cup
L\setminus W_{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{w\in
W_{I}}X_{w}\big{)}=0$;

  4. 4.

$\widetilde{F}(p_{W})=0$ for all $p_{W}\in\operatorname{Im}(K)$.

###### Proof.

That 1 and 2 are equivalent follows immediately from the equivalence of
properties 1 and 3 in Theorem 4.5. In doing so, $q$ replaces $n$, $X_{J}$
replaces $Y$, and $X_{L_{i}}$ replaces $X_{i}$.

3 immediately implies 2 by Proposition 4.10 and observing that $X_{J\cup
L\setminus L_{I}}\cdot X_{L_{I}\setminus W_{I}}=X_{J\cup L\setminus W_{I}}$. 3
and 4 are clearly seen to be equivalent using the definition of
$\operatorname{Im}(K)$ and the fact that

$X_{J\cup L\setminus
W_{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{w\in
W_{I}}X_{w}\big{)}=X_{[n]\setminus
W_{I}}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{w\in
W_{I}}X_{w}\big{)}=\widetilde{F}(p_{W_{I}}).$

We used $J\cup L=[n]$ in the first step and Corollary 3.4 in the second.

Finally, we need to see that 2 implies 4. Let $p_{W}\in\operatorname{Im}(K)$.
Then by Lemma 4.9, there is a set $I\subseteq[q]$ with $\left|I\right|\geq 2$
such that $p_{W}\in A_{I}=\bigcap_{i\in
I}\widetilde{X}_{L_{i}}\setminus\widetilde{X}_{J\cup L\setminus L_{I}}$. Then,
using Hu’s Theorem 3.2 and property 2, we obtain
$\widetilde{F}\big{(}A_{I}\big{)}=\big{(}X_{J\cup L\setminus
L_{I}}\big{)}.F\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{i\in
I}X_{L_{i}}\big{)}=0$. By subset determination, Theorem 3.5, this results in
particular in $\widetilde{F}(p_{W})=0$, and we are done. ∎

Figure 5: This figure visualizes the full conditional mutual $F$-independence
($F$-FCMI) of $X_{L_{1}}$, $X_{L_{2}}$ and $X_{L_{3}}$ for the case $n=4$,
$L_{1}=\\{1\\}$, $L_{2}=\\{2,3\\}$, and $L_{3}=\\{4\\}$. Here, the conditional
variable is trivial, corresponding to $J=\emptyset$. By the characterization
of $F$-FCMIs, Theorem 4.11, $\widetilde{F}$ vanishes on all atoms in the gray
region. This leads to a degeneracy of the $F$-diagram, which can then be
depicted on the small set of atoms at the right-hand-side of the figure.

######  Remark 4.12.

If we replace property 1 in the preceding theorem by simply stating the
independence relation — without naming this an $F$-FCMI — then properties 1,
2, and 3 are also equivalent without assuming $L\cup J=[n]$. This corresponds
to conditional mutual $F$-independences that are not _full_. The reason is
that $n$ does not even appear in those statements, and so we can always
relabel the elements in $J\cup L$ to be equal to $[n^{\prime}]$ for some
$n^{\prime}<n$. However, for the equivalence to statement $4$ we need the
property $L\cup J=[n]$.

###  4.3 $F$-Markov Random Fields and $F$-Markov Chains

In this section, we characterize Markov random fields with respect to
$\perp\\!\\!\\!\perp_{F}$ and a graph $\mathcal{G}$ in terms of the
$F$-diagram. Then we specialize this to a characterization of Markov chains.
As in the previous subsection, fix elements $X_{1},\dots,X_{n}\in M$, giving
rise to a $G$-valued measure $\widetilde{F}:2^{\widetilde{X}}\to G$ by Hu’s
Theorem 3.2. Additionally, we now fix a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with vertex set $\mathcal{V}=[n]$, see
Definition 2.5.

######  Terminology 4.13 ($F$-Markov Random Field, $F$-Markov Chain).

$X_{1},\dots,X_{n}$ are said to form an $F$-Markov random field with respect
to $\mathcal{G}$ if they form a Markov random field with respect to
$\perp\\!\\!\\!\perp_{F}$ and $\mathcal{G}$, see Definition 2.6. Similarly,
$X_{1},\dots,X_{n}$ are said to form an $F$-Markov chain if they form a Markov
chain with respect to $\perp\\!\\!\\!\perp_{F}$, see Definition 2.10.

We now define the notions of connected and disconnected atoms with respect
$\mathcal{G}$. They are identical to the notions of type I and type II atoms
defined in Yeung et al. (2002).

######  Definition 4.14 (Connected and Disconnected Atoms).

For $\mathcal{W}\subseteq[n]$, the corresponding atom
$p_{\mathcal{W}}\in\widetilde{X}$ is called _disconnected_ with respect to
$\mathcal{G}$ if $\mathcal{V}\setminus\mathcal{W}=[n]\setminus\mathcal{W}$ is
a cutset, i.e., if $\mathcal{W}$ is disconnected as a vertex set in
${\mathcal{G}}^{\setminus\big{(}[n]\setminus\mathcal{W}\big{)}}$. Otherwise,
$p_{\mathcal{W}}$ is called _connected_ (with respect to $\mathcal{G}$).

######  Lemma 4.15.

Let $\mathcal{U}$ a cutset for $\mathcal{G}$. Let
$\mathcal{V}_{i}(\mathcal{U})$, $1\leq i\leq s\left(\mathcal{U}\right)$ be the
corresponding components 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.
Then all $p_{\mathcal{W}}\in\operatorname{Im}(K)$ are disconnected.

###### Proof.

Let $p_{\mathcal{W}}\in\operatorname{Im}(K)$. There exists
$I\subseteq[s\left(\mathcal{U}\right)]$ with $\left|I\right|\geq 2$ and
$\emptyset\neq\mathcal{W}_{i}\subseteq\mathcal{V}_{i}(\mathcal{U})$ for all
$i\in I$ such that $\mathcal{W}=\mathcal{W}_{I}=\bigcup_{i\in
I}\mathcal{W}_{i}$. Now, let $i\neq j\in I$ and
$w_{i}\in\mathcal{W}_{i}\subseteq\mathcal{V}_{i}(\mathcal{U})$ and
$w_{j}\in\mathcal{W}_{j}\subseteq\mathcal{V}_{j}(\mathcal{U})$. Since
$\mathcal{V}_{i}(\mathcal{U})$ and $\mathcal{V}_{j}(\mathcal{U})$ are
components of ${\mathcal{G}}^{\setminus\mathcal{U}}$, there is no walk
connecting $w_{i}$ and $w_{j}$ in ${\mathcal{G}}^{\setminus\mathcal{U}}$.
Since $\mathcal{U}\subseteq\mathcal{V}\setminus\mathcal{W}_{I}$, there can
also be no such walk in
${\mathcal{G}}^{\setminus(\mathcal{V}\setminus\mathcal{W}_{I})}$. This shows
that $\mathcal{V}\setminus\mathcal{W}_{I}$ is a cutset, and thus
$p_{\mathcal{W}}=p_{\mathcal{W}_{I}}$ is disconnected. ∎

The proof of the following characterization of $F$-Markov random fields is
similar to the one given in Yeung et al. (2002), Theorem 8, for the special
case of probabilistic Markov random fields.

######  Theorem 4.16 ($F$-Markov Random Field Characterization).

Let $M$ be a commutative, idempotent monoid acting additively on an abelian
group $G$, and $F:M\to G$ a function satisfying the chain rule Equation (15).
Additionally, fix elements $X_{1},\dots,X_{n}$ giving rise to
$\widetilde{F}:2^{\widetilde{X}}\to G$ and a graph $\mathcal{G}$ with vertex
set $[n]$. Then the following statements are equivalent:

  * •

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

  * •

$\widetilde{F}(p_{\mathcal{W}})=0$ for all disconnected atoms
$p_{\mathcal{W}}\in\widetilde{X}$.

###### Proof.

Assume that $X_{1},\dots,X_{n}$ form an $F$-Markov random field with respect
to $\mathcal{G}$. Let $p_{\mathcal{W}}$ be a disconnected atom. We need to
show $\widetilde{F}(p_{\mathcal{W}})=0$.

Define $\mathcal{U}\coloneqq\mathcal{V}\setminus\mathcal{W}$. By assumption of
$\mathcal{W}$ being disconnected, $\mathcal{U}$ is a cutset. Thus,
$s\left(\mathcal{U}\right)\geq 2$ and we have components
$\mathcal{V}_{1}(\mathcal{U}),\dots,\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})$
in ${\mathcal{G}}^{\setminus\mathcal{U}}$. Since $X_{1},\dots,X_{n}$ form an
$F$-Markov random field with respect to $\mathcal{G}$, we obtain by
Proposition 2.9 the $F$-independence

$F:\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}}.$

Now, notice that this is precisely the $F$-FCMI corresponding to the
conditional partition $K=\big{(}\mathcal{U},\mathcal{V}_{i}(\mathcal{U}),1\leq
i\leq s\left(\mathcal{U}\right)\big{)}$. By Theorem 4.11,
$\widetilde{F}(p_{\mathcal{W}^{\prime}})=0$ for all atoms
$p_{\mathcal{W}^{\prime}}\in\operatorname{Im}(K)$. Now, notice that
$\bigcup_{i=1}^{s\left(\mathcal{U}\right)}\mathcal{V}_{i}(\mathcal{U})=\mathcal{V}\setminus\mathcal{U}=\mathcal{W}$,
which, due to $s\left(\mathcal{U}\right)\geq 2$ and
$\mathcal{V}_{i}(\mathcal{U})\neq\emptyset$, shows that
$p_{\mathcal{W}}\in\operatorname{Im}(K)$. This shows
$\widetilde{F}(p_{\mathcal{W}})=0$, and we are done.

For the other direction, assume that $\widetilde{F}$ vanishes on all
disconnected atoms. Now, let $\mathcal{U}\subseteq\mathcal{V}$ be a cutset,
with components
$\mathcal{V}_{1}(\mathcal{U}),\dots,\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})$
of ${\mathcal{G}}^{\setminus\mathcal{U}}$. By Proposition 2.9, we need to show
the $F$-independence

$F:\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}}.$

This is the $F$-FCMI corresponding to the conditional partition
$K=\big{(}\mathcal{U},\mathcal{V}_{i}(\mathcal{U}\big{)},1\leq i\leq
s\left(U\right))$. Thus, by Theorem 4.11, we need to show that
$\widetilde{F}(p_{\mathcal{W}})=0$ for all
$p_{\mathcal{W}}\in\operatorname{Im}(K)$. Since all
$p_{\mathcal{W}}\in\operatorname{Im}(K)$ are disconnected by Lemma 4.15, this
follows from assuming that $\widetilde{F}$ vanishes on all disconnected atoms.
∎

We refer back to Figure 1 for a visualization of how $F$-diagrams of
$F$-Markov random fields look like. That visualization focused on $I$-Markov
random fields, but is entirely correct also in our general case, as the
preceding theorem shows.

######  Corollary 4.17.

With all notation as above, the following two statements are equivalent:

  * •

$X_{1},\dots,X_{n}$ form an $F$-Markov chain.

  * •

$\widetilde{F}(p_{\mathcal{W}})=0$ for all $\mathcal{W}\subseteq[n]$ that do
_not_ only contain consecutive numbers.

###### Proof.

For the proof, we specialize to the graph
$\mathcal{G}=\big{(}\mathcal{V},\mathcal{E}\big{)}$ with $\mathcal{V}=[n]$ and
$\mathcal{E}=\big{\\{}\\{i,i+1\\}\mid i=1,\dots,n-1\big{\\}}$, so
$\mathcal{G}$ is intuitively a chain. Then from Proposition 2.11 we know that
the first statement is equivalent to $X_{1},\dots,X_{n}$ forming an $F$-Markov
random field with respect to $\mathcal{G}$. Since the disconnected atoms
$p_{\mathcal{W}}$ with respect to $\mathcal{G}$ are precisely those where
$\mathcal{W}$ does not only consist of consecutive numbers, the result follows
from Theorem 4.16. ∎

Figure 6: If elements $X_{1},\dots,X_{n}\in M$ form an $F$-Markov chain, then
many atoms in the $F$-diagram disappear by Corollary 4.17. The only atoms that
remain are those corresponding to “intervals” in $[n]$. This leads to a fan-
like structure of the $F$-diagram, as visualized here for $n=3$ and $n=5$.

The effect of the preceding corollary on $F$-diagrams is visualized in Figure
6.

######  Corollary 4.18.

Assume $X_{1},\dots,X_{n}$ form an $F$-Markov Chain. Then for all
$I,J\subseteq[n]$ with $\emptyset\neq
I=\big{\\{}i_{1}<i_{2}<\dots<i_{q}\big{\\}}$, the following equality holds:

$X_{J}.F\big{(}X_{i_{1}};X_{i_{2}};\dots;X_{i_{q}}\big{)}=X_{J}.F\big{(}X_{i_{1}};X_{i_{q}}\big{)}.$

###### Proof.

We can without loss of generality assume $X_{J}=\bm{1}$. Using Hu’s Theorem
3.2, we obtain

$\displaystyle F(X_{i_{1}};\dots;X_{i_{q}})$
$\displaystyle=\widetilde{F}\Bigg{(}\bigcap_{k=1}^{q}\widetilde{X}_{i_{k}}\Bigg{)}=\sum_{L:\
i_{1},\dots,i_{q}\in L}\widetilde{F}(p_{L})\overset{(\star)}{=}\sum_{L:\
i_{1},i_{q}\in L}\widetilde{F}(p_{L})$
$\displaystyle=\widetilde{F}\Big{(}\widetilde{X}_{i_{1}}\cap\widetilde{X}_{i_{q}}\Big{)}=F(X_{i_{1}};X_{i_{q}}).$

In $(\star)$, we used Corollary 4.17: both sums are equal since for all
summands where $L$ does not contain the whole “interval”
$\left[i_{1}:i_{q}\right]$, we have $\widetilde{F}(p_{L})=0$. ∎

##  5 Probabilistic Independences and Markov Random Fields

In this section, we specialize the results from Section 4 to the probabilistic
setting. We start in Section 5.1 with explaining the preliminaries on
probabilistic conditional independences and monoids of equivalence classes of
discrete random variables. We obtain a separoid of discrete random variables,
which means we can use the concepts and results from Section 2.

Since we want to study probabilistic FCMIs and Markov random fields, we want
to restrict our information measures — e.g., Shannon entropy, Kullback-Leibler
divergence, and cross-entropy — to probability distributions satisfying these
properties. However, to be able to work in the setting of Section 3 of a
general function $F:M\to G$, we need a monoid action, which in the
probabilistic case involves conditional probability distributions. We thus
need to make sure that properties of distributions such as “forms a Markov
random field” are preserved under conditioning. We prove this for several
properties in Section 5.2.

In Section 5.3 we briefly study a general class of information functions that
satisfy the chain rule, and motivate the case of higher-order cross-entropy
and Kullback-Leibler divergence by a connection to the cluster cross-entropy
from Cocco and Monasson (2012). Building on Section 5.2, in Section 5.4, we
restrict general information functions to stable properties like “forms a
Markov random field” and show that this preserves the monoid action and the
chain rule. In Theorem 5.14, we then recover the notion of a Markov random
field with respect to restricted information functions, providing examples for
the $F$-Markov random fields studied in Section 4. In Section 5.5 we then
specialize to the case of Kullback-Leibler Markov chains with fixed transition
probabilities between time-steps, reminiscent of the physical laws. This leads
to Theorem 5.15 and Corollary 5.16, where we interpret a weak version of the
second law of thermodynamics in terms of a degeneracy of Kullback-Leibler
diagrams.

The results in Yeung et al. (2002) of $I$-diagram characterizations of FCMIs
and Markov random fields focus on _fixed_ probability distributions, thus only
looking at what we will call a _slice_ of the $I$-diagram. This does not
directly correspond to our supposed generalizations; after all, they always
involve a monoid action, and thus let the probability distributions
unspecified in the probabilistic case. In Appendix D, we demonstrate that this
is not a problem by showing that our Theorems 4.11 and 4.16 actually imply the
main results in Yeung et al. (2002). This validates the claim that our results
are indeed generalizations.

In this whole section, let $\Omega$ be a finite, discrete sample space, with
the probability distribution _not_ yet fixed.

###  5.1 Background: Probabilistic Independence and Monoids of Random
Variables

We look at finite, discrete random variables $X:\Omega\to E_{X}$; that $X$ is
finite and discrete means that $E_{X}$ is finite and discrete. We write the
measurable space of probability mass functions $P:\Omega\to[0,1]$ as
$\Delta(\Omega)$. A mass function $P:\Omega\to[0,1]$ also induces a
probability distribution $P:2^{\Omega}\to[0,1]$ by
$P(A)\coloneqq\sum_{\omega\in A}P(\omega)$, which we denote by abuse of
notation with the same symbol. Whenever we write “discrete”, we actually mean
_finite_ and discrete.

For a probability distribution $P\in\Delta(\Omega)$, we write the
distributional law with respect to a discrete random variable $X:\Omega\to
E_{X}$ as

${P}_{X}:E_{X}\to[0,1],\quad{P}_{X}(x)\coloneqq
P\big{(}X^{-1}(x)\big{)}=\sum_{\omega\in X^{-1}(x)}P(\omega).$

This is also a probability distribution. Furthermore, for $x\in E_{X}$ with
$P_{X}(x)\neq 0$, we define the conditional distribution
${P}|_{X=x}\in\Delta(\Omega)$ by

${P}|_{X=x}:\Omega\to[0,1],\quad{P}|_{X=x}(\omega)\coloneqq\frac{P\big{(}\\{\omega\\}\cap
X^{-1}(x)\big{)}}{{P}_{X}(x)}.$

If $X:\Omega\to E_{X}$ and $Y:\Omega\to E_{Y}$ are two discrete random
variables, then their joint variable is given by

$XY:\Omega\to E_{X}\times
E_{Y},\quad\omega\mapsto\big{(}X(\omega),Y(\omega)\big{)}.$

If the random variable is clear from the context, we write $P(x)$ for
${P}_{X}(x)$. Similarly, we may write $P(x\mid y)$ for
${\big{(}{P}|_{Y=y}\big{)}}_{X}(x)$ and $P(x,y)$ for ${P}_{XY}(x,y)$.

######  Definition 5.1 (Probabilistic Conditional Independence).

Let $X,Y,Z$ be discrete random variables on $\Omega$ and $P:\Omega\to[0,1]$ a
probability distribution. Then $X$ and $Y$ are said to be _$P$ -independent_
given $Z$, written

$X\underset{P}{\perp\\!\\!\\!\perp}Y\ |\ Z,$

if for all $(x,y,z)\in E_{X}\times E_{Y}\times E_{Z}$, the joint distribution
decomposes as follows:888If $P(z)=0$, then $P(x\mid z)$ is not defined. But
then $P(x,y,z)=0$ and $P(y,z)=0$, so we can simply define the right-hand-side
of the equation as zero.

$P(x,y,z)=P(x\mid z)\cdot P(y,z).$ (19)

Equivalently, for all $z\in E_{Z}$ with $P(z)\neq 0$ one has

$P(x,y\mid z)=P(x\mid z)\cdot P(y\mid z).$

Equivalently, for all $y,z\in E_{Y}\times E_{Z}$ with $P(y,z)\neq 0$ one has

$P(x\mid y,z)=P(x\mid z).$

To impose the structure of a monoid on collections of discrete random
variables, we need to identify _equivalent_ random variables. For two random
variables $X,Y$ on $\Omega$, we define $X\precsim Y$ if $X$ is a deterministic
function of $Y$, meaning there exists a function $f_{XY}:E_{Y}\to E_{X}$ such
that $X=f_{XY}\circ Y$, i.e., $X(\omega)=f_{XY}(Y(\omega))$ for all
$\omega\in\Omega$. We write $X\sim Y$ if $X\precsim Y$ and $Y\precsim X$,
which is an equivalence relation. If $X^{\prime}\sim X$, $Y^{\prime}\sim Y$,
$Z^{\prime}\sim Z$, and $P\in\Delta(\Omega)$, then

$X\underset{P}{\perp\\!\\!\\!\perp}Y\ |\ Z\quad\Longleftrightarrow\quad
X^{\prime}\underset{P}{\perp\\!\\!\\!\perp}Y^{\prime}\ |\ Z^{\prime},$

see, for example, Dawid (2001), Section 6.2. Consequently, we can replace
random variables by their equivalence classes. In the following, we will then
write $X$ for both the random variable and its equivalence class, and we
denote by $\mathop{\scalebox{1.5}{\raisebox{-0.86108pt}{$\ast$}}}$ the trivial
measurable space that contains precisely one element
$\ast\in\mathop{\scalebox{1.5}{\raisebox{-0.86108pt}{$\ast$}}}$. One obtains
the following:

######  Proposition 5.2 (The Monoid of Random Variables).

Equivalence classes of random variables, together with the multiplication
given by the joint operation $X\cdot Y\coloneqq XY$ and the neutral element
given by
$\bm{1}:\Omega\to\mathop{\scalebox{1.5}{\raisebox{-0.86108pt}{$\ast$}}}$, form
a commutative, idempotent monoid.

###### Proof.

See Lang et al. (2022), Proposition 3.8. ∎

Clearly, any subset of equivalence classes of random variables — if it is
closed under multiplication and contains a constant random variable — then
also forms a commutative, idempotent monoid. Together with the
$P$-independence relation defined earlier, this forms a separoid, see
Definition 2.1:

######  Proposition 5.3.

Let $M$ be a monoid of random variables as in Proposition 5.2 and
$P\in\Delta(\Omega)$ a probability distribution. Then
$(M,\perp\\!\\!\\!\perp_{P})$ is a separoid.

###### Proof.

This is well-known and appeared originally in this formulation in Dawid
(2001). It also follows from the generalization given in Forré (2021), Theorem
3.11. ∎

We will later also need the following definition, for example for defining the
Kullback-Leibler divergence:

######  Definition 5.4 (Absolutely Continuous).

Let $P,Q\in\Delta(\Omega)$ be two probability distributions. Then $P$ is said
to to be absolutely continuous with respect to $Q$, written $P\ll Q$, if the
following implication holds for all $\omega\in\Omega$:

$Q(\omega)=0\quad\Longrightarrow\quad P(\omega)=0.$

We now specialize the notions of conditional mutual independences, FCMIs,
Markov random fields, and Markov chains from general separoids to the
probabilistic case to make wordings and notation more efficient. Recall
Definitions 2.3, 2.7, 2.6, 2.10, and 4.6.

######  Terminology 5.5.

Let $X_{1},\dots,X_{n},Y$ be discrete random variables on $\Omega$,
$P:\Omega\to[0,1]$ a probability distribution, and $\perp\\!\\!\\!\perp_{P}$
the corresponding separation relation. If $X_{1},\dots,X_{n}$ are mutually
independent given $Y$ with respect to $\perp\\!\\!\\!\perp_{P}$, then we write

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

and call this a conditional mutual $P$-independence. Let
$K=\big{(}J,L_{i},1\leq i\leq q\big{)}$ be conditional partition of $[n]$.
Then the $FCMI$

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

is called a full conditional mutual $P$-independence (with respect to
$X_{1},\dots,X_{n}$) — or $P$-FCMI for short. If it holds, then we say $K$
induces a $P$-FCMI. Now, let
$\mathcal{G}=\big{(}\mathcal{V},\mathcal{E}\big{)}$ be a graph with
$\mathcal{V}=[n]$. If $X_{1},\dots,X_{n}$ form a Markov random field with
respect to $\mathcal{G}$ and $\perp\\!\\!\\!\perp_{P}$, then we say that
$X_{1},\dots,X_{n}$ form a $P$-Markov random field with respect to
$\mathcal{G}$. Finally, $X_{1},\dots,X_{n}$ are said to form a $P$-Markov
chain if they form a Markov chain with respect to $\perp\\!\\!\\!\perp_{P}$.

###  5.2 Stability under Conditioning

In this subsection, we show that for discrete random variables
$X_{1},\dots,X_{n}$, the property to be an FCMI, the property to be a Markov
random field, and the property of two distributions to have “equal transition
probabilities” between time-steps in a Markov chain, are all _stable under
conditioning_. That means that if they hold with respect to a probability
distribution $P$, they also hold with respect to $P|_{Y=y}$ for arbitrary
$Y=X_{I}$ with $I\subseteq[n]$ and $y\in E_{Y}$. We first need two lemmas:

######  Lemma 5.6.

Let $X,Y,Z$ be three random variables on $\Omega$ and $P:\Omega\to[0,1]$ a
probability distribution. If $P(y,z)\neq 0$, then

$\big{(}{P}|_{Y=y}\big{)}(x\mid z)=P(x\mid y,z).$

###### Proof.

We have:

$\displaystyle\big{(}{P}|_{Y=y}\big{)}(x\mid
z)=\Big{(}{\big{(}{P}|_{Y=y}\big{)}}|_{Z=z}\Big{)}(x)=\big{(}{P}|_{YZ=(y,z)}\big{)}(x)=P(x\mid
y,z).$

The second step can be showed by explicit computation. ∎

######  Lemma 5.7.

Let $U,V,W,Y$ be discrete random variables on $\Omega$ and $P:\Omega\to[0,1]$
a probability distribution such that the following independence holds:

$U\underset{P}{\perp\\!\\!\\!\perp}V\ |\ WY.$

Let $y\in E_{Y}$ be arbitrary with $P(y)\neq 0$. Then the following
independence follows:

$U\underset{{P}|_{Y=y}}{\perp\\!\\!\\!\perp}V\ |\ W.$

###### Proof.

Let $u\in E_{U},v\in E_{V}$ and $w\in E_{W}$ be arbitrary. We want to show the
following:

$\big{(}{P}|_{Y=y}\big{)}(u,v,w)=\big{(}{P}|_{Y=y}\big{)}(u\mid
w)\cdot\big{(}{P}|_{Y=y}\big{)}(v,w).$ (20)

If $P(w\mid y)=0$, then both sides of Equation (20) vanish and the result is
clear. Thus, we can assume $P(w\mid y)\neq 0$, and therefore, together with
$P(y)\neq 0$, we obtain $P(w,y)\neq 0$. By Lemma 5.6, this results in
$\big{(}{P}|_{Y=y}\big{)}(u\mid w)=P(u\mid w,y)$. We obtain that the desired
Equation (20) is equivalent to the following:

$\frac{P(u,v,w,y)}{P(y)}=P(u\mid w,y)\cdot\frac{P(v,w,y)}{P(y)},$

which is equivalent to

$P(u,v,w,y)=P(u\mid w,y)\cdot P(v,w,y).$

This follows from the assumption $U\underset{P}{\perp\\!\\!\\!\perp}V\ |\ WY$.
∎

######  Proposition 5.8.

Let $X_{1},\dots,X_{n}$ be discrete random variables on $\Omega$,
$P:\Omega\to[0,1]$ a probability distribution, and $K=\big{(}J,L_{i},1\leq
i\leq q\big{)}$ a conditional partition of $[n]$ that induces a $P$-FCMI with
respect to $X_{1},\dots,X_{n}$. Then for all $I\subseteq[n]$, for $Y\coloneqq
X_{I}$, and for all $y\in E_{Y}$ with $P(y)\neq 0$, $K$ also induces a
$\big{(}P|_{Y=y}\big{)}$–FCMI with respect to $X_{1},\dots,X_{n}$.

###### Proof.

By assumption, we have the $P$-FCMI
$P:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$. This means that for all $i\in\\{1,\dots,q\\}$, we have

$X_{L_{i}}\underset{P}{\perp\\!\\!\\!\perp}X_{\bigcup_{l\neq i}L_{l}}\ |\
X_{J}.$ (21)

Now, decompose $I$ into three sets $I_{i}=I\cap L_{i}$, $I_{\setminus
i}=I\cap\bigcup_{l\neq i}L_{l}$ and $I_{J}=I\cap J$. We obtain the
corresponding random variables $Y_{i}=X_{I_{i}}$, $Y_{\setminus
i}=X_{I_{\setminus i}}$ and $Y_{J}=X_{I_{J}}$. Since the monoid of random
variables is idempotent, the above pairwise $P$-independence is equivalent to
the following:

$Y_{i}X_{L_{i}}\underset{P}{\perp\\!\\!\\!\perp}Y_{\setminus
i}X_{\bigcup_{l\neq i}L_{l}}\ |\ X_{J}Y_{J}.$

Applying weak union (S4) to both the left and right factor, we obtain

$X_{L_{i}}\underset{P}{\perp\\!\\!\\!\perp}X_{\bigcup_{l\neq i}L_{l}}\ |\
X_{J}\big{(}Y_{i}Y_{\setminus i}Y_{J}\big{)}.$

Since $K$ is _full_ , meaning the contained sets cover all of $[n]$, we obtain
$I=I_{i}\cup I_{\setminus i}\cup I_{J}$ and consequently $Y_{i}Y_{\setminus
i}Y_{J}=Y$. Lemma 5.7 then shows the $\big{(}P|_{Y=y}\big{)}$–independence
${X_{L_{i}}\underset{P|_{Y=y}}{\perp\\!\\!\\!\perp}X_{\bigcup_{l\neq i}L_{l}}\
|\ X_{J}}$. Since $i$ was arbitrary, we obtain the
$\big{(}P|_{Y=y}\big{)}$–FCMI
$P|_{Y=y}:\mathop{\raisebox{0.0pt}{\scalebox{1.4}{$\displaystyle\perp\\!\\!\\!\perp$}}}_{i=1}^{q}X_{L_{i}}\
|\ X_{J}$. That was to show. ∎

######  Corollary 5.9.

Let $X_{1},\dots,X_{n}$ be discrete random variables on $\Omega$,
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ a graph with $\mathcal{V}=[n]$, and
$P:\Omega\to[0,1]$ a probability distribution. Assume $X_{1},\dots,X_{n}$ form
a $P$-Markov random field with respect to $\mathcal{G}$.

Then for all $I\subseteq[n]$, for $Y\coloneqq X_{I}$, and for all $y\in E_{Y}$
with $P(y)\neq 0$, $X_{1},\dots,X_{n}$ also form a
$\big{(}P|_{Y=y}\big{)}$–Markov random field with respect to $\mathcal{G}$.

###### Proof.

We show this by proving the cutset property, which by Proposition 2.9 is
equivalent to the global Markov property. Thus, let $\mathcal{U}\subseteq[n]$
be a cutset and $\mathcal{V}_{1}(\mathcal{U})$, …,
$\mathcal{V}_{s\left(\mathcal{U}\right)}(\mathcal{U})$ the corresponding
components. By assumption we know that the conditional partition
$K=\big{(}\mathcal{U},\mathcal{V}_{i}(\mathcal{U}),1\leq i\leq
s\left(\mathcal{U}\right)\big{)}$ induces a $P$-FCMI. Then Proposition 5.8
shows that we also obtain a $\big{(}P|_{Y=y}\big{)}$–FCMI, meaning we have
${P|_{Y=y}:\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}}}$. This was to show. ∎

Next, we show that the property to have “equal transition probabilities”
between time-steps in a Markov chain is stable under conditioning. We will use
this in Section 5.5 to illustrate a weak version of the second law of
thermodynamics.

######  Proposition 5.10.

Let $X_{1},\dots,X_{n}$ be discrete random variables on $\Omega$ and
$(P,Q)\in\Delta(\Omega)^{2}$ be two probability distributions such that $P$ is
absolutely continuous with respect to $Q$, see Definition 5.4. Assume that
$X_{1},\dots,X_{n}$ form a $P$-Markov chain _and_ $Q$-Markov chain.
Additionally, assume that $P$ and $Q$ have the same transition probabilities,
i.e.: $P(x_{i}\mid x_{i-1})=Q(x_{i}\mid x_{i-1})$ for all $i$ and all
$x_{i-1},x_{i}$ with $P(x_{i-1})\neq 0$.

Then for all $I\subseteq[n]$, for $Y\coloneqq X_{I}$, and for all $y\in E_{Y}$
with $P(y)\neq 0$, ${P}|_{Y=y}$ is also absolutely continuous with respect to
${Q}|_{Y=y}$ and $X_{1},\dots,X_{n}$ also forms a
$\big{(}{P}|_{Y=y}\big{)}$–Markov chain and a
$\big{(}{Q}|_{Y=y}\big{)}$–Markov chain. Additionally, ${P}|_{Y=y}$ and
${Q}|_{Y=y}$ also have the same transition probabilities, i.e.:
$({P}|_{Y=y})(x_{i}\mid x_{i-1})=({Q}|_{Y=y})(x_{i}\mid x_{i-1})$ for all $i$
and all $x_{i-1},x_{i}$ with $({P}|_{Y=y})(x_{i-1})\neq 0$.

###### Proof.

That ${P}|_{Y=y}$ is absolutely continuous with respect to ${Q}|_{Y=y}$ is
clear. That $X_{1},\dots,X_{n}$ also forms a $\big{(}{P}|_{Y=y}\big{)}$–Markov
chain and a $\big{(}{Q}|_{Y=y}\big{)}$–Markov chain follows from the fact that
Markov chains are Markov random fields by Proposition 2.11, and from Corollary
5.9.

For the second statement, let $i$ be given. Write $I=I_{-}\cup I_{+}$ with
$I_{-}\subseteq[i-1]$, $I_{+}\subseteq\left[i:n\right]$. Correspondingly, we
write $Y=Y_{-}Y_{+}$. Remember that being a Markov chain implies being a
Markov random field according to Proposition 2.11. Together with Lemma 2.2 and
the decomposition separoid axiom (S3), one can show the following two
independences:

$X_{i}\underset{P}{\perp\\!\\!\\!\perp}Y_{-}\ |\ X_{i-1}Y_{+},\quad\quad
X_{i}\underset{Q}{\perp\\!\\!\\!\perp}Y_{-}\ |\ X_{i-1}Y_{+}.$

It follows

$\displaystyle\big{(}{P}|_{Y=y}\big{)}(x_{i}\mid x_{i-1})$
$\displaystyle\overset{(\star)}{=}P(x_{i}\mid x_{i-1},y)$
$\displaystyle\big{(}\text{Lemma\leavevmode\nobreak\
\ref{lem:double_conditioning}}\big{)}$ $\displaystyle=P(x_{i}\mid
x_{i-1},y_{-},y_{+})$ $\displaystyle=P(x_{i}\mid x_{i-1},y_{+})$
$\displaystyle=\frac{P(x_{i},y_{+}\mid x_{i-1})}{P(y_{+}\mid x_{i-1})}$
$\displaystyle=\frac{P(x_{i}\mid x_{i-1})\cdot P(y_{+}\mid
x_{i-1},x_{i})}{\sum_{x_{i}^{\prime}}P(x_{i}^{\prime}\mid x_{i-1})\cdot
P(y_{+}\mid x_{i-1},x_{i}^{\prime})},$

In $(\star)$, to apply the lemma, we used $P(y)\neq 0$ and the additional
assumption that $\big{(}P|_{Y=y}\big{)}(x_{i-1})\neq 0$, which results in
$P(y,x_{i-1})\neq 0$. Due to to $P$ being absolutely continuous with respect
to $Q$, we also obtain $Q(y,x_{i-1})\neq 0$. Thus, we similarly get:

$\big{(}{Q}|_{Y=y}\big{)}(x_{i}\mid x_{i-1})=\frac{Q(x_{i}\mid x_{i-1})\cdot
Q(y_{+}\mid x_{i-1},x_{i})}{\sum_{x_{i}^{\prime}}Q(x_{i}^{\prime}\mid
x_{i-1})\cdot Q(y_{+}\mid x_{i-1},x_{i}^{\prime})}.$

By assumption, we already know $P(x_{i}\mid x_{i-1})=Q(x_{i}\mid x_{i-1})$.
The preceding computations therefore show that it is enough to prove that
$P(y_{+}\mid x_{i-1},x_{i})=Q(y_{+}\mid x_{i-1},x_{i})$. We can assume that
$I_{+}\subseteq\left[i+1:n\right]$ since otherwise $x_{i}$ determines the
first entry of $y_{+}$, which can then be removed from the expression if it is
equal to $x_{i}$. Then, let $J\subseteq\left[i+1:n\right]$ be such that
$J\dot{\cup}I_{+}=\left[i+1:n\right]$. We obtain:

$\displaystyle P(y_{+}\mid x_{i-1},x_{i})$
$\displaystyle=\sum_{x_{J}}P\big{(}x_{\left[i+1:n\right]}\mid
x_{i-1},x_{i}\big{)}$
$\displaystyle=\sum_{x_{J}}\prod_{j=i}^{n-1}P(x_{j+1}\mid x_{j})$
$\displaystyle\big{(}\text{Markov chain property}\big{)}$
$\displaystyle=\sum_{x_{J}}\prod_{j=i}^{n-1}Q(x_{j+1}\mid x_{j})$
$\displaystyle=\sum_{x_{J}}Q\big{(}x_{\left[i+1:n\right]}\mid
x_{i-1},x_{i}\big{)}$ $\displaystyle\big{(}\text{Markov chain
property}\big{)}$ $\displaystyle=Q(y_{+}\mid x_{i-1},x_{i}).$

This was to show. ∎

###  5.3 Information Functions Satisfying the Chain Rule

Before we show in the next subsection that information functions can always be
restricted to stable probability sets, we first define a class of information
functions to work with. This includes Shannon entropy, Kullback-Leibler
divergence, and cross-entropy. We also connect higher-order cross-entropy and
Kullback-Leibler divergence to the notion of cluster entropy defined in Cocco
and Monasson (2012).

To capture many information functions, we work in the following general
setting very similar to Baudot and Bennequin (2015), Section 5. Let $M$ be the
monoid of equivalence classes of discrete random variables on the fixed sample
space $\Omega$, and let $r\geq 0$ be a natural number. We denote tuples of
distributions in $\Delta(\Omega)^{r+1}$ by
$\big{(}Q\|P_{1},\dots,P_{r}\big{)}\coloneqq\big{(}Q,P_{1},\dots,Q_{r}\big{)}$
to remind of the notation inside the Kullback-Leibler divergence. Then, we set

$\widetilde{\Delta(\Omega)^{r+1}}\coloneqq\Big{\\{}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in\Delta(\Omega)^{r+1}\
\big{|}\ P\ll Q_{1},\dots,P\ll Q_{r}\Big{\\}}.$ (22)

Here, $P\ll Q$, means that $P$ is absolutely continuous with respect to $Q$,
see Definition 5.4. In applications, $r=0$ would be used for Shannon entropy
and $\alpha$-entropy, and $r=1$ for Kullback-Leibler divergence,
$\alpha$–Kullback-Leibler divergence and cross-entropy, indicating the number
of additional probability distributions. We do not have applications for
$r\geq 2$ in mind.

Let

$G\coloneqq\operatorname{Meas}\Big{(}\widetilde{\Delta(\Omega)^{r+1}},\mathds{R}\Big{)}\coloneqq\Big{\\{}f:\widetilde{\Delta(\Omega)^{r+1}}\to\mathds{R}\
\big{|}\ f\mathrm{\ is\ measurable}\Big{\\}},$ (23)

which clearly is an abelian group. We also assume an additive monoid action of
$M$ on $G$ given by the formula

$\big{[}X.f\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}=\sum_{x\in
E_{X}}g\big{(}P(x),Q_{1}(x),\dots,Q_{r}(x)\big{)}\cdot
f\big{(}P|_{X=x}\|Q_{1}|_{X=x},\dots,Q_{r}|_{X=x}\big{)}$ (24)

for some measurable function $g:[0,1]^{r+1}\to\mathds{R}$ with
$g(0,\star,\dots,\star)=0$.101010The condition $g(0,\star,\dots,\star)=0$ is
satisfied in all examples we consider and ensures that we have a zero
coefficient whenever the conditionals are not defined. We then define the
product as simply zero. Additionally, note that due to absolute continuity, we
have $P(x)=0$ whenever $Q_{i}(x)=0$ for some $i$. Therefore, it is enough to
have the vanishing condition for $g$ in the first component only. We assume
$g$ to be the same function irrespective of $X,f$, and $P,Q_{1},\dots,Q_{r}$.
Note that $P\ll Q_{i}$ implies that also ${P}|_{X=x}\ll{Q_{i}}|_{X=x}$, which
means that the preceding formula is actually defined.

Furthermore, we assume to have a function $F:M\to G$ that satisfies the chain
rule, meaning that for all $X,Y\in M$, we have

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

The reader can verify that all of Shannon entropy, Kullback-Leibler
divergence, $\alpha$-entropy, $\alpha$–Kullback-Leibler divergence, and cross-
entropy, fit precisely under this umbrella. Precise definitions that fit our
exact framework can be found in Lang et al. (2022), Sections 3 and 6. For
example, for Shannon entropy we have $r=0$ and
$G=\operatorname{Meas}\big{(}\Delta(\Omega),\mathds{R}\big{)}$. The action is
given by

$\big{[}X.f\big{]}(P)\coloneqq\sum_{x\in E_{X}}P(x)\cdot
f\big{(}P|_{X=x}\big{)},$

and the Shannon entropy $I:M\to G$ is given by

$\big{[}I(X)\big{]}(P)\coloneqq-\sum_{x\in E_{X}}P(x)\cdot\log P(x),$ (25)

which indeed satisfies the chain rule $I(XY)=I(X)+X.I(Y)$. Note that
$0\cdot\log 0\coloneqq 0$ in this formula. Similarly, for Kullback-Leibler
divergence we have $r=1$ and
$G=\operatorname{Meas}\Big{(}\widetilde{\Delta(\Omega)^{2}},\mathds{R}\Big{)}$.
The action is given by

$\big{[}X.f\big{]}(P\|Q)\coloneqq\sum_{x\in E_{X}}P(x)\cdot
f\big{(}P|_{X=x}\|Q|_{X=x}\big{)}.$ (26)

The Kullback-Leibler divergence $D:M\to G$ is then defined by

$\big{[}D(X)\big{]}(P\|Q)\coloneqq\sum_{x\in
E_{X}}P(x)\cdot\log\frac{P(x)}{Q(x)}.$ (27)

This also satisfies the chain rule: $D(XY)=D(X)+X.D(Y)$. Note that
$0\cdot\log\frac{0}{Q(x)}\coloneqq 0$ in this formula. Similarly, the cross-
entropy $C:M\to G$ is defined by

$\big{[}C(X)\big{]}(P\|Q)\coloneqq\sum_{x\in
E_{X}}P(x)\cdot\log\frac{1}{Q(x)}.$ (28)

Clearly, one then has $C(X)=I(X)+D(X)$.

Once these definitions are set in place, one can study higher-order terms
$F:M^{q}\to G$ as in Equation (16), and visualize them in $F$-diagrams. The
higher-order terms for Shannon entropy $I$, i.e., the mutual information and
interaction information, are frequently studied, whereas the higher-order
terms for $C$ and $D$ have gotten substantially less attention. So before we
continue to study the $F$-diagrams of such functions for Markov random fields
in the coming section, we briefly connect these higher-order terms to the
cluster entropy from Cocco and Monasson (2012).

Namely, Cocco and Monasson (2012) define the cluster (cross-)entropy111111The
authors often write “entropy” when they actually mean cross-entropy. $\Delta
C$ for subsets of $n$ random variables $X_{1},\dots,X_{n}$ by

$\Delta C\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in
J}X_{j}\big{)}\coloneqq\sum_{K\subseteq J}(-1)^{|K|-|J|}\cdot C(X_{K}).$ (29)

In contrast, we define higher-order cross-entropies as in Equation (16) by the
inductive formula

$C\big{(}X_{j_{1}};\dots;X_{j_{q}}\big{)}=C\big{(}X_{j_{1}};\dots;X_{j_{q-1}}\big{)}-X_{j_{q}}.C\big{(}X_{j_{1}};\dots;X_{j_{q-1}}\big{)}.$

In Lang et al. (2022), Corollary 3.6, part 6, it is deduced from the
generalized Hu theorem that this obeys the following inclusion-exclusion type
formula:

$C\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in
J}X_{j}\big{)}=\sum_{K\subseteq J}(-1)^{|K|+1}\cdot C(X_{K}).$ (30)

Comparing Equations (29) and (30), we see that our higher-order cross-
entropies and the cluster cross-entropies differ by a simple sign that depends
on the order:

$C\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in
J}X_{j}\big{)}=(-1)^{|J|+1}\cdot\Delta
C\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in J}X_{j}\big{)}.$

Higher-order Kullback-Leibler divergence is then fully determined by higher-
order cross-entropy and information, as
$D\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in
J}X_{j}\big{)}=C\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in
J}X_{j}\big{)}-I\big{(}\mathop{}{\scalebox{1.6}{$\displaystyle;$}}_{j\in
J}X_{j}\big{)}$. We hope that these connections provide motivation for the
reader to study information diagrams for functions such as cross-entropy and
Kullback-Leibler divergence, and that the study of these diagrams, in turn,
could help to better understand concepts like the cluster cross-entropies.

###  5.4 Restricting Information Measures to Stable Probability Sets

In this subsection, we show that information functions that “satisfy the chain
rule” can, under mild conditions, always be restricted to subsets of
probability distributions as long as those are stable. We define this notion
in Definition 5.11, which encompasses the examples we saw in the previous
subsection. In Theorem 5.14, we will then see that restricting to probability
distributions that give rise to Markov random fields leads to the formalism of
an $F$-Markov random field, as studied in Section 4.3. Let the notation
throughout be as in the preceding subsection.

######  Definition 5.11 (Stable Property).

Let $n\geq 0$, $X_{1},\dots,X_{n}\in M$, $r\geq 0$, and
$\mathcal{R}=\mathcal{R}(X_{1},\dots,X_{n})$ be a property of probability
tuples with $r+1$ entries, which means that for all
$\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in\Delta(\Omega)^{r+1}$,
$\mathcal{R}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$ is either true or false.
$\mathcal{R}$ is called _stable_ if the following holds:

  * •

$\mathcal{R}$ is _well-defined_ , i.e., if $Y_{1},\dots,Y_{n}$ are discrete
random variables on $\Omega$ with $Y_{i}\sim X_{i}$, then
$\mathcal{R}(X_{1},\dots,X_{n})=\mathcal{R}(Y_{1},\dots,Y_{n})$;

  * •

$\mathcal{R}$ is _measurable_ , i.e., the set

$\Big{\\{}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in\Delta(\Omega)^{r+1}\ \big{|}\
\mathcal{R}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\Big{\\}}$

is a measurable subset of $\Delta(\Omega)^{r+1}$;

  * •

$\mathcal{R}$ is _stable under conditioning with respect to
$X_{1},\dots,X_{n}$_, i.e.: let $M_{\mathcal{R}}$ be the submonoid of $M$
generated by $X_{1},\dots,X_{n}$.121212I.e., this submonoid consists of all
$X_{I}$ for $I\subseteq[n]$. Then we assume that for all
$\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in\Delta(\Omega)^{r+1}$, all $Y\in
M_{\mathcal{R}}$, and all $y\in E_{Y}$ with $P(y)\neq 0$, following
implication holds:

$\mathcal{R}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\quad\Longrightarrow\quad\mathcal{R}\big{(}P|_{Y=y}\|Q_{1}|_{Y=y},\dots,Q_{r}|_{Y=y}\big{)}.$

Now, let $X_{1},\dots,X_{n}\in M$, and let
$\mathcal{R}=\mathcal{R}(X_{1},\dots,X_{n})$ be a stable property of
probability tuples with $r+1$ elements. Define

${\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}}\coloneqq\Big{\\{}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\in\widetilde{\Delta(\Omega)^{r+1}}\
\big{|}\ \mathcal{R}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\Big{\\}}.$

Then, define

${G}_{\mathcal{R}}\coloneqq\operatorname{Meas}\Big{(}{\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}},\mathds{R}\Big{)}$
(31)

and the action
${.}_{\mathcal{R}}:{M}_{\mathcal{R}}\times{G}_{\mathcal{R}}\to{G}_{\mathcal{R}}$
by

$\big{[}X{.}_{\mathcal{R}}f\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}\coloneqq\big{[}X.\tilde{f}\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)},$
(32)

where $\tilde{f}$ is any measurable extention of $f$ to all of
$\widetilde{\Delta(\Omega)^{r+1}}$. Note that this means that $X.\tilde{f}$ is
a measurable extension of $X{.}_{\mathcal{R}}f$, and that
$X{.}_{\mathcal{R}}f$ is thus again measurable.

######  Lemma 5.12.

The function
${.}_{\mathcal{R}}:{M}_{\mathcal{R}}\times{G}_{\mathcal{R}}\to{G}_{\mathcal{R}}$,
as defined above, is a well-defined additive monoid action.

###### Proof.

For well-definedness, one first needs to check that for all measurable
$f:{\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}}\to\mathds{R}$,
a measurable extension $\tilde{f}$ to all of
$\widetilde{\Delta(\Omega)^{r+1}}$ exists: note that from the fact that
$\mathcal{R}$ is stable and thus measurable, we immediately obtain that
${\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}}$ is a
measurable subset of $\widetilde{\Delta(\Omega)^{r+1}}$. Then $\tilde{f}$ can,
for example, be constructed by mapping all elements in
$\widetilde{\Delta(\Omega)^{r+1}}\setminus{\big{(}\widetilde{\Delta(\Omega)^{r+1}}\big{)}}_{\mathcal{R}}$
to zero, which is clearly measurable.

Furthermore, one needs to check that the definition is independent of the
extension $\tilde{f}$ and the representative of the _equivalence class_ $X$.
The first requirement follows from Equation (24): $g$ was assumed to be
independent of $\tilde{f}$, and $\tilde{f}$ is only applied to elements on
which already $f$ is uniquely defined, due to the assumption of $\mathcal{R}$
being stable under conditioning. That the formula is independent of the
representative of $X$ then follows since the original action was well-defined.

That ${.}_{\mathcal{R}}$ is additive and $\bm{1}\in{M}_{\mathcal{R}}$ acts
neutrally is obvious. We now show that the action is associative:

$\displaystyle\Big{[}(XY){.}_{\mathcal{R}}f\Big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle=\Big{[}(XY).\tilde{f}\Big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle=\Big{[}X.\big{(}Y.\tilde{f})\Big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle\overset{(\star)}{=}\Big{[}X{.}_{\mathcal{R}}\big{(}Y{.}_{\mathcal{R}}f)\Big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}.$

In step $(\star)$, we used that $Y.\tilde{f}$ is by definition a measurable
extension of $Y{.}_{\mathcal{R}}f$, which by definition of the “outer” action
${.}_{\mathcal{R}}$ gives the result. This finishes the proof. ∎

Finally, let $F:M\to G$ be a function satisfying the chain rule as in Section
5.3 and define

${F}_{\mathcal{R}}:{M}_{\mathcal{R}}\to{G}_{\mathcal{R}},\quad\big{[}{F}_{\mathcal{R}}(X)\big{]}(P\|Q_{1},\dots,Q_{r})\coloneqq\big{[}F(X)\big{]}(P\|Q_{1},\dots,Q_{r}).$
(33)

In other words, ${F}_{\mathcal{R}}(X)$ is just the restriction of $F(X)$ to
the tuples of probability distributions satisfying property $\mathcal{R}$.

######  Proposition 5.13.

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 (24), and that $F:M\to G$ is a
function satisfying the chain rule Equation (15).

Now, let $X_{1},\dots,X_{n}$ be discrete random variables on $\Omega$ and
$\mathcal{R}=\mathcal{R}(X_{1},\dots,X_{n})$ a stable property of tuples of
$r+1$ probability distributions. Let ${M}_{\mathcal{R}}$ be the submonoid
generated by $X_{1},\dots,X_{n}$ and ${G}_{\mathcal{R}}$ be defined as in
Equation (31). Let ${M}_{\mathcal{R}}$ act on ${G}_{\mathcal{R}}$ as in
Equation (32). Then the restricted information function
${F}_{\mathcal{R}}:{M}_{\mathcal{R}}\to{G}_{\mathcal{R}}$, defined in Equation
(33), satisfies the chain rule:

${F}_{\mathcal{R}}(XY)={F}_{\mathcal{R}}(X)+X{.}_{\mathcal{R}}{F}_{\mathcal{R}}(Y).$

###### Proof.

We have

$\displaystyle\big{[}{F}_{\mathcal{R}}(XY)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle=\big{[}F(XY)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle=\big{[}F(X)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}+\big{[}X.F(Y)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle\overset{(\star)}{=}\big{[}{F}_{\mathcal{R}}(X)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}+\big{[}X{.}_{\mathcal{R}}{F}_{\mathcal{R}}(Y)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$
$\displaystyle=\big{[}{F}_{\mathcal{R}}(X)+X{.}_{\mathcal{R}}{F}_{\mathcal{R}}(Y)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}.$

In step $(\star)$, in the right-hand term, we used that $F(Y)$ extends
${F}_{\mathcal{R}}(Y)$, which by definition of the action ${.}_{\mathcal{R}}$
results in $X.F(Y)$ extending $X{.}_{\mathcal{R}}{F}_{\mathcal{R}}(Y)$. ∎

The preceding proposition ensures that we can apply Hu’s Theorem 3.2 to
${F}_{\mathcal{R}}$, which we will make use of in the next section on
Kullback-Leibler Markov chains.

In the next theorem, we restrict this setting somewhat further to obtain a
result on ${F}_{\mathcal{R}}$-Markov random fields that will apply to Shannon
entropy, Kullback-Leibler divergence and cross-entropy. The result will,
however, as stated not apply to $\alpha$-entropy and $\alpha$–Kullback-Leibler
divergence.

For the theorem, we make the stronger assumption that the action of $M$ on $G$
is given by

$\big{[}X.f\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}=\sum_{x\in
E_{X}}P(x)\cdot f\big{(}P|_{X=x}\|Q_{1}|_{X=x},\dots,Q_{r}|_{X=x}\big{)},$
(34)

meaning that, in Equation (24), we have $g(p,\star,\dots,\star)=p$.
Additionally, we make the assumption that $F$ is given by

$\big{[}F(X)\big{]}\big{(}P\|Q_{1},\dots,Q_{r}\big{)}=\sum_{x\in
E_{X}}P(x)\cdot h\big{(}P(x),Q_{1}(x),\dots,Q_{r}(x)\big{)}$ (35)

for some function $h:[0,1]^{r+1}\to\mathds{R}$. Clearly, all these stronger
assumptions hold for Shannon entropy, Kullback-Leibler divergence, and cross-
entropy, see, e.g., Equations (25) and (27).131313To make those examples fit
the framework precisely, one needs to define $\log(0)$ to be an arbitrary real
number instead of $-\infty$. This does not change the result as $\log(0)$ is
always multiplied with the coefficient $0$.

Now, fix random variables $X_{1},\dots,X_{n}$ on $\Omega$ and a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with $\mathcal{V}=[n]$. We now define
the property

$\mathcal{MRF}\coloneqq\mathcal{MRF}(\mathcal{G};X_{1},\dots,X_{n}).$ (36)

When applied to a probability tuple $\big{(}P\|Q_{1},\dots,Q_{r}\big{)}$, this
evaluates to “true” if $X_{1},\dots,X_{n}$ form a $P$-Markov random field and,
for all $i$, a $Q_{i}$-Markov random field, with respect to $\mathcal{G}$. We
know from Corollary 5.9 that $\mathcal{MRF}$ is stable under conditioning. It
is also clearly well-defined, since conditional independences do not depend on
the equivalence classes of the involved random variables. Finally, it is
measurable since it is a conjunction of conditional independence relations:
the subset of probability distributions that satisfy an independence relation
can by Equation (19) easily seen to be measurable.

Thus, $\mathcal{MRF}$ is a stable property and we obtain the function
${F}_{\mathcal{MRF}}$ that satisfies the chain rule by Proposition 5.13.
Consequently, we obtain a separation rule
$\perp\\!\\!\\!\perp_{{F}_{\mathcal{MRF}}}$ by Proposition 3.11. In the
following, we slightly generalize from this by considering properties that