{'fraction_non_alphanumeric': 0.03899841503767761, 'fraction_numerical': 0.006673525567944832, 'mean_word_length': 4.235623817149512, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The d-separation criterion in Categorical Probability

The d-separation criterion detects the compatibility of a joint probability distribution with a directed acyclic graph through certain conditional independences. In this work, we study this problem in the context of categorical probability theory by introducing a categorical definition of causal models, a categorical notion of d-separation, and proving an abstract version of the d-separation criterion. This approach has two main benefits. First, categorical d-separation is a very intuitive criterion based on topological connectedness. Second, our results apply both to measure-theoretic probability (with standard Borel spaces) and beyond probability theory, including to deterministic and possibilistic networks. It therefore provides a clean proof of the equivalence of local and global Markov properties with causal compatibility for continuous and mixed random variables as well as deterministic and possibilistic variables.

The d-separation criterion [23] is a necessary and sufficient condition for the compatibility of a probability distribution with a causal structure in the form of a directed acyclic graph (DAG). It states that a joint probability distribution of a collection of random variables is compatible with the DAG-in the sense that each of its nodes is one of the given variables, and each arrow denotes the possibility of causal influence-if and only if the distribution satisfies a list of conditional independence relations encoded in the structure of the DAG.
In this paper, we study this causal compatibility problem in the framework of categorical probability theory. We elaborate on the framework of generalized causal models recently proposed in [12], introduce a categorical notion of d-separation, and prove a categorical generalization of the d-separation criterion. The framework of generalized causal models involves freely generated categories called free Markov categories [12]. Starting from a set of morphisms as building blocks (representing the basic causal mechanisms), we construct a morphism in this category by assembling these blocks consistently. More precisely, a morphism in such a free category is a string diagram consisting of wires and boxes. In our context, these diagrams represent the causal models. Each wire corresponds to a local random variable and each box to a causal mechanism generating one or several new output variables from its input ones. A morphism in any Markov category is compatible with such a causal model if it can be decomposed in the form specified by the causal model; this generalizes the standard factorization definition of Bayesian networks [8].
Further, we define a categorical notion of d-separation in terms of the string diagrams. A causal structure displays d-separation of a collection of outputs Z if it becomes disconnected upon removing the corresponding wires in Z. We show that this is equivalent to classical d-separation for the class of causal models for which the latter is defined, namely those corresponding to DAGs.
Finally, we prove an abstract version of the d-separation criterion for our categorical notions of causal model and d-separation. We show that a given distribution, possibly depending on additional input variables, is compatible with a causal structure if and only if it displays conditional independence between sets of variables whenever the causal model displays d-separation for the corresponding sets of wires. This result goes beyond the classical result for "distributions"; it holds for arbitrary morphisms in any suitable Markov category C. A central structural ingredient in the proof is the assumption that C has conditionals [11]. Intuitively, this property states that every Markov kernel with multiple output variables arises by generating one output variable after the other, namely as a function of the input variables and previously generated outputs. For example, Markov kernels between finite sets have conditionals since every conditional probability distribution p(x, y a) factorizes into p(x, y a) = p(x y, a) ⋅ p(y a).
The conditional distribution p(x y, a) arises by solving this equation for every x, y, and a and taking it to be arbitrary when p(y a) = 0. Conditionals also exist for continuous or mixed random variables (technically for Markov kernels between standard Borel spaces, but not arbitrary measurable spaces) as well as in the Markov category of Gaussian kernels. Moreover, we will show that Markov categories with conditionals also exist in settings that do not involve numerical probabilities. This implies that our results apply equally easily to all of these cases.
This approach leads to new insights into the structure of d-separation and generalizes the classical result, to the best of our knowledge, in four notable directions: -It generalizes the d-separation criterion in the pure DAG setting to a larger class of causal models. First, it gives a criterion for the compatibility of Markov kernels with a causal structure rather than merely for probability distributions. This is because Markov categories formalizing probabilities have Markov kernels as their morphisms, which therefore become the basic primitives of our formalism. Second, the local mechanisms in the causal structures are allowed to have multiple outputs and to appear multiple times. While all those generalizations can also be included in the DAG setting via suitable workarounds, as considered for example by [9], string diagrams contain them already intrinsically. -Categorical d-separation on string diagrams is more general and conceptually simpler than "classical" d-separation on DAGs since it only relies on three intuitive operations on string diagrams: marginalization, removing wires, and checking disconnectedness. -It provides a uniform proof of the equivalence between d-separation and causal compatibility for discrete variables, continuous variables (or rather arbitrary variables taking values in standard Borel spaces), and Gaussian variables. This follows from the fact that we reason abstractly and even more generally in any Markov category with conditionals. Together with the first point, this approach, therefore, generalizes the d-separation criterion on the pure DAG setting for continuous variables shown for distribution with a density [19,18], which was later extended to arbitrary variables with values in standard Borel spaces in [10]. -The abstract reasoning using Markov categories implies that the d-separation criterion also applies to non-probabilistic settings, for example to networks modeling deterministic or possibilistic variables and causal mechanisms. This paper is organized as follows. In Section 2, we give a more detailed non-technical overview of the main concepts of this paper, including causal models as string diagrams and categorical d-separation. In Section 3, we recall and explain the definitions of Markov categories and gs-monoidal categories. In Section 4, we review the construction of free gsmonoidal and free Markov categories, leading to generalized causal models and causal compatibility for morphisms in Markov categories. In Section 5, we present the notions of conditionals and conditional independence. In Section 6, we introduce a categorical notion of d-separation and prove the main results of this paper, namely the equivalence with classical d-separation (Proposition 28) and our abstract version of the d-separation criterion for causal compatibility (Theorem 34).

C M
In this paper, we study causal models, in the sense of Bayesian networks, from a categorical perspective. In order to make this accessible to readers without a formal background in category theory, we outline this paper's main concepts and results in this section. Section 2.1 gives a non-technical introduction to the string diagrammatic formalism representing causal models and its relation to the classical DAG formalism. We then present the concept of causal compatibility in Section 2.2 as a functorial property. In Section 2.3, we present categorical d-separation as a statement about the connectedness of the string diagram and explain our result on the d-separation criterion in Section 2.4. Therefore, the string diagrammatic approach opens the door for a new perspective on d-separation and its connection to causal compatibility.
2.1. Extending Bayesian networks with string diagrams. Traditionally, the definition of Bayesian networks relies on the concept of directed acyclic graphs (DAG) since such a graph encodes the underlying causal structure. Each node v ∈ V (G) of a DAG G is associated with a random variable X v , and each directed arrow w → v is associated with a direct possible causal dependence of the variable X v on X w . Formally, if we index the nodes by 1, . . . , n, then this means that a joint probability distribution P is compatible with G if P factorizes into where Pa(X i ) = {X j ∶ G contains the arrow j → i} is the set of parents of X i relative to G.
In the categorical framework, we can refine the notion of Bayesian networks via string diagrams, an idea that extends the categorical approach developed by Fong [8] and others [26,27,14,16]. These diagrams arise naturally in categorical probability, which refers more generally to recent work on axiomatizing probability theory with simple, algebraic rules which avoid the low-level machinery of measure theory by hiding it in the proofs of the relevant axioms [11].
In categorical probability, the basic primitives are conditional probability distributions, also known as Markov kernels. A Markov kernel is represented as a morphism f ∶ A → X, depicted as X f A Here, A represents the input space and X the output space. The morphism f can be understood as a map that assigns a probability distribution on X to every point a ∈ A in a measurable way. Depending on the particular context, f can be a stochastic matrix representing a Markov kernel between finite sets, a linear map with added Gaussian noise, or an arbitrary measurable Markov kernel. For example, a finite stochastic matrix is defined as a map is a probability distribution on X for every a ∈ A. When choosing A to be a singleton set I, a morphism p ∶ I → X represents a probability distribution, depicted as p X Here, I is not drawn in the diagram, the upper wire represents the probability space X, and the box p the distribution, considered now as a function with no input and one (random) output in X. Therefore, probability distributions are considered as special cases of the basic primitives in categorical probability by setting the input space A to be a trivial object I. These morphisms can be composed into new ones. For example, composing f ∶ X → Y with p ∶ I → X, pictorially Y f p gives rise to a new distribution of a random variable with values in Y . In the concrete setting, the composition is given by the Chapman-Kolmogorov equation, which reads for discrete distributions as and for Markov kernels on arbitrary measurable spaces as where A ∈ Σ Y , with Σ Y the σ-algebra of the measurable space Y .
Each random variable can be copied or marginalized over, for which there exists special string diagrammatic notation: and These maps satisfy manipulation rules formalizing basic properties of information flow, for example: (i) When marginalizing the output of a box, the action of the box becomes irrelevant and therefore the box can be removed from the diagram, pictorially This also applies in the case of multiple outputs since the formalism allows viewing multiple wires as a single one (which corresponds to the operation of taking products of measurable spaces). (ii) When marginalizing an output of the copy map, the resulting map acts like an identity, pictorially We formally axiomatize the semantics of the resulting string diagram calculus in Definition 1 as the definition of a Markov category.
Each flavour of probability has its own Markov category. There is a Markov category for discrete probabilities (called FinStoch), one for Gaussian probability (Gauss), one for probability theory on standard Borel spaces (BorelStoch), and one for probability theory on arbitrary measurable spaces (Stoch).
But there are also non-probabilistic Markov categories. These include Markov categories in which every morphism is deterministic (for example FinSet) and possibilistic Markov categories (for example FinSetMulti), in which the non-determinism comes merely in the form a distinction between which outcomes are possible and which ones are not: for a morphism f ∶ X → Y , we have f (y x) = 1 or f (y x) = 0 according to whether a certain outcome y ∈ Y is possible on an input x ∈ X or not.
The causal structures themselves are also morphisms in yet another class of Markov categories, the so-called free Markov categories. These form our framework for causal structures which generalize DAGs. Rather than Markov kernels, the morphisms in a free Markov category are the string diagrams themselves, i.e. all "networks" that can be built by wiring together a set of boxes, similar to how an electrical circuit is obtained by wiring together electrical components. In this way, string diagrams constitute generalized causal models. In particular, we will see that string diagrams can represent arbitrary DAG causal models. Consider for example this DAG: As a string diagram, this causal structure looks like this: By definition, a probability distribution P (X, Y, Z, W ) is compatible with this structure if Each box in the string diagram represents a placeholder for a conditional distribution. For example, the box f stands for the conditional distribution P (W XY ). Each loose wire 1 represents a random variable where the wire's name indicates the variable's name. Further, each variable has a corresponding type, a placeholder for the measurable space in which the variable takes values. Unless necessary, we will not explicitly mention the type of each variable.
In our setting, some wires are connected to an "output" representing a variable that is "observed" rather than marginalized over, as indicated by the white dots. Note that every variable then becomes an output in at most one way. While the above string diagram connects every wire to an output, the following string diagram also contains "unobserved" variables: In the setting of discrete probability, a distribution P (X, Y ) is therefore compatible with this structure, if where the marginalized variable Z is represented by the wire not connected to the output. In certain situations, we only consider causal models where every wire is connected to an output. Throughout the paper, we call such diagrams pure blooms (see Definition 10). Unless stated otherwise, we will denote the output by the name of the wire connected to the output. We will define certain operations, like d-separations, only with respect to output wires, highlighting that we cannot address latent variables (i.e. wires that are not connected to an output) in general.
Causal models given by a DAG correspond to pure bloom string diagrams where each box has precisely one output wire, and the input wires represent the parents of the node in the DAG. The following table explains the relation between nodes in a DAG, boxes in the string diagram and the corresponding conditional probability distribution. DAG string diagram conditional distribution one output Using string diagrams themselves as generalized causal models allows us to go beyond the DAG approach in several directions: -String diagrams in Markov categories describe Markov kernels instead of just probability distributions. Therefore, the string diagram language allows for modeling causal structures with inputs, such as This describes a causal structure in which the input variable at the bottom does not have any particular distribution itself. For example, a conditional probability distribution is compatible with the above string diagram if -As indicated in the table, boxes in the string diagram can have more than a single output wire. This allows for causal structures like which are not native to the DAG framework (see Example 36(i) for a detailed discussion of this structure). In this situation a probability distribution P (X, Y, Z 1 , Z 2 ) is compatible with the given structure if -String diagrams allow for the use of identical boxes multiple times. This allows to represent for example the transition probabilities of a Markov decision processes (see [25, Section 2.1]) as the causal structure Here, S i denotes the state variable and A i the action variables at time i and the boxes are all identical since such a decision process is given by a fixed conditional probability distribution which highlights that a Markov decision process has no additional internal memory besides the previous state. Moreover, in this situation the types of the variables A 1 , . . . , A n must be the same, namely a particular action space A, and similarly the S 1 , . . . , S n all represent the same state space S. Therefore, the box f can be seen as a morphism S ⊗ A → S.
Throughout the paper, we will usually follow the convention of labelling wires by their types together with an index that lets us address them individually, and at the same time identify these wires with the variables they carry. We do not index the boxes as there is no need to reference the distinct instances of the same type of box separately.

Causal compatibility for Markov categories.
A distribution is compatible with a causal model if it can be written as a composition in precisely the way specified by the corresponding string diagram. In other words, every type W in the string diagram must be mapped to a concrete measurable space F W and every box f to a concrete Markov kernel F f .
In category-theoretic language, this is captured in the following way [8]. A morphism p in a concrete Markov category is compatible with a causal structure ϕ if and only if there exists a Markov functor F such that p = F ϕ. Intuitively, this functor acts in the following way:

FreeMarkov
Stoch, BorelStoch, where p is the given morphism in a concrete Markov category and FreeMarkov the free Markov category whose morphisms capture the causal models. Further, X has type A, Y has type B, and Z has type C. So if the original p takes input from a measurable space Z ′ and outputs values in measurable spaces X ′ , Z ′ and Y ′ , then the types must match in the sense that F A = X ′ etc.

2.3.
Categorical d-separation. The notion of d-separation for DAGs is a criterion relating conditional independence in causal models to the causal compatibility with a DAG. In Section 6.1, we introduce a categorical notion of d-separation from a different perspective. Although this notion looks different and conceptually much simpler than classical d-separation, we prove that it coincides with the classical one when considering causal models on DAGs.
An output wire Z categorically d-separates the output X from output Y if X and Y become disconnected upon marginalizing over all wires not in X, Y and Z and then removing the wire Z. We also express this by saying that X is categorically d-separated from Y by Z.
Consider, for example, the DAG in Equation (3). Z classically d-separates X from Y , as one can see based on the fact that the only paths between X and Y are the collider X → W ← Y and the fork X ← Z → Y . In the corresponding string diagram, Equation (4), we witness categorical d-separation by first marginalizing over W , then removing the Z wire, and finally observing that X and Y are disconnected, pictorially: Here we have used the rules of marginalization, namely Equation (1) and Equation (2).
On the other hand, X is not d-separated from Y by W and Z due to the collider X → W ← Y . In the string diagram, this is apparent since upon removing the wires Z and W , We note that there also are approaches to classical d-separation based on topological disconnectedness, such as using the moralized graph of a DAG [18,Proposition 3.25]. An application of this criterion consists of four steps: first, marginalizing a certain subset of variables not present in the d-separation; second, moralizing the DAG to an undirected graph; third, removing every vertex associated to Z; and finally, checking disconnectedness. Categorical d-separation is conceptually simpler than the DAG approach since it consists only of three steps, namely marginalizing all variables not involved in the putative d-separation, removing the Z wires, and then checking disconnectedness. The moralization step is omitted since its function is already encoded in the structure of string diagrams. Therefore, categorical d-separation is a more intuitive procedure compared to the standard definitions of d-separation on DAGs.

d-separation and causal compatibility.
For Bayesian networks, d-separation detects conditional independences for any compatible probability distribution. In particular, if two output wires X and Y are d-separated by the output wire Z, we have that X is independent of Y given Z (denoted as X ⊥ Y Z).
Conditional independence in Markov categories is defined string diagrammatically. A probability distribution p on a product space X × Y × Z displays the conditional independence X ⊥ Y Z if it can be written in the form This reflects the classical notion of conditional independence with the two unnamed boxes corresponding to the conditionals 2 ; in the context of discrete probability, it encodes the equation But also for Gaussian random variables as well as measures on standard Borel spaces, one recovers the intuitive notions of conditional independence [11,Section 12]. Moreover, the diagrammatic definition is even sufficient to derive the semigraphoid properties [11,Lemma 12.5]. It also generalizes to a notion of conditional independence for morphisms with inputs (see Definition 20).
In Section 6.2, we prove that the categorical d-separation criterion applies to generalized causal models in Markov categories. For this reason, we define a notion of conditional independence which applies to arbitrary Markov kernels (Definition 20). We first prove the soundness of the d-separation, namely, if Z categorically d-separates X from Y , then X ⊥ Y Z (Corollary 32). Second, we prove the completeness of d-separation for causal compatibility: if a Markov kernel satisfies the global Markov property for a causal structure (i.e. every d-separated triple shows conditional independence), then the Markov kernel is compatible with the structure (see Theorem 34 for the precise assumptions and also the equivalence with the local Markov property).
A central assumption for the proof is the existence of conditionals (see Definition 15). Intuitively it says that the outputs of any morphism f can be generated successively while having access to all prior information. Conditionals exist in discrete probability, measuretheoretic probability on standard Borel spaces and in Gaussian probability, and this facilitates the application of our results to all of these cases, where the second case includes continuous random variables.

-M
In the following, we recall the definitions of Markov categories and gs-monoidal categories. Markov categories are the basic structure modeling different flavors of probability, including discrete random variables, Gaussian random variables, continuous random variables on standard Borel spaces, or random variables on arbitrary measurable spaces. We assume some familiarity with symmetric monoidal categories and string diagrams. We refer to [20,24] for a general introduction to category theory and to [1,5,15] for a more detailed account of monoidal categories and their string diagrammatic calculus.
Intuitively, a monoidal category is a category with a product structure ⊗. Specifically, two objects A, B in the category have an associated product object A ⊗ B. Moreover, if f ∶ A → X and g ∶ B → Y are morphisms, then ⊗ gives rise to a new morphism f ⊗ g ∶ A ⊗ B → X ⊗ Y . This monoidal product can have different realizations. For example, the category Set is monoidal with the Cartesian product of sets and functions. A monoidal category is symmetric if the objects A ⊗ B and B ⊗ A are naturally isomorphic in a nice way. All of the monoidal categories in this paper are symmetric.
The notion of gs-monoidal categories goes back to Gaducci's thesis [13, Definition 3.9] and and an associated paper by Corradini and Gadducci [7]. There, it was considered with a different motivation in the context of term graphs and term graph rewriting.

Definition 1 (gs-monoidal category and Markov category).
(i) A gs-monoidal category C is a symmetric monoidal category with monoidal unit I equipped with a commutative comonoid structure for every object X ∈ C given by a counit del X ∶ X → I and a comultiplication copy X ∶ X → X ⊗ X. In the string diagrammatic notation, these operations are depicted as They are required to satisfy the commutative comonoid equations, diagrammatically given by and to be compatible with the monoidal structure, i.e.
as well as We refer to [12, Remark 2.2] for more details on the multifarious history of these notions. When considering morphisms with multiple inputs or outputs, we often denote the collective inputs and outputs as (multi)sets instead of tensor products. For example, we write Modulo some abuse of notation, the order of the inputs and outputs is irrelevant since we can always permute the wires, and therefore it is enough to consider V and W as multisets rather than lists. (a) FinStoch is the Markov category of finite stochastic maps. The objects are finite sets X, morphisms p ∶ I → X are probability distributions and general morphisms f ∶ X → Y are stochastic matrices with entries f (y x). The symmetric monoidal structure is given by the Cartesian product of sets. (b) Stoch is the Markov category of arbitrary Markov kernels on measurable spaces.
The objects are measurable spaces, morphisms p ∶ I → X are probability measures, and general morphisms f ∶ X → Y are measurable Markov kernels. (c) BorelStoch is given by Stoch restricted to standard Borel spaces as objects. (d) Gauss is the Markov category of Gaussian probability distributions. The objects are the spaces R n , morphisms p ∶ I → R n are Gaussian probability measures and general morphisms f ∶ R n → R m can be understood as stochastic maps of the form where A is any real m × n matrix and ξ is an independent Gaussian variable with given mean and variance. Gauss is a (non-full) subcategory of BorelStoch. (e) FinSet is the Markov category of finite sets and (deterministic) functions. Therefore, a morphism f ∶ X → Y is a function from X to Y and p ∶ I → X is a single element of X. The copy maps are given by and the deletion morphism del X ∶ X → I is the only map to the one-element set I.
Equivalently, a morphism f ∶ X → Y can be thought of a matrix (f (y x)) y∈Y,x∈X with entries in {0, 1} by defining f (y x) = 1 if and only if f (x) = y. This shows that there is a functor FinSet → FinStoch through which the Markov category structure of FinSet is inherited from FinStoch. FinSet also generalizes to the category Set by considering arbitrary sets. (f) FinSetMulti is the Markov category of finite sets and multivalued maps. A morphism f ∶ X → Y is given by a matrix (f (y x)) y∈Y,x∈X with entries in {0, 1} and subject to the condition that for every x, we have f (y x) = 1 for some y If f (y x) = 1, then y is possible when given where we use the convention that 1 + 1 = 1. This suggests the same notation as for morphisms as in FinStoch.
For further details on the composition, the symmetric monoidal structure and the Markov category structure of these examples, we refer to [11].
In our context, gs-monoidal categories that are not Markov categories play more of an auxiliary role which we will detail below.

F M
Causal models are a framework for studying and modeling dependencies between random variables. In this section, we introduce such a framework in the language of Markov categories. We therefore investigate causal relationships independently of the particular notion of probability behind it (discrete, measure-theoretic, Gaussian, etc).
Free Markov categories are the tailored notion for these purposes. These categories contain precisely all blueprints for causal networks that can be built from a bunch of given causal mechanisms. A morphism in this category is then a generalized causal model.
The remainder of this section explains this in technical detail based on the formalism of free gs-monoidal categories and free Markov categories from [12]. 3 This part is structured as follows: In Section 4.1, we introduce the category of hypergraphs. In Section 4.2 we use hypergraphs to define gs-monoidal string diagrams, free gs-monoidal categories, and subsequently free Markov categories. In Section 4.3 we introduce generalized causal models and causal compatibility of morphisms in arbitrary Markov categories.

The category of hypergraphs.
A gs-monoidal string diagram, and therefore also a generalized causal model is defined as a hypergraph with extra structure. To define the relevant notion of hypergraph following [2], let first I be the category defined in the following way: (i) The set of objects is given by {(k, ℓ) k, ℓ ∈ N} ∪ {⋆}.
(ii) Besides the identity morphisms, for every (k, ℓ) there are k+ℓ different morphisms and no other morphisms. It is not necessary to specify a composition rule in I since no compositions except the trivial ones can be formed.

Definition 3.
A functor G ∶ I → Set is called a hypergraph. Accordingly, we define the functor category Hyp ∶= Set I to be the category of hypergraphs.
Intuitively, the functor G characterizes our common interpretation of (directed) hypergraphs in the following way: is the set of vertices, which we will call wires. ℓ)) is the set of hyperedges, which we will call boxes, with k inputs and ℓ outputs. (iii) G(in i ) specifies the ith input wire of every box. (iv) G(out j ) specifies the jth output wire of every box. While the set of wires and boxes of a hypergraph may be infinite, the number of inputs and outputs of a box is always finite. We present a pictorial representation of a hypergraph in Figure 1. The wire E is not incident to any box.
Thus in(b, A) and out(b, A) counts the number of incoming or outgoing wires of type A in the box b. We also define the sets of inputs and outputs as where repeated wires are counted only once.
Next, we analyze the morphisms in Hyp. Since Hyp is a functor category, a morphism α ∶ F → G is precisely a natural transformation α ∶ F ⇒ G. Such a natural transformation is fully determined by its components satisfying naturality, i.e. commutativity of all diagrams of the form In other words, every natural transformation is a structure-preserving map between hypergraphs, i.e. if box f is incident to wire A in its ith input in the hypergraph F , then the same applies to their images with respect to α in the hypergraph G.
A hypergraph can contain an infinite set of wires and boxes. In the following we mainly restrict to finite hypergraphs, i.e. functors G ∶ I → Set where W (G) and are finite sets. We denote the corresponding full subcategory of Hyp by FinHyp.

gs-monoidal string diagrams and free Markov categories.
The pictorial representation of hypergraphs indicates their use for modeling causal structures in a categorical framework. In this subsection, we construct the free Markov category associated to a fixed hypergraph Σ. This is a Markov category in which the morphisms are string diagrams formed out of the boxes in Σ, and we argue that these morphisms can be used as generalized causal models.
However, three apparent problems make hypergraphs not directly applicable to represent string diagrams: (1) General hypergraphs might contain loops, for example in the sense that an output wire of a box may directly feed back as an input. (2) While the splitting of a wire into two represents the copying of values and makes sense in any Markov category, the merging of wires as in Figure 1 does not make sense. (3) A hypergraph in itself does not include any information about which wires are inputs or outputs of the overall diagram.
We resolve these issues by restricting to acyclic and left monogamous hypergraphs and by representing gs-monoidal string diagrams by cospans thereof: where the subscripts are modulo k. (ii) G is left monogamous, i.e. for every wire W ∈ W (G) we have By abuse of notation, we also write G for the underlying hypergraph of the object G in FinHyp Σ, and we write type ∶ G → Σ for the morphism that makes it into an object of FinHyp Σ.
In this definition, the discrete hypergraph n is defined to have W (n) = {1, . . . , n} and contains no boxes. Thus the morphism p ∶ n → G simply equips some wires with labels from 1, . . . , n, thereby telling us which wires of G are input wires of the overall diagram and in which order. The other cospan leg q ∶ m → G similarly encodes the m output wires.

Example 5. Consider the two hypergraphs
Note that we represent Σ by two distinct boxes instead of connecting them via the Y wire in order to highlight the purpose of Σ being the collection of elementary building blocks. The hypergraph G is an object of the slice category FinHyp Σ through the hypergraph morphism type ∶ G → Σ that maps the wires X 1 to X, Y 1 to Y , and W 1 , W 2 , W 3 to W , and that maps the box f 1 to f , and the boxes g 1 , g 2 , g 3 to g.
We define a gs-monoidal string diagram as a cospan by specifying two discrete hypergraphs n and m together with mappings p ∶ n → W (G), q ∶ m → W (G) that specify which wires are connected to the input and to the output output. Let us consider two different choices: (i) If n = {1, 2} and m = {1, 2, 3, 4, 5} as well as then we get a cospan that corresponds to a diagram that could be drawn as (ii) If n = {1} and m = {1, 2, 3} as well as then we get a cospan that corresponds to the gs-monoidal string diagram drawn as 1 Note that we have secretly used the convention to draw the discrete hypergraph n (representing the input) on the bottom and m (representing the output) on the top. Moreover, we used the convention that wires at the bottom of a box are input wires and wires on the top are output-wires.

Remark 6.
Throughout the rest of the paper, we will omit the numbering of input and output based on the convention that inputs and outputs are numbered from left to right. Moreover, we will only label the boxes by their type, highlighting that the causal mechanisms are identical. For example, we will draw the string diagram Example 5 (ii) in simplified form as follows: Moreover, this string diagram is also gs-monoidal since it is acyclic and left monogamous. In contrast, the string diagram in Example 5 (i) is not left monogamous since the wire X 1 does not arise from a unique global input.
For further examples and non-examples of gs-monoidal string diagrams, we refer to Figure 2.
Pictorially, an acyclic hypergraph does not contain a family of wires which form a loop. Further, left monogamy requires that every wire in the hypergraph arises as either a global input or as an output of a box in precisely one way, ensuring that no "merging" of wires occurs. See Figure 2 for an illustration of all of this.
The notion of gs-monoidal string diagram is the main ingredient for constructing a gsmonoidal category whose morphisms are freely generated by the wires and boxes in a fixed hypergraph Σ. Indeed we can now define the category FreeGS Σ as follows: (i) Objects are all hypergraph morphisms σ ∶ n → Σ for n ∈ N, or equivalently finite sequences of wires in Σ. (ii) Morphisms are the isomorphism classes of gs-monoidal string diagrams.
Composition in FreeGS Σ is defined by a pushout which coincides with the way of stacking and connecting up drawings of string diagrams. The gs-monoidal structure likewise corresponds to the obvious operations in terms of string diagrams. We refer to [12] for . details. In the following, we will not distinguish between a gs-monoidal string diagram and its isomorphism class.
Although FreeGS Σ is a gs-monoidal category, it is typically not a Markov category. For example, the first step in the following simplification does not hold since the (cospans of) hypergraphs are not isomorphic, while the second equation does hold: In the following, we define the free Markov category FreeMarkov Σ by taking a quotient of FreeGS Σ which enforces Equation (10), so that also the first equation above becomes true.
be a gs-monoidal string diagram.
Every gs-monoidal string diagram has a normalized version obtained by iteratively applying the rule of Equation (10) to any eliminable box. Since every diagram is finite, this procedure terminates after finitely many steps, and we reach the normalized version. In addition, this diagram is unique since the order of elimination does not matter.
The free Markov category FreeMarkov Σ is now defined just as FreeGS Σ , but with morphisms restricted to the normalized gs-monoidal string diagrams. The composition of morphisms is then defined as composition in FreeGS Σ followed by normalization since the composition of two normalized diagrams need not be normalized. See [12] for details.
In particular, any normalized gs-monoidal string diagram ϕ as in Equation (12) is a morphism of the form in FreeMarkov Σ .
is not normalized since the output of b gets discarded. Applying Equation (10), also the output of c get discarded. Therefore the normalization of ϕ is In general, normalizing a gs-monoidal string diagram defines a strict gs-monoidal functor norm ∶ FreeGS Σ → FreeMarkov Σ that is identity-on-objects.

Causal models and causal compatibility.
We now introduce the notion of a generalized causal model and define when a morphism in a Markov category is considered compatible with a generalized causal model. Definition 9 ([12, Definition 7.1]). Given a hypergraph Σ, a generalized causal model is a normalized gs-monoidal string diagram (represented by (12)) over Σ such that q is injective.
Intuitively, a generalized causal model is a morphism in FreeMarkov Σ where the injectivity of q ensures that each wire is connected to at most one output. This lets us identify the global inputs and outputs with the wires in W (G) (see Notation 13). In the traditional terminology of random variables, the injectivity of q guarantees that different outputs correspond to different variables. Figure 3 shows examples of generalized causal models.
One relevant subclass of generalized causal models are pure blooms. These morphisms represent causal models in which all variables are observed, i.e. every wire is an output in exactly one way, such as in Figure 3(c).   . (Non-)Examples of generalized causal models. While (b), (c) are generalized causal models, the string diagram (a) is not since the output wire of g is connected to two global outputs. Concerning Definition 10, the generalized causal model (b) is not a pure bloom since the output of Λ is not connected to a global output. The generalized causal model (c) is a pure bloom without inputs. For a further analysis of (c) regarding dseparation, see Example 36(i). In all three examples, we have Σ = G and assume type to be the identity map for simplicity.

Definition 10 ([12]). Let ϕ be a generalized causal model represented by a gs-monoidal string diagram
For an example of a pure bloom morphism, we refer to Figure 3. We will show that the soundness of the d-separation criterion holds for arbitrary generalized causal models (see Corollary 32) while the completeness holds for pure bloom morphisms (see Theorem 34).
To define causal compatibility, we make the following assumption for the rest of the paper for convenience:

Assumption 12. Throughout, C is a strict Markov category.
A monoidal category is strict if monoidal products like A ⊗ (B ⊗ C) and (A ⊗ B) ⊗ C, or B ⊗ A and A ⊗ B are not only isomorphic but identical. We refer to [15,Section 1.3] for an introduction to strict monoidal categories.
Although most examples like FinStoch, BorelStoch or Stoch already fail strictness, this does not exclude these examples since we can always work with a strictification instead [11,Theorem 10.17], which satisfies Assumption 12. On the other hand, our free Markov categories FreeMarkov Σ already satisfy this condition "on the nose". In any case, Assumption 12 is a useful convenience that holds without loss of generality.

Notation 13.
For the rest of the paper, we will assume that ϕ is a generalized causal model with We identify inputs and outputs with the wires they map to under p and q and refer to them as such. In particular, we define for the set of all input/output wires. If ϕ is a pure bloom morphism, then out(ϕ) = W (G).
In the following, we present the notion of causal compatibility for a generalized causal model ϕ. Intuitively, a morphism f in any Markov category C is compatible with ϕ if we can plug in a morphism from C into every box in B(Σ) in such a way that the composite is exactly f , and such that the global input and output wires of ϕ correspond to a given tensor factorization of the domain and codomain of f : Definition 14 (Compatibility). For Σ a hypergraph, let ϕ be a generalized causal model as in (13). Let further for all input indices i = 1, . . . , n and output indices j = 1, . . . , k.
This generalizes the functorial definition of causal models as first studied in [8]. Note that the functor F must assign to every wire type (i.e., wire in Σ) a corresponding object in the category C. This implies that wires in W (G) with identical types must map to the same object in C. For example, one may consider a situation where f is a probability distribution with no inputs and all output variables are real-valued. In this case, we have V ′ j = R for all j, and one may want to consider a causal model ϕ in which all wires are likewise of the same type. For the string diagrammatic picture of this definition, we refer to Section 2.2.
Similarly, the hypergraph morphism type ∶ G → Σ assigns to each box in G a specific "type" box in Σ. This means that under F , any two boxes with the same type must map to the same morphism in C. This is why generalized causal models in our sense can naturally incorporate the condition that several causal mechanisms must be the same, namely when choosing the types in a way enforcing this. This has already been highlighted in our discussion of gs-monoidal string diagrams (see Example 5).
In the following, we denote for every wire X ∈ W (G) in ϕ the corresponding object F (type(X)) in C by X ′ . Similarly, for every set of wires W ⊆ W (G) in ϕ, we denote the corresponding multiset of wires in C by W ′ . For the rest of the paper, we will associate this multiset with the corresponding tensor product in C obtained by tensoring its elements, where we ignore the question of how to order the factors.

C
In this section, we review a central assumption to prove the d-separation criterion, namely the existence of conditionals. Moreover, we introduce a string diagrammatic definition of conditional independence.

Existence of conditionals.
To use the d-separation criterion to detect causal compatibility, we need in addition the existence of conditionals. This notion has been studied in categorical terms in [4] in a special case, where the authors call it admitting disintegration, and subsequently in [11] in general. In the following, we briefly review the definition following [11,Section 11].
Definition 15. Let C be a Markov category. We say that C has conditionals if for every mor- Note that X , Y are single output spaces. However, since these can arise as products of multiple output spaces each, we use notation that suggests interpreting X and Y as multisets of spaces. Since Markov categories are symmetric monoidal, we can use the multisets or tensor product pictures interchangeably.
Examples of categories having conditionals are FinStoch, Gauss as well as BorelStoch. In contrast, Stoch does not have conditionals (see [11,] and references therein).
In the following, we prove that the deterministic Markov category FinSet and the possibilistic Markov category FinSetMulti have conditionals.

Proposition 16. FinSet and FinSetMulti have conditionals.
Proof. We show the statements separately, doing the case of single objects A, X and Y without loss of generality.
(i) In FinSet, any map f ∶ A → X × Y is uniquely determined by its components f X ∶ A → X and f Y ∶ A → Y , which are equivalently its marginals. Defining where we have used the equation which shows the statement.
Note that the proof also generalizes trivially to Set and SetMulti.

Conditional independence.
A second ingredient of the d-separation criterion is the definition of conditional independence. The following definition has been introduced in several works (see for example [4,6]) and shown to satisfy the well-known semigraphoid properties. In addition, Fritz [11] shows that it is still meaningful to define conditional independence in the absence of conditionals.
In other words, X ⊥ Y Z holds if f is compatible with the generalized causal model which corresponds to the string diagram on the right-hand side (where all boxes are of distinct type, and we leave labels off for simplicity).

Remark 18.
The conditional independence X ⊥ ∅ Z is equivalent to the existence of the conditional r Z . Therefore, if C has conditionals, then every state r satisfies X ⊥ ∅ Z for every tensor factorization of its codomain X ⊗ Z.
While conditional independence coincides with the standard definition in probabilistic Markov categories like FinStoch, Gauss or BorelStoch, we show in the following an example of conditional independence for FinSetMulti.

Example 19.
(i) Let X = Y = Z be finite sets and f (x, y, z) = δ x,y,z , where δ x,y,z = 1 if and only if x = y = z. In other words, a triple of outcomes (x, y, z) is possible if and only if x = y = z. Then f displays the conditional independence X ⊥ Y Z since f (x, y, z) = f (x z) ⋅ f (y z) ⋅ f (z), with f (z) = 1 for every z ∈ Z and f (x z) = δ x,z and f (y z) = δ y,z . Note that in this representation f (x z) and f (y z) correspond to the left and the right boxes in the decomposition of Definition 17. (ii) Let X = Y = Z be finite sets and similarly f (x, y, z) = δ x,y ⋅ δ z,z 0 for fixed z 0 ∈ Z, which has marginal f Z (z) = δ z,z 0 . Then f does not display the conditional independence X ⊥ Y Z. Assuming the contrary, we would have which cannot be the case as soon as our sets have at least two elements.
As we have already done in the previous definition, we write X , Y, . . . for arbitrary lists of objects in C. We also allow for implicit reordering of these lists-effectively identifying these lists with multisets-and omit mention of the relevant compositions of f by swap morphisms. 6 This allows us to talk about conditional independence with respect to any tripartition of the tensor factors in the codomain of any state f .
With this in mind, we now introduce a notion of conditional independence for morphisms with inputs. This notion is the key ingredient of the d-separation criterion presented in Section 6.2, and it is the categorical generalization of the transitional conditional independence introduced recently in [9, Definition 3.1].

Definition 20. A morphism
Note that the above definition of conditional independence is not symmetric, i.e. X ⊥ Y Z does not necessarily imply Y ⊥ X Z. If C has conditionals then X ⊥ Y Z rewrites to A which highlights the asymmetry. Moreover, if A is trivial, then the conditional independence coincides with Definition 17.
Due to the asymmetry, the outputs in Y might contain information about the inputs A which cannot be retrieved just from the outputs in Z. On the other hand, the outputs in X are generated using only the information from the outputs in Z. The local Markov property that we will use in Definition 33 explicitly highlights this asymmetry: the output of a box (corresponding to X ) is independent of its non-descendants (Y) given its inputs (Z). Every global input is non-descendant of any box; however, not every global input wire is directly an input to the box itself.

Example 22.
In the Markov category Set, a function f ∶ A → X × Z × Y is always such that each one of its components f X , f Y and f Z is a deterministic function of a ∈ A. Such f displays the conditional independence X ⊥ Y Z if and only if the X output can be rewritten as a function of the Z output only, i.e. x = g(z), or equivalently if and only if f X factors through f Z .

D d-
The main goal of this section is to prove that the d-separation criterion [23, Section 1.2.3] correctly detects causal compatibility not just in discrete probability but in all Markov categories with conditionals. To this end, we introduce a categorical notion of d-separation phrased in terms of connectedness of the gs-monoidal string diagram representing the causal model. We then show that this notion coincides with the classical notion of dseparation whenever the latter applies.
This part is structured as follows. In Section 6.1, we introduce the categorical notion of d-separation on generalized causal models. Moreover, we show in Proposition 28 that this notion coincides with the classical notion of d-separation for all those generalized causal models that correspond to DAGs. In Section 6.2, we first show that d-separation implies conditional independences for compatible morphisms in Markov categories with conditionals. We then show in Theorem 34 that d-separation fully characterizes causal compatibility. and a set of output wires Z ⊆ out(ϕ), we define a new gs-monoidal string diagram Cut Z (ϕ) obtained by removing the wires in Z in the following sense. Its underlying hypergraph H is such that the set of boxes is the same, B(H) ∶= B(G), while the set of wires is W (H) ∶= W (G) ∖ Z. Each box has the same input and output wires as before, expect in that those in Z are simply removed, which lowers the arities of the boxes correspondingly. We also remove all occurrences of wires in Z from the global inputs and outputs, and this results in a gs-monoidal string diagram where n ′ ⊆ n, m ′ ⊆ m and p ′ , q ′ are the restrictions of p and q, respectively. Note that Cut Z (ϕ) is generally not a morphism in FreeMarkov Σ anymore since it is not normalized. However, it can be understood as a morphism in FreeGS H . Example 25 will present a few examples. We next introduce some notation for paths of wires.

Definition 23. Let ϕ be a gs-monoidal string diagram in FreeGS Σ . (i) An undirected path between two wires X, Y ∈ W (G) is a sequence of wires
together with a sequence of boxes b 1 , . . . , b n ∈ B(G) such that If there exists an undirected path between X and Y , then we write X − Y .
(iii) For two wires A, B ∈ W (G), we write A ↠ B if there exists a sequence of wires W 1 , . . . , W n ∈ W (G) such that Thus, an undirected path in ϕ may traverse a box not just from input or output or vice versa, but also from input to input or output to output.
The intuitive idea behind the following definition of d-separation, as already briefly discussed in [12,Remark 7.2], was communicated to us by Rob Spekkens. (Categorical d-separation). Let ϕ be a generalized causal model. For three disjoint sets of output wires X , Y, Z ⊆ out(ϕ), we say that Z d-separates X and Y if

Definition 24
has no undirected path between any output in X and any output in Y.
Here, ϕ W ∶= norm(del W c ○ ϕ) with W c = out(ϕ) ∖ W denotes the marginal on W in FreeMarkov Σ . The absence of an undirected path as in the definition manifests itself in the string diagrams simply as topological disconnectedness.

Example 25.
The following examples constitute the basic components of "classical" dseparation 7 and illustrate the simplicity of categorical d-separation. In all cases, the unlabeled boxes denote distinct generators, i.e. distinct boxes in the generating hypergraph Σ.
(i) Fork: consider the morphism has disconnected X and Y . (ii) Chain: consider the morphism has disconnected X and Y .
(iii) Collider: consider the morphism and therefore which still contains an undirected path X − Y . The same reasoning applies when which has disconnected X and Y . Therefore ∅ d-separates X and Y . (iv) Consider the morphism This morphism differs from (i) by adding an independent process A → W . The normalized marginal ϕ X,Y,Z is given by which again shows that Z d-separates X from Y since cutting Z makes X and Y disconnected.
In order to define the classical notion of d-separation, we note that certain gs-monoidal string diagrams have an underlying DAG, given by using wires as nodes and taking the edges to be → as in Definition 23. We use the term DAG path to refer to an undirected path in this DAG, i.e. to a sequence of wires connected by boxes from input to output or vice versa (but not from input to input or output to output). For example, in the string diagram there are two undirected paths witnessing W 1 − W 3 , namely on the one hand the direct path W 1 , W 3 and on the other hand the indirect W 1 , W 2 , W 3 . Only the second is a DAG path since its two steps are input to output and output to input, while going from W 1 to W 3 directly would be input of b to input of b. We also define the ancestor wires of a given set of wires as An(X ) = {U ∈ W (G) ∶ ∃X ∈ X such that U ↠ X} and the set of descendant wires as where A ↠ B is defined in Definition 23(iii). Note that X ⊆ An(X ), Dec(X ). To state the following classical definition [23, Definition 1.2.3] in our language, we restrict further to those generalized causal models that are determined by their underlying DAGs. As noted in Remark 11, a causal structure ϕ is represented by a DAG, if the string diagram is pure bloom, every box has exactly one output, and it has no global inputs, i.e. in(ϕ) = ∅. (Classical d-separation). Let ϕ be a pure bloom causal model with in(ϕ) = ∅ and such that every box has exactly one output. Then:

Definition 26
(a) A DAG path p in ϕ is called d-separated by a set of wires Z ⊆ out(ϕ) if at least one of the following two conditions holds: We will now prove the equivalence of categorical d-separation with classical d-separation for the class of causal models on which the latter is defined. This requires some preparation.

Lemma 27.
Let ϕ be a pure bloom causal model, b ∈ B(G) a box in ϕ and W ⊆ out(ϕ) a subset of its wires. The following statements are equivalent: Proof. (ii) ⇒ (i): To prove the contrapositive, assume ∃A ∈ out(b) such that A ∈ An(W).
Then there is a path A ↠ W with W ∈ W. Since W is still an overall output that does not get discarded, this path is still valid in del W c ○ ϕ. Therefore b remains in norm(del W c ○ ϕ).
(i) ⇒ (ii): Consider the set Dec(out(b)). By assumption, we have that Dec(out(b)) ∩ An(W) = ∅. We show that the box b gets discarded in norm(del Dec(out(b)) ○ ϕ), which is enough because of W c ⊇ Dec(out(b)). By definition of Dec(out(b)), there exists a final box 8 b such that out(b) ⊆ Dec(out(b)). This shows thatb gets discarded in norm(del Dec(out(b)) ○ϕ).
Defineφ ∶= norm(del Dec(out(b)) ○ ϕ). Repeating the above procedure withφ, we arrive after finite number of steps at b itself being a final box. Since it is then eliminable after composing with del Dec(out(b)) , it indeed no longer appears in the normalization.
We now show the promised equivalence result between categorical d-separation and classical d-separation in the cases where ϕ represents a causal structure given by a DAG, i.e. in(ϕ) = ∅ and every box has a single output.

Proposition 28.
Both concepts of d-separation coincide on pure bloom causal models ϕ with in(ϕ) = ∅ and in which every box has exactly one output.
Proof. To make the proof more intuitive, we introduce the term d-connected as the negation of d-separated (in either version).
We start by showing that classical d-connectedness implies categorical d-connectedness. Let p be a DAG path between some X ∈ X and some Y ∈ Y which witnesses that Z makes X and Y be d-connected in the classical sense, which means that the following hold: For simplicity, we also assume without loss of generality that p contains only one wire from X and Y each, say X and Y respectively. Then this p can also be interpreted as an undirected path in ϕ, but generally not in ϕ cut ∶= Cut Z (ϕ X ,Y,Z ) since it may traverse wires that are not in ϕ cut . However, we now show that there still is an undirected path p ′ between X and Y in ϕ cut . Since p is d-connected, if p contains a wire Z ∈ Z, then it has to arise from a collider U → Z ← W in p. Removing wire Z from p still defines a valid undirected path between X and Y , pictorially: We prove that the path p ′ obtained by removing all wires in Z from p like this is an undirected path in ϕ cut , which implies categorical d-connectedness. To this end, it only remains to show that each wire in p ′ is an existing wire in ϕ cut , which we do as follows: (i) X and Y themselves are still in ϕ cut .
(ii) Every Z ∈ Z in p is part of a collider U → Z ← W as above, so that U, W ∈ An(Z). This implies that U and W survive in ϕ X ,Y,Z by Lemma 27. (iii) Since U and W are themselves either the middle node in a chain or fork or the start or end of p, we have U, W ∈ Z. This implies U, W ∈ An(Z) ∖ Z, and therefore U and W survive also in ϕ cut . (iv) For every chain W → M → U in p, if U survives in ϕ cut , then so does M (since it survives in ϕ X ,Y,Z and M ∈ Z). (v) For every fork W ← M → U in p, if U or W survives in ϕ cut , then so does M (since it survives in ϕ X ,Y,Z and M ∈ Z). Since the wires in p ′ are exactly those of p minus some of the colliders, we can start with the first two observations and then apply the latter two repeatedly on any segment bounded by colliders or the starting node X or the final node Y in order to conclude that all wires in p ′ are present in ϕ cut . This concludes one direction of the proof.
The converse direction of showing that categorical d-connectedness implies classical dconnectedness works similarly. Let p be an undirected path between X ∈ X and Y ∈ Y in ϕ cut . We assume without loss of generality that all wires in p are distinct. Furthermore, we also assume without loss of generality that p is of the form, in terms of the notation from Definition 23(iii), where every wire that is in between A and B is not contained in An(X ) or An(Y), or equivalently that every wire in p that is also in An(X ) is directly reached from X by outputto-input traversals in p, and similarly for all wires in An(Y). This property can be achieved by taking every wire in p which is additionally in An(X ) and replace it with the path from X to it by a sequence of output-to-input traversals, and similarly for every wire in An(Y). Note that this replacement may involve changing the starting and ending wires X and Y as well.
In order to turn p into a DAG path p ′ that witnesses classical d-separation, we need to remove all direct input-to-input traversals of a box in p; direct output-to-output traversals cannot occur due to the assumption that every box has exactly one output. We can hence simply add to p the unique output wire of every box that has an input-to-input traversal in p, and we obtain a valid DAG path p ′ .
It remains to verify the conditions on chains, forks and colliders. Clearly, p ′ does not contain any chain W → Z → U or fork W ← Z → U with Z ∈ Z since such a configuration cannot occur in p to begin with. For a collider W → M ← U , the unique box which outputs M must be contained in ϕ X ,Y,Z , and therefore be in An(X ∪Y ∪Z) by Lemma 27. However, M being in An(X ) or An(Y) violates the assumption that p is of the form (19). Therefore M has to be in An(Z), showing the collider condition (ii).
We record one more observation on categorical d-separation for further use below.
Lemma 29. Let ϕ be a pure bloom causal model and X , Y, Z ⊆ out(ϕ) a partition of all output wires such that Z categorically d-separates X and Y. Then every box b ∈ B(G) in ϕ satisfies at least one of the cases: Proof. If there exist Y ∈ Y ∩ out(b) and X ∈ X ∩ out(b), then these wires are still in the output of b in ϕ cut , and this contradicts the assumed disconnectedness of ϕ cut with respect to X and Y. Since X , Y, Z form a partition, this shows that either out(b) ⊆ X ∪ Z or Since ϕ is a pure bloom we have that in(b) ⊆ out(ϕ) which guarantees that works similarly to the first part of the proof, and this then proves the statement.
Pictorially, Lemma 29 shows that if Z d-separates X and Y, then every box b in ϕ is of the form 6.2. Causal compatibility. In the following, we show that d-separation implies conditional independence for any generalized causal model. We first prove this result for a partition of wires in a pure bloom causal model in Lemma 30. We then refine it to any disjoint collection of wires in Corollary 32 in any generalized causal model. Finally, we show in Theorem 34 that d-separation fully characterizes causal compatibility for pure bloom causal models in all Markov categories with conditionals.
Throughout, we also use the following convenient notation: If a morphism f in C is compatible with a causal model ϕ in the sense of Definition 14, then we refer to the wires of ϕ to indicate conditional independence instead of the objects in the tensor factorization of f . In other words, instead of writing X ′ ⊥ Y ′ Z ′ , we simply write X ⊥ Y Z. Here, each W ′ = F (type(W )) is the object in C associated with the wire W by the causal model functor F (see Definition 14).
Lemma 30. Let C be a strict Markov category with conditionals, and let ϕ be a pure bloom causal model. Further, let X , Y, Z ⊆ out(ϕ) be a partition of wires in ϕ such that in(ϕ) ⊆ Y ∪ Z and X and Y are d-separated by Z.
If a morphism f in C is compatible with ϕ, then X ⊥ Y Z (as in Definition 20).
Proof. Choose a total ordering of all boxes b 1 , . . . , b k−1 ∈ B(G) and a chain of sets of wires in out(ϕ), in FreeMarkov Σ , where η i is again a pure bloom and η 1 is an identity morphism. The existence of such a chain of sets follows easily by induction on the number of boxes based on the existence of a final box [12,Lemma 4.6]. 9 Then for every i ∈ {1, . . . , k}, we show the existence of a decomposition 10 Since W c k = ∅, setting i = k proves the desired statement. We prove this stronger claim by induction on i. The start of the induction at i = 1 is trivial since η 1 is the identity and therefore For the induction step, we prove the statement at i + 1.
Since ϕ is pure bloom and since An(W i+1 ) = W i+1 , we can peel off the box b i with W i+1 = 10 Note that we assume, without loss of generality, that every box in the string diagram depends on every variable in the collection of wires. For example, ki depends on every variable in Z ∩ Wi. If this is not the case, say, ki does not depend on W ∈ Z ∩ Wi, we replace it by k ′ i = ki ○ (id ⊗ del W ).
out(b i ) ∪ W i from ψ i , so as to achieve the decomposition where we have used the induction assumption to obtain a decomposition as in the lower half, and the dashed wires indicate that only some of them may be present since the inputs of b i are an unspecified subset of W i . By Lemma 29 we have to distinguish two cases: Then, the third dashed wire in the above decomposition of f is not needed, and we consider the morphism g ∶= which is part of that decomposition. By the existence of conditionals, we can rewrite g in the form where both lower boxes can be refined with internal structure consisting of carrying (Z ∩W i ) ′ forward on a separate wire, but this internal structure is not relevant for the remainder of the proof. Substituting this form of g into Equation (21), i.e.
replacing the morphism k i there with the box r i here and merging the box ℓ i here with h i there, proves the induction step.
Then, the first dashed wire in the above decomposition of f is not needed, and we can merge F (b i ) with h i , which shows the statement.
We will now generalize Lemma 30 to all generalized causal models and to arbitrary disjoint sets X , Y and Z which do not necessarily partition the set of all wires.
Lemma 31. Let ϕ be a generalized causal model and X , Y, Z ⊆ out(ϕ) a tripartition of output wires in ϕ such that in(ϕ) ⊆ Y ∪ Z and such that Z categorically d-separates X and Y. Then there exists a tripartition of wiresX ⊇ X ,Ỹ ⊇ Y, Z in the pure bloom version ϕ pure-bloom of ϕ 11 such that Z d-separatesX andỸ in ϕ pure-bloom By definition,X ,Ỹ, Z form a tripartition of wires in ϕ pure-bloom . Moreover,X andỸ are categorically d-separated by Z since any path in Cut Z (ϕ pure-bloom ) is a valid path in Cut Z (ϕ) and vice versa.
Corollary 32. Let C be a strict Markov category with conditionals, and let ϕ be a generalized causal model. 12 Further, let X , Y, Z ⊆ out(ϕ) be disjoint sets of output wires in ϕ such that in(ϕ) ⊆ Y ∪ Z and X and Y are d-separated by Z. If f is compatible with ϕ, then X ⊥ Y Z.
In this statement, we use another standard convention: when the disjoint sets X , Y, Z do not partition the set of wires of ϕ, then the conditional independence X ⊥ Y Z is to be understood as Definition 20 applied to the corresponding marginal Proof. We prove this statement by reducing it to the case of pure bloom causal models treated in Lemma 30.
Consider the restricted causal model ψ ∶= ϕ X ,Y,Z . We have that f X ′ ,Y ′ ,Z ′ = F (ψ) since F is a Markov functor. By the definition of categorical d-separation, Z d-separates X and Y also in ψ. Let ψ pure-bloom be the pure bloom version of ψ. Since f X ′ ,Y ′ ,Z ′ is compatible with ψ, we can extend it to a pure bloom version By Lemma 31, for ψ pure-bloom there is a tripartition of output wiresX ⊇ X ,Ỹ ⊇ Y, Z such that Z d-separatesX andỸ. Since C has conditionals, Lemma 30 provides us with 11 The pure-bloom version ϕ pure-bloom is obtained by copying each wire so to make it into an output. It is part of the bloom-circuitry factorization of [12]. 12 In this situation ϕ does not need to be pure bloom. a decomposition of the form By marginalizing overX ′ ∖X ′ ,Ỹ ′ ∖Y ′ in g, we obtain the desired conditional independence for the marginal f X ′ ,Y ′ ,Z ′ .
Note that this result includes the soundness of the classical d-separation criterion in the classical case of discrete random variables in Bayesian networks 13 , which is obtained upon restricting to pure bloom causal models with in(ϕ) = ∅, the Markov category FinStoch, and every box having precisely one output since then conditional independence reduces to Definition 17 by Remark 21.
Definition 33. Let ϕ be a generalized causal model and f a morphism in a strict Markov category C (not necessarily having conditionals). Then we say that f satisfies: (i) the global Markov property with respect to ϕ if for every three disjoint sets of outputs Theorem 34. Suppose that we are given the following: • C is a strict Markov category with conditionals.
• ϕ is a pure bloom causal model over a hypergraph Σ such that the boxes in ϕ have distinct where ψ is another causal model satisfying all of our assumptions, and no box in ψ has the same type in Σ as b does.
In order to construct a functor F as in Definition 14, note first that it must satisfy (16), which already lets us write the domain of f as in(ϕ) ′ , and similarly for the codomain. Since f satisfies the local Markov property with respect to b, we can decompose f by Definition 20 as By induction hypothesis, we have that g is compatible with ψ since g satisfies the local Markov properties specified by ψ. Since the box b appears only once in ϕ, we can freely define the action of the functor F on b as F (b) ∶= h. Then, we obtain where we use in the first step Equation (22) and in the last the fact that F is a Markov functor.

Remark 35.
(i) Note that we have used the assumption that C has conditionals only for the implication (i) ⇒ (ii). Therefore, for an arbitrary strict Markov category, the global as well as the local Markov property is a sufficient condition for the compatibility of a morphism with a generalized causal model (satisfying our assumptions). However, these Markov properties implicitly require the existence of This shows that the conditional f Z exists, and this recovers the box that outputs M (up to almost sure equality). (ii) Theorem 34 shows that d-separation correctly detects causal compatibility for the Markov categories FinStoch, Gauss or BorelStoch. For the Markov category Stoch, which does not have conditionals, the global and local Markov properties are at least sufficient for the compatibility since our proof of these implications has not used conditionals. (iii) Note that Theorem 34 only applies to causal models where each box appears at most once in the model (which in particular implies that ϕ has no nontrivial symmetries). However, the implication (i) ⇒ (ii) applies to arbitrary generalized causal models as proven in Corollary 32.
Example 36. We now present three examples that go beyond the classical d-separation criterion. In (i) we study a causal structure that does not arise from a DAG, in (ii) we study a DAG causal structure with continuous and possibilistic variables, and in (iii) we study a causal structure with inputs with deterministic variables.
(i) Let ϕ be the causal structure We claim that such a distribution is compatible with ϕ if and only if there exist morphisms d and d ′ such that where s is the first marginal of r, and similarly d ′ ∶ Z ′ 2 → Z ′ 1 satisfies the same equations the other way around. Here, the second equation states that the morphism d is s-a.s. deterministic [11,Definition 13.11], and similarly for d ′ .
Indeed, assuming compatibility we have that which shows the first equality in Equation (23). For the second equality we have that where we have used the conditional independence Z 2 ⊥ X Z 1 in the first step and Equation (24) in the second step. Since the morphism is symmetric with respect to permutations of the output wires X and Z 2 , we have a = F (f ) s-a.s. which shows the second equality in Equation (23). Proving the existence of d ′ works analogously by interchanging the roles of X and Y as well as Z 1 and Z 2 .
Conversely, we have where we have used the assumption that d is s-a.s. deterministic in the second equation. Repeating this calculation interchanging the roles of Z 1 and Z 2 as well as X and Y shows the statement. (ii) Consider the instrumental scenario, given by the DAG

A B
Λ X This has been previously studied mainly in the context of DAGs with latent variables [22,3]. For our analysis, we assume each variable to be observed, which means that the causal structure reads string diagrammatically as There are two non-trivial d-separations: (a) Between X and B by {A, Λ}, (b) Between X and Λ. Therefore, Theorem 34 implies that a distribution P on a four-fold tensor product object in a Markov category with conditionals is compatible with ϕ if and only if X ⊥ B A, Λ and X ⊥ Λ.
In BorelStoch, this means that P is compatible with ϕ if and only if P (X ∈ E 1 , A ∈ E 2 , B ∈ E 3 , Λ ∈ E 4 ) = E 2 E 4 P X A,Λ (X ∈ E 1 a, λ) P B A,Λ (B ∈ E 3 a, λ) P A,Λ (da, dλ) and P (X ∈ E 1 , Λ ∈ E 4 ) = P (X ∈ E 1 ) ⋅ P (Λ ∈ E 4 ) where E i are measurable sets in the Borel σ-algebras of the spaces X ′ , A ′ , B ′ and Λ ′ . For simplicity, assume that all random variables take values in R and are absolutely continuous, i.e. there exists a density f ∶ The causal compatibility now amounts to the following two conditions: (a) X ⊥ Λ, i.e. f X,Λ (x, λ) = f X (x) ⋅ f Λ (λ) a.e.
where a.e. means almost everywhere with respect to the Lebesgue measure on R. (b) X ⊥ B A, Λ, i.e.
which is the usual factorization condition for compatibility with the causal structure in (25).
In FinSetMulti, the same observation implies that a morphism