2.1 The positivity axiom

Here, we recall the definition of a positive Markov category. Readers familiar with this material may proceed directly to Section 2.2.

Definition 2.1. A Markov category $\textsf{C}$ is positive if whenever $f \colon X\to Y$ and $g \colon Y\to Z$ are such that $g \circ f$ is deterministic, then we have

(16)

The positivity property was introduced under this name in Fritz (Reference Fritz2020) because the proof that it holds in $\textsf{Stoch}$ relies importantly on the nonnegativity of probabilities. It was also observed there that positivity follows from the existence of conditionals. Moreover, positivity fails in $\textsf{FinStoch}_\pm$ (Fritz Reference Fritz2020, Example 11.27), which provides a nice way to see that $\textsf{FinStoch}_\pm$ does not have conditionals.

Since this class of morphisms is closed under composition, tensor product and contains all the structure morphisms of $\textsf{FinStoch}_\pm$ , it follows that it is a Markov category in its own right. To see that every isomorphism is deterministic, note that a stochastic matrix of rank 1 is not invertible unless its domain and codomain are both singletons, in which case its only entry must be 1. To see that positivity fails, consider e.g.

(17) \begin{equation} f = \left( \begin{matrix} 1 \\ 1 \\ -1 \end{matrix} \right), \qquad g = \left( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix} \right), \end{equation}

for which $g \circ f$ is deterministic, but Equation (16) does not hold.

2.2 Deterministic marginal independence is equivalent to positivity

In probability theory, it is an obvious fact that a deterministic random variable is independent of any other random variable. This fact has previously made a brief appearance in the Markov categories framework in Fritz (Reference Fritz2020, Proposition 12.14). Here is the general definition.

Definition 2.4. A Markov category $\textsf{C}$ satisfies deterministic marginal independence (DMI) if for every deterministic morphism $p \colon A \to X$ , every dilation $\pi \colon A \to X \otimes E$ of p displays the conditional independence of X and E given A, i.e.

(18)

Equivalently, DMI says that every morphism $A \to X \otimes E$ that has a deterministic marginal (say, on X) must display conditional independence of X and E given A.

Note that the term “deterministic marginal independence” is intended to be understood as “(deterministic marginal) independence,” not as “deterministic (marginal independence).”

In words, deterministic marginal independence states that a deterministic output of a process cannot be correlated with another output. The following example already illustrates that this property is also related to the nonnegativity of probabilities.

Example 2.5. (DMI for stochastic matrices). $\textsf{FinStoch}$ satisfies deterministic marginal independence. For instance, consider trivial input $A = I$ , so that $\pi$ is a joint distribution of X and E. Deterministic states in $\textsf{FinStoch}$ are point distributions, so that we have $p = \delta_{x_0}$ for some $x_0 \in X$ . The assumption that $\pi$ dilates p means that for $x \in X$ ,

(19) \begin{equation} \sum_{e \in E} \pi(x,e) = \begin{cases} 1 & \text{if } x = x_0, \\ 0 & \text{otherwise} \end{cases} \end{equation}

holds. By the nonnegativity of probabilities, this implies that $\pi(x,e)$ vanishes for all e whenever $x \neq x_0$ . Consequently, the other marginal of $\pi$ is given by

(20) \begin{equation} \pi_E(e) = \pi(x_0,e), \end{equation}

and the whole joint distribution can be written as

(21) \begin{equation} \pi(x,e) = \delta_{x_0}(x) \cdot \pi(x_0, e) = p(x) \cdot \pi_E(e) \end{equation}

which is precisely the desired Equation (18). For more general morphisms, the same holds, where now both p and $\pi$ depend on an additional parameter.

Another closely related notion is the following one.

Definition 2.6. A morphism $q \colon A\to X\otimes E$ is deterministic in X if and only if it satisfies

(22)

Discarding the output E shows that if q is deterministic in X, then its marginal $q_X$ is deterministic. However, the converse does generally not hold, as the following example shows.

Example 2.7. (Deterministic marginals with negative probabilities). In $\textsf{FinStoch}_\pm$ , a joint distribution $q \colon 1\to X\otimes E$ is deterministic in X if and only if for all outcomes $x_1, x_2 \in X$ and $e \in E$ , we have

(23) \begin{equation} \delta_{x_1, x_2} \cdot q(x_2, e) = q_X(x_1) \cdot q(x_2, e) . \end{equation}

In $\textsf{FinStoch}$ , this property is equivalent to the marginal $q_X$ being deterministic; this is an instance of Theorem 2.8 below. In $\textsf{FinStoch}_\pm$ , instead, there are joint distributions q which are not deterministic in X although their marginal $q_X$ is deterministic. For example, for $X = \{x,y\}$ and $E = \{a,b\}$ , taking the signed distribution with joint probabilities given by

(24) \begin{equation} \begin{array}{c|cc} q & a & b \\ \hline x & 1/2 & 1/2 \\ y & 1/2 & -1/2 \end{array} \end{equation}

has marginal $q_X$ equal to $\delta_x$ , which is deterministic. However, setting $x_1=x_2=y$ and $e=a$ in (23) results in

(25) \begin{equation} 1\cdot 1/2 \ne 0 \cdot 1/2 . \end{equation}

The culprit is that the marginal $q_X$ gives mass zero to y, but the joint probability q gives nonzero mass to the point (y,a). This is possible because in this category we are allowing negative probabilities, and some mass cancels out when we form the marginal.

Proof. : This was proven as Fritz (Reference Fritz2020, Proposition 12.14), we recall the argument here for completeness. If p is deterministic, then in the defining Equation (16) we take a dilation $\pi$ thereof in place of f and the morphism

(26)

in place of g. Then the composite $g \circ f$ is equal to p, which is deterministic by assumption. Equation (16) now reads

(27)

We then get the desired conditional independence by marginalizing over the leftmost output and swapping the other two,

(28)

implicitly using the commutativity of $\textrm{copy}$ .

: Consider $f \colon A\to X$ and $g \colon X\to Y$ with a deterministic composite $g \circ f$ . Then the morphism

(29)

is a dilation of its Y-marginal $g \circ f$ , which is deterministic by assumption. Therefore deterministic marginal independence applies and gives

(30)

as was to be shown.

: We already noted that determinism in X of q always implies that its X-marginal $q_X$ is deterministic, so we focus on the backward implication, assuming that $\textsf{C}$ satisfies DMI.

Consider a morphism $q\colon A \to X \otimes E$ with deterministic marginal $q_X$ . By DMI, q displays the conditional independence of X and E given A. Using both of these properties entails

(31)

so that q is indeed deterministic in X. The first and last equations hold because of the conditional independence; the second one uses the fact that $q_X$ is deterministic; and the third one holds by associativity of copying.

: Let $\pi \colon A\to X\otimes E$ be a dilation of a deterministic morphism $p \colon A \to X$ . Then $\pi$ is necessarily deterministic in X by the assumed Property (iii). Marginalizing the middle output in Equation (22) gives

(32)

which is the desired conditional independence.

Remark 2.9. Let us call a morphism $p \colon A \to X$ globally deterministic if every dilation of p is deterministic in X. We can then express Property (iii) as saying

(33) \begin{equation} \textsf{C}_\textrm{det} = \textsf{C}_\textrm{gd} \end{equation}

where $\textsf{C}_\textrm{gd}$ denotes the class of globally deterministic morphisms in $\textsf{C}$ .

As a consequence of Theorem 2.8, Example 2.7 corresponds to the failure of positivity in $\textsf{FinStoch}_\pm$ as noticed in Fritz (Reference Fritz2020, Example 11.27).

We can also use Theorem 2.8 to establish the conditions under which Markov categories of semiring-valued stochastic matrices from Example 1.4 are positive. First, let us characterize the deterministic morphisms therein. To that end, recall that a commutative semiring R is entire if $0 \neq 1$ and if R has no zero divisors in the sense that

(34) \begin{equation} rs = 0 \quad \implies \quad r = 0 \;\text{ or }\; s = 0 \end{equation}

holds.

Lemma 2.10. Let R be an entire commutative semiring. A morphism $f \colon A \to X$ in ${\textsf{Kl}}(D_R)$ is deterministic if and only if it can be expressed as

(35) \begin{equation} f(x | a) = \delta_{f^{\flat}(a)}(x) \end{equation}

for a function $f^{\flat} \in {\textsf{Set}}(A,X)$ , where $\delta_{x'} \in D_R(X)$ is the delta distribution given by

(36) \begin{equation} x \mapsto \begin{cases} 1 & \text{if } x = x', \\ 0 & \text{if } x \neq x' . \end{cases} \end{equation}

Moreover, $f^\flat$ is then uniquely determined by f.

In other words, deterministic morphisms of ${\textsf{Kl}}(D_R)$ coincide with its pure morphisms in the sense of Moss and Perrone (Reference Moss and Perrone2022, Definition 2.5). However, they do not necessarily coincide with pure or dilationally pure morphism in the sense of Selby et al. (Reference Selby, Scandolo and Coecke2021) and Houghton-Larsen (Reference Houghton-Larsen2021), respectively. Note that the function $f^{\flat}$ is unique by $1 \neq 0$ in R.

Proof. Since every morphism of that form is clearly deterministic, it suffices to show the forward implication. Let f be deterministic, meaning that

(37) \begin{equation} f(x | a) \, f(x' | a) = f(x | a) \, \delta_{x'}(x) \end{equation}

holds for all $a \in A$ and all $x,x' \in X$ . For every a there is an x with $f(x | a) \neq 0$ . Since R has no zero divisors by assumption, Equation (37) which takes the form $f(x | a) \, f(x' | a) = 0$ then implies $f(x' | a) = 0$ for every x’ distinct from x. Normalization then forces $f(x | a) = 1$ , so that f satisfies Equation (35).

The uniqueness is clear by $0 \neq 1$ in R; equivalently, the canonical Kleisli functor ${\textsf{Set}} \to {\textsf{Kl}}(D_R)$ is faithful.

While the proof of Lemma 2.10 is instructive, it is worth noting that this statement also follows from Fritz et al. (Reference Fritz, Gonda, Perrone and Rischel2023, Propositions 3.4 and 3.6), which in turn also implies that the Markov category ${\textsf{Kl}}(D_R)$ is representable.^{Footnote 3}

Definition 2.11. A semiring R is zerosumfree if it satisfies

(38) \begin{equation} r + s = 0 \quad \implies \quad r = s = 0 \end{equation}

for all $r,s \in R$ .

This generalizes the fact that ${\textsf{FinStoch}}_\pm$ is not positive and can be taken as further motivation for the term “positivity”.

First, assume that R is zerosumfree and consider a dilation $\pi \colon A \to X \otimes E$ of a deterministic $p \colon A \to X$ . By Lemma 2.10, we have

(39) \begin{equation} \sum_{e \in E} \pi(x,e|a) = p(x | a) = \delta_{p^{\flat}(a)}(x). \end{equation}

Therefore by zerosumfreeness we have $\pi(x,e|a) = 0$ for every $e \in E$ and every $x \in X$ distinct from $p^\flat(a) \in X$ . This means that

(40) \begin{equation} \pi(x,e|a) = \delta_{p^{\flat}(a)}(x) \, \tilde{p}(e|a) \end{equation}

holds, where $\tilde{p} \colon A \to E$ is the E-marginal of $\pi$ . But this is precisely the statement of deterministic marginal independence.

Conversely, assume that R is not zerosumfree, i.e., that there exist r and s such that $r + s = 0$ and $r \neq 0$ . Consider a morphism $\pi \colon I \to X \otimes E$ with $X = \{x,x'\}$ and $E = \{e, e'\}$ , given by the joint distribution $\pi \in D_R(X \times E)$ with

(41) \begin{align} \begin{aligned} \pi(x, e) &= 1, \\ \pi(x, e') &= 0, \end{aligned} && \begin{aligned} \pi(x', e) &= r, \\ \pi(x', e') &= s. \end{aligned} \end{align}

Then the marginal $p := \pi_X$ is deterministic. However, $\pi$ is not equal to the product of its marginals, since the latter is instead given by

(42) \begin{align} \begin{aligned} \pi_X (x) \, \pi_E(e) &= 1 + r, \\ \pi_X (x) \, \pi_E(e') &= s, \end{aligned} && \begin{aligned} \pi_X (x') \, \pi_E(e) &= 0, \\ \pi_X (x') \, \pi_E(e') &= 0. \end{aligned} \end{align}

This means that ${\textsf{Kl}}(D_R)$ does not satisfy deterministic marginal independence and thus it is not positive.

2.3 Positivity of representable Markov categories

We will show next that the following existing notion can be used to detect the positivity of a representable Markov category, in terms of the associated commutative monad on the cartesian monoidal category $\textsf{C}_\textrm{det}$ of deterministic morphisms.

Definition 2.13. (Jacobs Reference Jacobs2016, Definition 1). A strong monad $(P,\mu,\delta)$ with strength s on a cartesian monoidal category $\textsf{D}$ is strongly affine if for all objects X and Y of $\textsf{D}$ , the diagram

(43)

is a pullback in $\textsf{D}$ , where $\pi_1$ is the projection map.

Taking $X = Y = 1$ shows that a strongly affine monad is in particular affine (satisfies $P1 \cong 1$ ). Therefore the adverb “strongly” cleverly refers to both a strengthening of affineness and to the fact that the condition involves the strength s.

In a representable Markov category, a morphism $p \colon A \to X$ is deterministic if and only if it satisfies $p^\sharp = \delta p$ (Fritz et al. Reference Fritz, Gonda, Perrone and Rischel2023, Proposition 3.12). For the remainder of the proof, we work in $\textsf{C}_\textrm{det}$ only. Then by the previous statement, a given $q \colon A \to X \times Y$ has deterministic first marginal $q_X$ if and only if there exists $f \colon A \to X$ (namely $q_X$ ) such that the diagram

(44)

commutes. Now, if the square (43) is a pullback, then q factors (uniquely) through the strength s, i.e. there exists a unique morphism $u \colon X\to Y\times PZ$ making the diagram

(45)

commute. By the universal property of the product $X\times PY$ in $\textsf{C}_\textrm{det}$ , the map u is determined by its components. Its X-component must be equal to $q_X$ and its PY-component must be equal to the marginal $q_Y^\sharp$ in order for the diagram to commute. Indeed, since the diagram

(46)

commutes, we have that $\pi_2\circ u = P(\pi_2)\circ s \circ u = P(\pi_2)\circ q^\sharp = q_Y^\sharp$ . Recall now that the strength s is given by the following composition,

(47)

where $\nabla$ denotes the lax symmetric monoidal structure morphism of P. Therefore, if (43) is a pullback, then we get

(48) \begin{equation} q^\sharp = s\circ u = \nabla\circ (\delta\times\textrm{id}) \circ (f,q_Y^\sharp) = \nabla \circ ( q_X^\sharp, q_Y^\sharp). \end{equation}

Sampling on both sides produces the desired factorization of Equation (18). Since q was arbitrary, it follows that $\textsf{C}$ has deterministic marginal independence.

The converse implication follows by the same line of argument upon noting that the above reasoning covers every instance of the universal property of the pullback in $\textsf{C}_\textrm{det}$ .

2.4 Causality and positivity

We now turn to another important information flow axiom: causality (Fritz Reference Fritz2020, Definition 11.31).

Definition 2.15. (Fritz Reference Fritz2020, Definition 11.31). A Markov category $\textsf{C}$ is causal if whenever $f \colon A\to W$ , $g \colon W\to X$ and $h_1,h_2 \colon X\to Y$ satisfy

(49)

then we also have the stronger equation

(50)

Intuitively, the axiom states that if a choice between $h_1$ and $h_2$ in the “future” of g does not affect anything that happens from there on, then this choice cannot affect anything that happened in the “past” of g either.

To show that causality is a stronger property than the positivity axiom, it is helpful to have an alternative formulation thereof. The following definition elaborates on Fritz (Reference Fritz2020, Remark 11.36).

Definition 2.16. A Markov category $\textsf{C}$ has parametrized equality strengthening if for any $h_1,h_2 \colon X \to Y$ and any $p \colon A \to X$ ,

(51)

implies that for every dilation $\pi$ of p with environment E, we have

(52)

Definition 2.16 extends the notion of equality strengthening given by Cho and Jacobs (Reference Cho and Jacobs2019, p. 19), who considered the special case in which p has trivial input, meaning that $A = I$ .

Proof. The proof amounts to reinterpreting the terms in the respective equalities.

: Consider $h_1$ , $h_2$ , and p satisfying Equation (51) and an arbitrary dilation $\pi \colon A \to X \otimes E$ of p. If we define

(53)

then Equation (51) coincides with (49) and applying causality gives

(54)

which, upon marginalizing the two X outputs, gives the required Equation (52).

: Conversely, the morphism

(55)

is a particular dilation of $g \circ f \colon A \to X$ with environment $X \otimes W$ , so that applying parametrized equality strengthening to Equation (49) gives Equation (50).

Let us use Proposition Proposition 2.17 to characterize causality for Markov categories of semiring-valued stochastic matrices from Example 1.4.

Definition 2.18. An element r of a semiring R is said to have a complement $\overline{r} \in R$ if we have

(56) \begin{equation} r + \overline{r} = 1 . \end{equation}

Proposition 2.20. Let R be a commutative semiring. The Markov category ${\textsf{Kl}}(D_R)$ is causal if and only if, for all $s,t,v,w \in R$ such that s,t and $v+w$ have complements in R, we have the following implication:

(57) \begin{equation} s (v + w) = t (v + w) \quad \implies \quad s v = t v \;\text{ and }\; s w = t w \end{equation}

Proof. First, let us show that for a semiring satisfying Implication (57), the corresponding Markov category ${\textsf{Kl}}(D_R)$ has parametrized equality strengthening. Writing out Equation (51) in components gives

(58) \begin{equation} h_1(y | x) \, p(x | a) = h_2(y | x) \, p(x | a) \end{equation}

which, for any dilation $\pi$ of p, reads

(59) \begin{equation} h_1(y | x) \left[ \sum_{e \in E} \pi(x,e|a) \right] = h_2(y | x) \left[ \sum_{e \in E} \pi(x,e|a) \right] . \end{equation}

For any choice of $a \in A$ , $e \in E$ , $x \in X$ , and $y \in Y$ , let us define the following elements of R,

(60) \begin{align} \begin{aligned} s &:= h_1(y | x), \\[2pt] \overline{s} &:= \sum_{y' \neq y} h_1(y' | x), \end{aligned} && \begin{aligned} t &:= h_2(y | x), \\[2pt] \overline{t} &:= \sum_{y' \neq y} h_2(y' | x), \end{aligned} && \begin{aligned} v &:= \pi(x,e | a), \\[2pt] w &:= \sum_{e' \neq e} \pi(x,e' | a). \end{aligned} \end{align}

Then, by normalization of the respective morphisms, s and t have $\overline{s}$ and $\overline{t}$ as complements, while $v+w$ , being equal to $p(x | a)$ , has a complement too. Moreover, Equation (59) takes the form of the antecedent of Implication (57). Using this implication then gives $s v = t v$ , which reads

(61) \begin{equation} h_1(y | x) \, \pi(x,e | a) = h_2(y | x) \, \pi(x,e | a). \end{equation}

This is the componentwise form of Equation (52) that we aimed to show.

Conversely, assume that ${\textsf{Kl}}(D_R)$ has parametrized equality strengthening. Let $A = I$ be the singleton and let X, Y, and E each have cardinality two. We choose morphisms p, $\pi$ , $h_1$ , and $h_2$ with types as above to be given by

(62) \begin{align} \begin{aligned} p &:= \begin{pmatrix} z \\ \overline{z} \end{pmatrix} \\[6pt] \pi &:= \begin{pmatrix} v & w \\ \overline{z} & 0 \end{pmatrix} \end{aligned} && \begin{aligned} h_1 &:= \begin{pmatrix} s & 1 \\ \overline{s} & 0 \end{pmatrix} \\[6pt] h_2 &:= \begin{pmatrix} t & 1 \\ \overline{t} & 0 \end{pmatrix} . \end{aligned} \end{align}

where $z := v + w$ . In the above matrix notation, $\pi$ ranges over X in its rows and over E in its columns, while $h_1$ and $h_2$ denote stochastic matrices $X \to Y$ with X in columns and Y in rows as usual. With these choices Equation (58) reads

(63) \begin{equation} \begin{pmatrix} s z & \overline{s} z \\ \overline{z} & 0 \end{pmatrix} = \begin{pmatrix} t z & \overline{t} z \\ \overline{z} & 0 \end{pmatrix}, \end{equation}

as an equality of joint distributions in $D_R(X \times Y)$ with X on the rows and Y on the columns. This equation follows from the assumed antecedent of Implication (57). Applying parametrized equality strengthening to get Equation (61), we then obtain the requisite equations $sv = tv$ and $sw = tw$ by choosing the elements of X and Y that correspond to the upper left corner in Equation (63).

As we show next, the conditions in Proposition 2.20 are also satisfied when R is a bounded distributive lattice (as considered in Remark 2.19). Later on, this will rule such semirings out as potential counterexamples showing that positivity does not imply causality, and we will need to consider more complicated semirings instead (Proposition 2.25).

Proof. Let us denote the underlying lattice ordering by $\geq$ . We will show that for arbitrary elements s,t,v,w of R, Implication (57) holds, from which causality follows by Proposition 2.20. By the antecedent of (57) and the fact that in a lattice we always have $a+b \geq a \geq ab$ and $a+b \geq b \geq ab$ , we can infer the order relations depicted in the following Hasse diagram, where $z := v + w$ :

(64)

Using transitivity of $\geq$ , we extract relations

(65) \begin{align} s &\geq tv, & v &\geq tv, & t &\geq sv, & v &\geq sv. \end{align}

Since sv is the greatest lower bound of $\{s,v\}$ , the first two imply $sv \geq tv$ , and by similar reasoning the latter two imply $tv \geq sv$ . Since $\geq$ is antisymmetric, we finally get $sv = tv$ . Analogously, one can obtain the other equation $sw = tw$ . By Proposition 2.20, ${\textsf{Kl}}(D_R)$ is thus a causal Markov category.

Returning to the general theory, we now prove a new and surprising implication from causality to positivity.

Proof. Let $f \colon A \to W$ and $g \colon W \to X$ be such that $g \circ f$ is deterministic. Define p to be the morphism

(66)

where the two forms of p are equal by the assumption that $g \circ f$ is deterministic. Then there is a dilation $\pi$ of p, with environment W, given by

(67)

Note that the following equation

(68)

holds by the associativity of copying, where we identify $h_1$ as ${\textrm{del}_X} \otimes {\textrm{id}_X}$ and $h_2$ as ${\textrm{id}_X} \otimes {\textrm{del}_X}$ .

Since causality is equivalent to parametrized equality strengthening (Proposition Proposition 2.17), we can apply the latter to Equation (68). Replacing p (with its outputs copied) by the dilation $\pi$ from (67) yields

(69)

which is the desired positivity equation up to swapping the outputs (see Definition 2.1).

The fact that positivity does not imply causality in general is shown by constructing a Markov category that is positive but not causal, which we do next in Proposition 2.25.

In particular, we take inspiration from Propositions 2.12 and 2.20 and look for an entire commutative semiring that is zerosumfree, but does not satisfy Implication (57). By Proposition 2.23, we know that such a semiring cannot be a distributive lattice. Rather, let $\mathcal{I}(\mathbb{Z}[2i])$ be the commutative quantale^{Footnote 5} of ideals of the commutative ring

(70) \begin{equation} \mathbb{Z}[2i] = \mathbb{Z} \oplus 2i \mathbb{Z} = \big\{ m \oplus 2i k \mid m,k \in \mathbb{Z} \big\}, \end{equation}

which is the subring of the Gaussian integers whose imaginary part is even. The addition and multiplication in $\mathcal{I}(\mathbb{Z}[2i])$ are the ideal addition and multiplication, respectively, with units given by the null ideal $\{0\}$ the whole ring $\mathbb{Z}[2i]$ , respectively.

Question 2.26. Is there a characterization of when a representable Markov category is causal, analogous to Proposition 2.14?

2.5 Information flow almost surely

As a brief aside, let us turn to the notion of strict positivity introduced in Fritz (Reference Fritz2020, Definition 13.16). As discussed in Section 4.3, the name strict positivity appears unfortunately chosen in retrospect. We thus refer to it as relative positivity in this article. It corresponds to the positivity axiom (Definition 2.1) with both antecedent and consequent relativized to p-almost sure equality. That is, we say that $\textsf{C}$ is a relatively positive Markov category if for all morphisms f, g, and p of suitable types, we have

(75)

Remark 2.27. Relative positivity implies ordinary positivity by choosing $p=\textrm{id}$ .

In fact, one can formulate similar relative versions of other information flow axioms, such as relative deterministic marginal independence and relative causality. By replacing equalities with p-a.s. equalities in the respective proofs, implications in Fig. 1 remain valid also between the relative versions of the axioms, e.g., relative causality implies relative positivity by Theorem 2.24.

An interesting observation is that the causality axiom is equivalent to its relativized version. That is, the implication

(76)

can be derived by two applications of the causality axiom itself. This lets us show the following strengthening of Theorem 2.24.

Proof. By the arguments presented in this section, we have

\begin{equation*} \text{causality} \iff \text{relative causality} \implies \text{relative positivity}. \end{equation*}

It is interesting to note that the first implication cannot be generalized to quantum Markov categories due to Parzygnat (Reference Parzygnat2020, Example 8.28 and Proposition 8.34).^{Footnote 7}

3.1 Quasi-Borel spaces

Quasi-Borel spaces have been introduced in Heunen et al. (Reference Heunen, Kammar, Staton and Yang2017) as a conservative extension of the category of measurable maps between standard Borel spaces to a cartesian closed category $\textsf{Qbs}$ . This means that one can form function spaces such as $2^\mathbb{R}$ , the space of all Borel subsets of $\mathbb{R}$ , and consider probability distributions on such objects. Quasi-Borel spaces also feature a probability monad P which is commutative, affine, and agrees with the Giry monad on standard Borel spaces. We denote the Markov category obtained as the Kleisli category of P by $\textsf{QBStoch}$ . It serves as an interesting source of counterexamples to information flow axioms, as it can “hide” information flow into objects like $2^\mathbb{R}$ .

A quasi-Borel space is a pair $(X,M_X)$ , where X is a set and $M_X \subseteq X^\mathbb{R}$ is a collection of functions $\mathbb{R} \to X$ , called random elements, satisfying certain closure properties (Heunen et al. Reference Heunen, Kammar, Staton and Yang2017), such as including all constant maps. A morphism of quasi-Borel spaces $(X,M_X) \to (Y,M_Y)$ is a function $f \colon X \to Y$ that preserves random elements. We consider the following quasi-Borel spaces of interest:

• • The real line is the quasi-Borel space $\mathbb{R}$ whose random elements are the Borel measurable maps $\mathbb{R} \to \mathbb{R}$ .

• • The Booleans form the quasi-Borel space 2 with two elements, whose random elements are the Borel measurable maps $\mathbb{R} \to 2$ , i.e., Borel subsets of $\mathbb{R}$ .

• • The exponential $2^\mathbb{R}$ in $\textsf{Qbs}$ consists of all Borel measurable maps $\mathbb{R} \to 2$ . Its random elements $\mathbb{R} \to 2^\mathbb{R}$ are precisely the exponential transposes of Borel measurable maps of type $\mathbb{R} \times \mathbb{R} \to 2$ . The evaluation map

  (77) \begin{equation} \textsf{ev} \colon 2^\mathbb{R} \times \mathbb{R} \to 2, \qquad (A,x) \mapsto {[\![} x \in A {]\!]} \end{equation}
  is a morphism of quasi-Borel spaces, where ${[\![} x \in A {]\!]}$ stands for the truth value of the proposition $x \in A$ .

Every quasi-Borel space $(X,M_X)$ has an induced $\sigma$ -algebra $\Sigma_{M_X}$ given by the largest $\sigma$ -algebra which makes all random elements measurable. Equivalently, a subset $A \subseteq X$ is measurable if and only if its characteristic function is a morphism of quasi-Borel spaces of type $(X,M_X) \to 2$ .

Random elements $\mathbb{R} \to X$ allow one to push a source of randomness from the quasi-Borel space $\mathbb{R}$ onto the quasi-Borel space $(X,\Sigma_{M_X})$ . In this spirit, a probability measure on $(X,M_X)$ is a probability measure on the induced measurable space $(X,\Sigma_{M_X})$ which can be obtained as a pushforward $\alpha_*\mu$ , where $\alpha \in M_X$ is a random element and $\mu \in P(\mathbb{R})$ is an ordinary probability measure on $\mathbb{R}$ .

The probability monad P on $\textsf{Qbs}$ assigns, to every quasi-Borel space $(X,M_X)$ , the set P(X) of all probability measures on X endowed with a suitable quasi-Borel structure. The unit $\eta_X \colon X \to P(X)$ of the monad is given by the Dirac measure. The monad P is affine and commutative (Heunen et al. Reference Heunen, Kammar, Staton and Yang2017), so that its Kleisli category $\textsf{QBStoch}$ is a Markov category.

3.2 Random singleton sets

We can now take advantage of the cartesian closure of quasi-Borel spaces to define random singleton sets. There is a morphism

(78) \begin{equation} \{ - \} \colon \mathbb{R} \to 2^\mathbb{R} \end{equation}

which sends a number $x \in \mathbb{R}$ to the singleton set $\{x\} \in 2^\mathbb{R}$ . Note that this morphism is simply the exponential transpose of the equality test $(=) \colon \mathbb{R} \times \mathbb{R} \to 2$ . If $\nu \in P(\mathbb{R})$ is a probability measure on the real line, then we can describe the distribution of a random singleton set by

\[ \mathcal{RS}_\nu = P(\{ - \})(\nu) \in P(2^\mathbb{R}). \]

Recall that by definition of distributions on a quasi-Borel space, $\mathcal{RS}_\nu$ is the pushforward measure $\{-\}_*\nu$ on the induced measurable space $(2^\mathbb{R}, \Sigma_{M_{2^\mathbb{R}}})$ , defined by

(79) \begin{equation} \mathcal{RS}_\nu(\mathcal U) = \nu \bigl( \big\{ x \in \mathbb{R} \mid \{x\} \in \mathcal U \big\} \bigr) \text{ for all } \mathcal U \in \Sigma_{M_{2^\mathbb{R}}} \end{equation}

Using the $\sigma$ -algebra $\Sigma_{M_{2^\mathbb{R}}}$ is crucial – it ensures, for example, that the set $\{ x \in \mathbb{R} \mid \{x\} \in \mathcal U \}$ in (79) is measurable. We elaborate on this further in the proof of the next theorem.

Theorem 3.2. (Privacy equation Sabok et al. Reference Sabok, Staton, Stein and Wolman2021). For every atomless probability measure $\nu$ , the random singleton is equal in distribution to the empty set, i.e.

(80) \begin{equation} \mathcal{RS}_\nu = \delta_\emptyset. \end{equation}

Proof idea. The details of the proof are covered extensively in Sabok et al. (Reference Sabok, Staton, Stein and Wolman2021, Theorem 4.1). We have to show that for all $\mathcal U \in \Sigma_{M_{2^\mathbb{R}}}$ ,

(81) \begin{equation} \mathcal{RS}_\nu(\mathcal U) = \delta_\emptyset(\mathcal U) = {[\![} \emptyset \in \mathcal U {]\!]}. \end{equation}

This claim hinges on the fact that the the induced $\sigma$ -algebra on $2^\mathbb{R}$ is highly restrictive; we have

(82) \begin{equation} \Sigma_{M_{2^\mathbb{R}}} = \Big\{ \mathcal{U} \mid \forall \alpha \colon \mathbb{R} \times \mathbb{R} \to 2 \text{ measurable} , \; \big\{ x \mid \alpha(x, -) \in \mathcal{U} \big\} \in \Sigma_\mathbb{R} \Big\}, \end{equation}

which is known as Borel-on-Borel in the literature on higher order measurability (e.g. Kechris Reference Kechris1995). All families $\mathcal U$ which would be assigned different values by the formulas in (81) turn out to be not measurable. As a brief nonexample, consider the family $\mathcal E = \{ \emptyset \}$ . This would clearly differentiate a random singleton from the empty set because we have

(83) \begin{equation} \mathcal{RS}_\nu(\mathcal E) = \nu \bigl( \{ x \in \mathbb{R} \mid \{x\} \in \mathcal E \} \bigr) = 0 \quad \text{ and } \quad \delta_\emptyset(\mathcal E) = {[\![} \emptyset \in E {]\!]} = 1. \end{equation}

However, it can be shown that $\mathcal E \notin \Sigma_{M_{2^\mathbb{R}}}$ . In other words, checking if a set is empty is not a morphism $2^\mathbb{R} \to 2$ in $\textsf{Qbs}$ .

We call Theorem 3.2 privacy equation because the random number $x \in \mathbb{R}$ is “anonymized in distribution” when expressed as a random set $\{x\} \in 2^\mathbb{R}$ . In particular, we have a dilation

(84)

of $\nu$ , with environment $2^\mathbb{R}$ , which gives no information about the value x in its environment marginal that behaves like the empty set. In this sense, we could view $\psi$ as a “private dilation” – one that leaks no information.

Another way to conceive of private dilations is to require that there is no correlation between the local output and the output leaked into the environment, i.e. that the two outputs are independent. However, the dilation $\psi$ does not factorize, and so it would not be “private” in this sense. In particular, provided access to $x \in \mathbb{R}$ , one can distinguish the leaked output from $\emptyset$ by applying the evaluation morphism given in (77).

We employ these curious properties of $\psi$ to show that $\textsf{QBStoch}$ is not a positive Markov category.

Proof. By Theorem 3.2, the $2^\mathbb{R}$ -marginal of $\psi$ equals $\delta_\emptyset$ :

(85)

while the second marginal equals $\nu$ . Therefore, the product of the marginals is $\delta_\emptyset \otimes \nu$ . This is different from $\psi$ , as we can witness by postcomposing with the evaluation map

(86)

where $\textsf{tt},\textsf{ff} \colon 1 \to 2$ are the two boolean truth values.

By applying Theorems 2.8 and 2.24, we immediately obtain the following consequence, which had already been announced in Sabok et al. (Reference Sabok, Staton, Stein and Wolman2021), Stein (Reference Stein2021).

Note that because $\textsf{QBStoch}$ faithfully contains $\textsf{BorelStoch}$ , positivity will hold in the full subcategory of all quasi-Borel spaces that come from standard Borel spaces. The function space $2^\mathbb{R}$ is not of that form. This gives a novel, probabilistic reading to Aumann’s result that the evaluation morphism $\textsf{ev}$ cannot be made into a measurable map (Aumann Reference Aumann1961). It is, nevertheless, a morphism in $\textsf{Qbs}$ .

3.3 Fresh name generation

Fresh name generation is a classic area of computer science (Pitts and Stark Reference Pitts and Stark1993; Stark Reference Stark1996). A pure name is an abstract entity that contains no other information except whether it is equal to other names. Typical examples of names are identifiers such as bound variables: In definitions such as $f(x,y) = xy^2$ , the names of the variables x,y do not matter as long as they remain distinct. They could be switched or replaced by say z,w without changing the meaning of the expression. New names are allocated freshly, when they are distinct from any other name already in place. In languages such as LISP, this primitive is called <monospace>gensym</monospace>.

We give a high-level summary of the categorical semantics of name generation and show that it is another instance of information flow which can be modeled using Markov categories. We also show that the information hiding for random functions arises naturally in the context of name generation, which makes it a prototypical example of non-positivity.

A categorical model of name generation consists of the following pieces of structure, satisfying further conditions spelled out in Stark (Reference Stark1996, Section 4.1):

• • a cartesian closed category $\textsf{C}$ and a distinguished object $\mathbb A$ of names,

• • an equality test $(=) \colon \mathbb A \times \mathbb A \to 2$ , where $2 := 1+1$ is assumed to exist. (One may think of the coproduct inclusions $\textsf{tt}, \textsf{ff} \colon 1 \to 2$ as represent the boolean truth values true and false.)

• • a commutative affine monad $T \colon \textsf{C} \to \textsf{C}$ ,

• • a distinguished state $\nu \colon I \to T(\mathbb A)$ which represents picking a fresh name.

Various nondegeneracy axioms are also assumed, such as that the unit $\eta_2 \colon 2 \to T(2)$ is monic. The Kleisli category of T is a Markov category, and the freshness condition for $\nu$ states that testing a fresh name on equality always returns $\textsf{ff}$ . We can write this condition in string diagrams:

(87)

This makes $\nu$ into an abstract version of the atomless measure used in Section 3.2.

An important problem in computer science is then to understand the behavior of higher order functions that generate fresh names locally. The program

(88) \begin{equation} \mathtt{let\;x=gensym()\;in\;\lambda y.(x=y)} \end{equation}

generates a fresh name $\mathtt x$ and returns a function $\mathbb A \to 2$ which tests its input $\mathtt y$ for equality with $\mathtt x$ . One can show that this function is observably indistinguishable from the function $\mathtt{\lambda y.false}$ (Stark Reference Stark1996, Example 8). This is because the name $\mathtt{x}$ remains private or enclosed in the function $\mathtt{\lambda y.(x=y)}$ , and it can never be extracted programmatically in order to obtain the output $\mathtt{true}$ .

In a categorical model of name generation, the function $\mathtt{\lambda y.(x=y)}$ is modeled using the singleton map $\{ - \} \colon \mathbb A \to 2^{\mathbb A}$ completely analogously to quasi-Borel spaces. A model of name generation is then said to satisfy the privacy equation if

(89)

holds. Given these ingredients, we can follow the reasoning of proposition 3.3 in an analogous way. This is a striking example how the abstraction of Markov categories enables connections between different areas of mathematics and computer science. That is, we obtain the following statement.

It is relatively involved to construct such a model, but Stark provides one in Stark (Reference Stark1996, Section 6.1) using a categorified version of logical relations. We stress that this model has no probabilistic ingredients whatsoever.

On the other hand, the use of Markov categories lets us apply synthetic probabilistic terminology and intuition to reason about name generation. In fact, choosing names at random is a common strategy to implement <monospace>gensym</monospace> in practice. By using an atomless measure $\nu$ , we formally obtain purely probabilistic semantics for name generation, as described in Sabok et al. (Reference Sabok, Staton, Stein and Wolman2021):

4.1 Categories of dilations

In this part, we study dilations more in detail (recall them from Definition 1.11). The following notion of dilational equality generalizes the definition of strongly almost sure equality (Cho and Jacobs Reference Cho and Jacobs2019, Definition 5.7), defined originally with respect to a state $p \colon I \to X$ . We have already encountered it in Definition 2.16, which defines a Markov category with parametrized equality strengthening as one in which equality almost surely implies dilational equality.

Definition 4.1. Let $p \colon A \to X$ and $f,g \colon X \to Y$ be morphisms in $\textsf{D}$ . We say that f and g are p-dilationally equal, written as

\[ f =_{p\text{-dil.}} g, \]

if for every dilation $\pi$ of p, we have

(90)

Intuitively, $f =_{p\text{-dil.}} g$ means that f and g cannot be distinguished even with access to whatever environment that p may have leaked information to. While this trivially implies $f p = g p$ , it is typically a strictly stronger condition:

This example suggests that dilational equality in the Markov categories case is closely related to almost sure equality (Fritz Reference Fritz2020, Definition 13.1). We now formalize this relation.

Proposition 4.3. In a Markov category $\textsf{C}$ , dilational equality implies equality almost surely. That is, for any $f,g \colon X \to Y$ and any $p \colon A \to X$ ,

(91) \begin{equation} f =_{p\text{-dil.}} g \quad \implies \quad f =_{p\text{-a.s.}} g . \end{equation}

The converse is true if and only if $\textsf{C}$ is a causal Markov category.

Proof. Every morphism p has a dilation given by

(92)

Substituting it for $\pi$ in Equation (90) produces exactly the desired p-a.s. equality of f and g.

Note that the converse of implication (91) is precisely the property of parametrized equality strengthening from Definition 2.16, which is equivalent to causality as shown in Proposition 2.17.

To every morphism in a semicartesian category, we can associate an entire category of dilations — a variant of the one introduced in Houghton-Larsen (Reference Houghton-Larsen2021, Remark 2.2.8).

Definition 4.4. Let $p \colon A \to X$ be any morphism in $\textsf{D}$ . Then its category of dilations, denoted

\[ \textsf{Dilations}(p), \]

has dilations of p as objects. Given two dilations of p, say $\pi \in \textsf{D}(A, X \otimes E)$ and $\pi' \in \textsf{D}(A, X \otimes E')$ , morphisms $\pi \to \pi'$ in $\textsf{Dilations}(p)$ correspond to $=_{\pi\text{-dil.}}$ equivalence classes of morphisms $f \in \textsf{D}(E, E')$ such that

(93)

holds. Composition of morphisms is defined as composition of representatives in $\textsf{D}$ .

In other words, if $f_1$ and $f_2$ both satisfy Equation (93), then these represent the same morphism of dilations if and only if $f_1 =_{\pi\text{-dil.}} f_2$ , which means that for every dilation $\rho$ of $\pi$ , we have

(94)

where the third output wire F denotes the additional environment object associated with $\rho$ .

Proof. Consider $f_1, f_2 \in \textsf{D}(E, E')$ and $g_1, g_2 \in \textsf{D}(E',E'')$ as representatives of morphisms $\pi \to \pi'$ and $\pi' \to \pi''$ . If $f_1 =_{\pi\text{-dil.}} f_2$ , then we have the requisite

(95) \begin{equation} g_1 \circ f_1 =_{\pi\text{-dil.}} g_1 \circ f_2 \end{equation}

by composing Equation (94) with $g_1$ .

On the other hand, given $g_1 =_{\pi'\text{-dil.}} g_2$ , we have the requisite

(96)

for every dilation $\rho$ of $\pi$ because the morphism

(97)

is itself a dilation of $\pi'$ . Thus, the required $g_1 \circ f_1 =_{\pi\text{-dil.}} g_2 \circ f_1$ follows and composition in $\textsf{Dilations}(p)$ is well-defined.

Example 4.6. (Copying leaked information is irrelevant). If $\pi \colon A \to X \otimes E$ is a dilation of any morphism $p \colon A \to X$ in a causal Markov category $\textsf{C}$ , then the dilation given by

(98)

is isomorphic to $\pi$ in $\textsf{Dilations}(p)$ . To see this, note that the copy morphism itself defines a morphism of dilations $\pi \to \pi'$ , while marginalizing either environment output of $\pi'$ defines a morphism $\pi' \to \pi$ . The composite $\pi \to \pi' \to \pi$ is trivially equal to $\textrm{id}_\pi$ already at the level of representatives in $\textsf{C}$ . In the other direction, we use Proposition 4.3 to reduce the claim to proving $\pi'$ -almost sure equality. This amounts to the equation

(99)

which is a straightforward consequence of the commutative comonoid equations on E. Note that for this direction, the composite $\pi' \to \pi \to \pi'$ is generally not equal to $\textrm{id}_{\pi'}$ on the level of representatives. In fact, in the version of $\textsf{Dilations}(p)$ where morphisms are not identified up to equivalence, the two dilations are generally not isomorphic, since an isomorphism therein in particular constitutes an isomorphism between X and $X \otimes X$ , which typically does not exist.

4.2 Initial dilations

We introduce and study a variant of the concept of universal dilations from Houghton-Larsen (Reference Houghton-Larsen2021, Definition 2.4.1).

Explicitly, a dilation $\pi$ of $p \colon A \to X$ is initial if for every dilation $\pi'$ of p there is a morphism f in $\textsf{D}$ such that

(100)

holds and moreover such that this f is unique up to $\pi$ -dilational equality.

Our notion of initial dilation is intermediate between the notions of universal dilation and of complete dilation from Houghton-Larsen (Reference Houghton-Larsen2021).^{Footnote 8} That is, every universal dilation is initial, and every initial dilation is complete. Indeed, a universal dilation is one for which the f in Equation (100) is unique as a morphism in $\textsf{D}$ rather than unique up to dilational equality as in the case of initial dilations. On the other hand, a complete dilation is one for which f is merely required to exist with no uniqueness requirement.

Writing $X^X$ for the hom-set $(1 / \textsf{Set})(X, X)$ with basepoint the identity map, function evaluation defines a morphism

(101) \begin{equation} \textrm{ev}_X \colon X \longleftarrow X \times X^X, \end{equation}

which is a dilation of $\textrm{id}_X$ . This dilation is initial, since every dilation $\pi \colon X \leftarrow X \times E$ of $\textrm{id}_X$ arises from $\textrm{ev}_X$ by composing with a unique morphism $X^X \leftarrow E$ .

Example 4.10. In a Markov category $\textsf{C}$ , a copy morphism $\textrm{copy}_X$ is a dilation of $\textrm{id}_X$ . If $\textsf{C}$ is positive, then $\textrm{copy}_X$ is an initial dilation of $\textrm{id}_X$ . Indeed, any dilation of $\textrm{id}_X$ can be written as

(102)

which follows from the positivity axiom in the form of deterministic marginal independence (Definition 2.4), instantiated with $\pi = \iota$ . The uniqueness clause is automatic.

To see that this can fail without positivity, we return to the Markov category of quasi-Borel spaces from Section 3.

Proof. In terms of the notation from Section 3, we construct a dilation $\iota \colon 2^\mathbb{R} \to 2^\mathbb{R} \otimes \mathbb{R}$ of the identity which cannot be obtained from the copy map. To this end, we define

(103)

where $\cup \colon 2^\mathbb{R} \otimes 2^\mathbb{R} \to 2^\mathbb{R}$ takes the union of subsets. That is, $\iota$ modifies its input set A by adding in a random point and records that point in the second output. The map $\cup$ is a morphism of $\textsf{QBStoch}$ because it can be obtained via cartesian closure and the monad unit from the disjunction map $\vee \in \textsf{Qbs}(2 \times 2, 2)$ .

The privacy equation implies that $\iota$ is indeed a dilation of the identity because we have

(104)

However, $\iota$ cannot be obtained by some dilation morphism from the copy map because we have

(105)

which can be witnessed by postcomposing with the evaluation morphism $\textsf{ev}$ for instance.

The copy morphism is an example of a specific type of dilation in which only the input is leaked to the environment. More generally, the bloom $p_\textrm{ic}$ (Fullwood and Parzygnat Reference Fullwood and Parzygnat2021) of a morphism $p \colon A \to X$ is the dilation of p given by^{Footnote 9}

(106)

In the following result, we reinterpret positivity as the property that blooms of arbitrary deterministic morphisms are initial dilations.

Proof. : Consider a deterministic morphism $p \colon A \to X$ and a dilation $\pi \colon A \to X \otimes E$ thereof. By Theorem 2.8, we can apply deterministic marginal independence to $\pi$ , which by Equation (18) gives

(107)

This makes the bloom $p_{\textrm{ic}}$ into an initial dilation of p, since the uniqueness is automatic by the fact that the A-marginal of $p_{\textrm{ic}}$ is $\textrm{id}_A$ .

: We show that $\textsf{C}$ satisfies deterministic marginal independence, which is enough by Theorem 2.8.

So once again let $\pi$ be an arbitrary dilation of a deterministic morphism p. Then, by assumption, $\pi$ factors through the bloom of p. That is, there exists an $f \colon A \to E$ satisfying

(108)

This already constitutes the relevant factorization as in Equation (18).

While for the existence of initial dilations for deterministic morphisms it suffices to assume positivity, we can give a generic argument for the existence of all initial dilations under the stronger assumption that the Markov category in question has conditionals. The following result and proof adapt the third author’s argument for the existence of universal dilations in $\textsf{FinStoch}$ (Houghton-Larsen Reference Houghton-Larsen2021, Theorem 2.4.6).

Proof. Let $p \colon A \to X$ be any morphism. We claim that an initial dilation of p is given by the dilation which simply copies both its input and output,

(109)

where the environment is given by $X \otimes A$ . To see this, let $\pi \colon A \to X \otimes E$ be any other dilation of p and let $\pi_{|X}$ be any conditional of $\pi$ with respect to X. Then $\pi$ factorizes through $p_{\textrm{ioc}}$ :

(110)

This equation follows directly from the definition of conditionals and the fact that $\pi$ is a dilation of p.

On the uniqueness, suppose that we have some other $h \colon X \otimes A \to E$ satisfying (110) in place of $\pi_{|X}$ . Then h is itself a conditional of $\pi$ with respect to X and, by the -a.s. uniqueness of conditionals, h is $p_\textrm{ioc}\text{-a.s.}$ equal to $\pi_{|X}$ . Since every Markov category with conditionals is causal (Fritz Reference Fritz2020, Proposition 11.34), we can use Proposition 4.3 to deduce that h must also be $p_\textrm{ioc}$ -dilationally equal to $\pi_{|X}$ , thus showing the requisite uniqueness property.

4.3 A dilational characterization of Markov categories

Here, we give an abstract characterization of positive Markov categories as semicartesian categories subject to additional principles. More precisely, these principles serve to single out the copy morphisms uniquely and ensure their defining properties.

We first introduce the concept of noncreative morphisms. It mimics the idea behind deterministic morphisms in a positive Markov category, but its definition applies in the semicartesian case since it does not reference the copy morphisms at all. To motivate this, let us anticipate Lemma 4.15 below: this shows that a morphism p in a positive Markov category is deterministic if and only if every dilation $\pi$ of p factors as in Equation (108). While this factorization of $\pi$ makes explicit reference to $\textrm{copy}_A$ , we also know from Example 4.10 that the copy morphism is an initial dilation of $\textrm{id}_A$ . Thus, the right-hand side of Equation (108) can be expressed as a sequential composition of an arbitrary dilation

(111)

of $\textrm{id}_A$ with $p \otimes \textrm{id}_E$ . Here is now the general definition.

Definition 4.14. A morphism $p \colon A \to X$ in a semicartesian category is called noncreative if every dilation of p is of the form

(112)

for some dilation $\iota \colon A \to A \otimes E$ of $\textrm{id}_A$ .

The term “noncreative” indicates that any information leaked from process p to the environment can be viewed as having leaked already from the input of p. For a semicartesian category $\textsf{D}$ , we write $\textsf{D}_\textrm{nc}$ for the class of noncreative morphisms in $\textsf{D}$ .

Proof. Let $p \colon A \to X$ be a noncreative morphism in $\textsf{C}$ . The morphism ${\rm{copy}}_X \circ p$ is a dilation of p, and therefore satisfies

(113)

for some dilation $\iota \colon A \to A \times X$ of $\textrm{id}_A$ by Definition 4.14. Since $\rm{copy}_A$ is an initial dilation of $\textrm{id}_A$ by assumption, we must have $\iota = (\textrm{id}_A \otimes f) \circ \rm{copy}_A$ for some $f \colon A \to X$ . Consequently,

(114)

holds and in particular we must have $f = p$ by marginalizing the left output. The resulting equation precisely asserts that p is deterministic. Hence, the claim $\textsf{C}_\textrm{nc} \subseteq \textsf{C}_\textrm{det}$ follows.

It remains to prove that the reverse inclusion $\textsf{C}_\textrm{det} \subseteq \textsf{C}_\textrm{nc}$ is equivalent to positivity of $\textsf{C}$ . This can be achieved either by showing that $\textsf{C}_\textrm{det} \subseteq \textsf{C}_\textrm{nc}$ is a just a different way to express deterministic marginal independence (Definition 2.4) or by relating it to property (ii) of Proposition 4.12. We take the latter approach. To this end, consider a deterministic morphism $p \colon A \to X$ in $\textsf{C}$ and an arbitrary dilation $\pi \colon A \to X \otimes E$ thereof.

Suppose first that $\textsf{C}$ is positive. By Proposition 4.12, the bloom of p is an initial dilation of p, so that we have

(115)

for some $f \colon A \to E$ . The fact that the morphism in the dashed rectangle is a dilation of $\textrm{id}_A$ shows that p is noncreative, so that $\textsf{C}_\textrm{det} \subseteq \textsf{C}_\textrm{nc}$ follows.

Conversely, suppose that $\textsf{C}_\textrm{det} \subseteq \textsf{C}_\textrm{nc}$ holds. Together with the assumption that $\textrm{copy}_A$ is an initial dilation of $\textrm{id}_A$ , this implies the factorization of $\pi$ as in Equation (115) for some f, which is necessarily the E-marginal of $\pi$ and therefore unique. By Proposition 4.12 again, we obtain that $\textsf{C}$ is a positive Markov category.

Positivity implies that copy morphisms are initial dilations of the identities (Example 4.10). We therefore obtain another immediate characterization of positivity.

Our next goal is to characterize certain classes of Markov categories as semicartesian categories subject to additional axioms. Specifically, these axioms shall serve as a way to reconstruct the copy morphisms and to ensure their required properties. In this way, the copy morphisms emerge as a consequence of dilational axioms rather than being imposed as additional mathematical data on top of a semicartesian category.

Definition 4.17.

1. (i) A morphism $b_X \colon X \to X \otimes X$ is broadcasting if both of its marginals are the identity:

   (116)

   

2. (ii) An object X admits broadcasting if there is a broadcasting morphism $b_X \colon X \to X \otimes X$ .

The terminology is inspired by the analogous concept of broadcasting in quantum information theory (Barnum et al. Reference Barnum, Caves, Fuchs, Jozsa and Schumacher1996). For example, the terminal object I trivially admits broadcasting; and if X and Y admit broadcasting via $b_X$ and $b_Y$ , then so does $X \otimes Y$ via the product $b_X \otimes b_Y$ with the middle outputs swapped. Furthermore, every copy morphism in a Markov category is broadcasting by the counitality axiom. In some Markov categories, however, there are other broadcasting morphisms as well. For instance, in $\textsf{FinStoch}_\pm$ (Example 2.7) for ${X = \{0,1\}}$ , the kernel given by

(117) \begin{equation} b_X( x_1, x_2 | x_0) := (-1)^{x_1+x_2} + \textrm{copy}_X(x_1, x_2 | x_0) \end{equation}

is broadcasting, but not equal to the copy map.

On the positive side, in positive Markov categories there are no broadcasting morphisms other than copy,^{Footnote 10} since then for any broadcasting morphism $b_X$ , we have

(118)

where the second step is by positivity and the third by the broadcasting property. This shows that $b_X$ is the copy morphism upon marginalizing the third output.

We therefore obtain a no-broadcasting theorem (Barnum et al. Reference Barnum, Barrett, Leifer and Wilce2007): X does not admit broadcasting if and only if $\textrm{del}_X$ is not noncreative.

Proof. : Given a broadcasting morphism $b_X$ , by equations (116) we have

(119)

for every $f \colon X \to Y$ . In particular, an arbitrary dilation of $\textrm{del}_X$ is of the form of diagram (112) and thus $\textrm{del}_X$ is noncreative.

: Consider the dilation $\textrm{id}_X$ of $\textrm{del}_X$ with environment X. Since $\textrm{del}_X$ is noncreative, this dilation must be of the form (112). That is, there is a dilation $\iota \colon X \to X \otimes X$ of $\textrm{id}_X$ whose second output is the environment and which also satisfies

(120)

In particular, $\iota$ is broadcasting.

In the remainder of this section, we characterize positive Markov categories in purely semicartesian terms.

Proof. : If $\textsf{D}$ is a Markov category in which the copy morphisms are initial dilations of the identity, then the requirements of (ii) hold since the identity is noncreative.

: Using the notation of the statement, since $\iota$ is a dilation of the noncreative morphism $\iota_E$ with environment X, we have

(122)

for some $c_X\colon X \to X \otimes X$ whose right-hand marginal is $\textrm{id}_X$ . We argue that this morphism is broadcasting. Indeed, we just noted that the right-hand marginal is the identity, while the left-hand marginal is the identity because $\iota$ is a dilation of the identity:

Moreover, since $\iota$ is an initial dilation of the identity, there is $g \colon E \to X$ in $\textsf{D}$ that corresponds to a morphism of type $\iota \to c_X$ in $\textsf{Dilations}(\textrm{id}_X)$ , so that

Marginalizing the first output of this equation gives $g \circ \iota_E = \textrm{id}_X$ , while the initiality of $\iota$ implies ${\iota_E \circ g =_{\iota\text{-dil.}} \textrm{id}_{E}}$ . As a consequence, $c_X$ is isomorphic to $\iota$ in $\textsf{Dilations}(\textrm{id}_X)$ and thus also an initial dilation of $\textrm{id}_X$ .

Next, we show that every identity morphism $\textrm{id}_X$ has exactly one broadcasting morphism. To this end, let ${c'_X \colon X \to X \otimes X}$ be another morphism satisfying equations (116). Then we have

(123)

for some $h \colon X \to X$ by initiality of $c_X$ . Marginalizing the left output gives $h = \textrm{id}_X$ , so that $c'_X$ is necessarily equal to $c_X$ . This demonstrates the asserted uniqueness. In particular, this immediately implies that $c_X$ is symmetric, i.e., it satisfies

(124)

because swapping the outputs of $c_X$ obviously results in a broadcasting morphism again. Furthermore, $c_X$ is also the only dilation of $\textrm{id}_X$ which is symmetric in this sense, as being a symmetric dilation implies being broadcasting.

Next, let us show that the unique symmetric dilation equips X with the structure of a commutative comonoid. Commutativity is precisely Equation (124) and counitality corresponds to Equations (116). For coassociativity, the initiality of $c_X$ implies that there is a $d_X$ of the same type such that

(125)

holds, since the left-hand side of the equation is a dilation of $\textrm{id}_X$ with environment $X \otimes X$ . But then marginalizing the first output shows $d_X = c_X$ since $c_X$ is broadcasting, so that we obtain the required coassociativity equation.

In order to see that $\textsf{D}$ becomes a Markov category, it is thus enough to prove the multiplicativity equation

(126)

for all objects X and Y. As we argued above, symmetric dilations of identities are unique. Therefore, Equation (126) follows upon showing that its right-hand side is a dilation of $\textrm{id}_{X \otimes Y}$ that is invariant under swapping the two copies of $X \otimes Y$ . Since this is a direct consequence of the symmetry of $c_X$ and $c_Y$ , we obtain the desired result.

Furthermore, the uniqueness of the broadcasting morphisms implies that the constructed Markov category structure is the only possible one (cf. Fritz Reference Fritz2020, Remark 11.29).

With this characterization at hand, also positive Markov categories can now be characterized in semicartesian terms by adding additional requirements to item (ii).

Consider a morphism f satisfying the condition of Equation (128). For $\pi=\textrm{copy}_Y$ , we have

(129)

where the box on the right-hand side represents an arbitrary dilation of the identity on X since $\textrm{copy}_X$ is its initial dilation by assumption. Marginalizing the left output gives $g = f$ , so that f is deterministic by Equation (129). Conversely, every deterministic morphism satisfies Equation (128), which, once again, follows from copy morphisms being initial dilations of identities. Therefore, the second part of item (ii) can be restated as “every deterministic morphism is noncreative,” and this holds if and only if $\textsf{D}$ is positive by Lemma 4.15.