Lemma [efr-0YP1]
  1. Suppose any category \mathcal {C}' admits products and intersections---that is, pullbacks U \times _X V whenever U,V are subobjects of X. Then it admits all finite limits.
  2. Suppose \mathcal {C}_\mathrm {det} admits and \mathcal {C}_\mathrm {det} \to \mathcal {C} preserves pullbacks along monomorphisms. Suppose further \mathcal {C} is positive. Then it is pullback-positive.

Proof

To see the first point, let f: X \to Z, g: Y \to Z be arbitrary maps. Note that X \times _Z Y = (X \times Y) \times _{X \times Y \times Z \times Z} X \times Y \times Z, where the horizontal map is given by (x,y) \mapsto (x,y,f(x),g(y)), and the top by (x,y,z) \mapsto (x,y,z,z)---in the sense that the universal property of this intersection is exactly the universal property of the given pullback.

Now suppose \mathcal {C}_\mathrm {det} \to \mathcal {C} preserves this intersection, and \mathcal {C} is positive. (Note that it doesn't follow that the inclusion preserves the pullback X \times _Z Y, because it doesn't preserve the products). This amounts to the claim that a map P \to X \otimes Y lifts to the pullback if and only if the composite P \to X \otimes Y \otimes Z \otimes Z lifts over the map 1_X \otimes 1_Y \otimes \mathrm {copy}_Z (note that the pullback of a monomorphism is a monomorphism).

This implies in particular such a lift is always unique. Since if \mathcal {C} is positive, given P \to X, P \to Y, if the latter is deterministic there is a unique pairing P \to X \otimes Y, this implies there is at most one map P \to X \times _Z Y pairing the two. On the other hand, since the composite P \to Y \to Z is deterministic and equal to the composite P \to X \to Z, they are both deterministic, and hence the pairing P \to Z \otimes Z factors over the diagonal. Applying positivity again, to the tensor product (X \otimes Y) \otimes (Z \otimes Z), since the latter component is deterministic, this pairing is independent, and hence the map P \to X \otimes Y \to X \otimes Y \otimes Z \otimes Z does indeed lift, finishing the proof.

Context

Markov Fibrations › Preliminaries › Markov categories [efr-E3HE]

Recall that Markov categories (Fritz, Reference [fritz-synthetic-markov-cats]) are semicartesian symmetric monoidal categories equipped with a suitably coherent system of comonoids (\mathrm {copy}_X: X \to X \otimes X, \mathrm {del}_X: X \to I) for each object X \in \mathcal {C}. These have been used as the basis for the categorical analysis of probability theory for a number of years, see eg Reference [rischel-fritz-infinite-products], Reference [markov-supports], Reference [law-large-nums-fritz-etal], Reference [moss-perrone-ergodic]. See Reference [fritz-synthetic-markov-cats] for the basic theory, and Reference [fritz-gonda-perrone-rischel-rep] for the theory of representable Markov categories. We assume familiarity with this theory in general, but we will review some theory below, as well as a few new minor results which are helpful for the theory of Markov fibrations.

The basic idea of a Markov category is to interpret morphisms X \to Y as "stochastic processes" or kernels---that is, functions valued in probability measures. A morphism P \to X \otimes Y is a parametrized joint probability measure---the comonoid structure allows us to build a canonical such given parametrized measures P \to X, P \to Y (by precomposing their tensor with the \mathrm {copy}_P map). This is the product measure of the two---the fact that in general not every map has this form (because \mathcal {C} is not necessarily Cartesian) allows us to express the probabilistic dependence---as in, non-independence---of one variable on another.

A morphism is called deterministic if it is a comonoid (co)homomorphism, which amounts to the claim that \mathrm {copy}_Y f = (f \otimes f) \mathrm {copy}_X---in other words, that running two independent copies of the kernel (with the same input) is equivalent to running one and copying the output. The deterministic morphisms form a Cartesian monoidal subcategory which is denoted \mathcal {C}_\mathrm {det} \subseteq \mathcal {C}.

We first note the following alternative characterization of Markov categories in terms of their deterministic morphisms.

Definition Premarkov structure [efr-5B0J]

Let \mathcal {C} be a symmetric monoidal category. A premarkov structure on \mathcal {C} is a wide symmetric monoidal subcategory \mathcal {C}' \subseteq \mathcal {C}---that is, a class of morphisms which contains all identities and structural isomorphisms, and is stable under composition and monoidal products---so that the monoidal category \mathcal {C}' is Cartesian.

Proposition [efr-10HQ]

Let \mathcal {C} be a monoidal category.

  1. Given a premarkov structure \mathcal {C}' \subseteq \mathcal {C}, there is a unique Markov structure on \mathcal {C} so that each morphism in \mathcal {C}' is deterministic.
  2. Given a Markov structure, \mathcal {C}_\mathrm {det} \subseteq \mathcal {C} is a premarkov structure.
  3. A premarkov structure has the form \mathcal {C}_\mathrm {det} for some Markov structure if and only if it is maximal.

Proof

The existence part first claim is clear: \mathcal {C}' acquires a unique Markov structure since it is Cartesian, and the inclusion of that Markov structure into \mathcal {C} gives a Markov structure on \mathcal {C}. Conversely, suppose \mathcal {C} is a Markov category and \mathcal {C}' \subseteq \mathcal {C}_\mathrm {det} is a class of deterministic morphisms which is still Cartesian. This means the projections X \otimes Y \to X,Y still exhibit X \otimes Y as a product in \mathcal {C}'. But since the pairing are the unique map lifting two given maps A \to X,Y, the pairing must be preserved by the inclusion \mathcal {C}' \to \mathcal {C}_\mathrm {det}. Since the canonical Markov structure is given as a pairing, this means the markov structure induced by \mathcal {C}' \to \mathcal {C} must agree with the one given by \mathcal {C}_\mathrm {det}, which is just the original one.

The second claim is straightforward---see eg Reference [fritz-synthetic-markov-cats] remark 10.13.

Now suppose \mathcal {C}_\mathrm {det} \subseteq \mathcal {C}' \subseteq \mathcal {C}, where \mathcal {C}' is some larger premarkov structure. By the argument above, they must generate the same Markov structure on \mathcal {C}. But again, this implies that every map in \mathcal {C}' is deterministic for this Markov structure, so we have \mathcal {C}_\mathrm {det} = \mathcal {C}'. This finishes the proof.

Note that given a merely monoidal category, we can ask whether it is Cartesian, and if it is, it admits a unique symmetry induced by the universal property of the product. Hence if \mathcal {C}' \subseteq \mathcal {C} is a Cartesian wide monoidal subcategory, we may attempt to define a symmetry on \mathcal {C} simply using the one from \mathcal {C}'. However, it is not automatic that this symmetry is natural for all the morphisms in \mathcal {C}.

This basic idea was already noted by Fritz (and goes back to Golubtsov's work in Reference [golubtsov-kleisli], an important part of the prehistory of Markov categories), although the precise statement above appears to be novel. Since the coherence conditions required of the comonoids in a Markov structure can be somewhat hard to remember, this characterization may be easier to understand.

Definition Representable Markov category [efr-38FR]

A Markov category is representable if the inclusion \mathcal {C}_\mathrm {det} \hookrightarrow \mathcal {C} admits a right adjoint. In this case we denote the right adjoint P and call the object PX for X \in \mathcal {C} a distribution object for X. Observe that \mathcal {C}(X,Y) = \mathcal {C}_\mathrm {det}(X,PY) (by definition,) and hence \mathcal {C} = Kl(P) where we denote the induced monad on \mathcal {C}_\mathrm {det} P by an abuse of notation.

Example Commonly used Markov Categories [efr-OSN1]

Here are some important Markov categories:

  1. \mathsf {Stoch} (Reference [fritz-synthetic-markov-cats], section 4) is the category whose objects are measurable spaces, whose morphisms are Markov kernels, with composition given by the Chapman-Kolmogorov equation and monoidal structure given by product measures.
  2. \mathsf {BorelStoch} \subseteq \mathsf {Stoch} (Reference [fritz-synthetic-markov-cats], section 4) is the full subcategory of \mathsf {Stoch} spanned by the standard Borel spaces, that is by those measurable spaces arising as the Borel \sigma -algebra on separable, complete metric space.
  3. \mathsf {FinStoch} is the subcategory of \mathsf {Stoch} spanned by finite sets in the powerset \sigma -algebra. A morphism X \to Y in \mathsf {FinStoch} is equivalently a matrix f_{xy} : x \in X, y \in Y with entries in \mathbb {R}_{\geq 0} and with \sum _y f_{xy} = 1 for each x (this is what is called a stochastic matrix).
  4. Let \Delta : \mathsf {Set} \to \mathsf {Set} be the monad which assigns to X \in \mathsf {Set} the set \Delta (X) of countably-supported probability measures. Then the Kleisli category Kl(\Delta ) is a Markov category, sometimes called the category of discrete probability.
  5. \mathsf {TychStoch} (Reference [markov-supports], example A.1.4) is the category of Tychonoff topological spaces and kernels which are valued in Radon probability measures, and where the measure f(- \mid x) varies continuous in x \in X with respect to the weak topology---in other words, given any continuous function u \in C(Y), the resulting function on X given by E_{y \sim f(- \mid x)}u(y) is continuous. (A space X is Tychonoff if it is Hausdorff and, given K \subset X closed and x_0 not in K, there exists continuous f: X \to [0,1] with f(x_0)=0, f(k) =1 for k \in K. Every locally compact Hausdorff space is Tychonoff).

Example Diagram Markov Categories [efr-NKD7]

If \mathcal {C} is a Markov category and I is any ordinary category, there is a Markov category \mathsf {Fun}(I,\mathcal {C}) whose objects are functors I \to \mathcal {C}_\mathrm {det}, and whose morphisms are natural transformations between these considered as functors into \mathcal {C} (i.e natural transformations with stochastic components). The monoidal and Markov structure is defined simply component-wise.

In particular, taking I = \to = \{0 \to 1\} the walking arrow, we obtain a Markov category of deterministic arrows \mathsf {Fun}(\to , \mathcal {C}). We will denote this category simply \mathcal {C}^\to . Again, the objects of this category are the deterministic morphisms of \mathcal {C}, while the morphisms are the commutative squares with not-necessarily-deterministic sides

Remark A note on terminology [efr-4VOU]

When we speak of a stochastic map in a Markov category, we always mean a map which is not necessarily deterministic---that is, a general map of \mathcal {C}.

Given a map p: P \to X \otimes Y into a tensor product, the composites with the projections P \to X, P \to Y are called the marginals. Given two maps f: P \to X, g: P \to Y, we refer to any map P \to X \otimes Y with those marginals as a pairing of the two. Note that there is always a canonical pairing given by (f \otimes g) \mathrm {copy}_P. We write \langle f,g \rangle : P \to X \otimes Y for this canonical pairing. For deterministic maps this is just the usual pairing using the universal property of the product. (We mostly use this in cases where one map is deterministic, so that the pairing is unique assuming positivity). When p = \langle \pi _Xp, \pi _Yp \rangle , we say X \bot Y \mid P, and say the two coordinates are independent given P (or just independent).

Recall that the codomain functor \mathcal {C}^\to \to \mathcal {C} is a fibration if and only if \mathcal {C} admits pullbacks. Since Markov categories have terminal objects but not, in general, products, they clearly cannot be expected to have pullbacks. However, if \mathcal {C} is positive (Reference [fritz-synthetic-markov-cats], def. 11.22---but see Proposition [efr-OYB6] below), given f: P \to X deterministic, every g: P \to Y has a unique pairing P \to X \otimes Y with f. Computing pullbacks X \otimes _Z Y in the subcategory \mathcal {C}_\mathrm {det}, we usually have a similar property. This will be the basic idea behind Markov prefibrations.

By the following straightforward proposition, this property of having unique deterministic pairings is in fact equivalent to positivity:

Proposition Characterization of positivity [efr-OYB6]

Let \mathcal {C} be a Markov category. The following are equivalent:

  1. In \mathcal {C}, if f: P \to X \otimes Y has deterministic marginal P \to X, then X \bot Y \mid P. In other words, anything is independent of a deterministic variable.
  2. Given a deterministic morphism P \to X and any morphism P \to Y, there is a unique P \to X \otimes Y with those marginals.
  3. \mathcal {C} is positive.

Proof

Clearly 1 and 2 are equivalent, since independence just means f is the independent pairing of the marginals---if it is uniquely determined by its marginals, it must be equal to the independent pairing, and conversely if it is necessarily independent, it is determined by its marginals. Now let us show this is equivalent to positivity.

First suppose \mathcal {C} has unique pairings in this sense. Let f,g be as in the definition of positivity. Then the two maps X \to Y \otimes Z indicated are pairings of gf and f, and since gf is deterministic, they are identical by hypothesis.

Finally, the implication 3 \Rightarrow 1 is precisely Reference [fritz-synthetic-markov-cats], prop. 12.14.

Definition Pullback-positive [efr-T3HM]

Let \mathcal {C} be a Markov category. We say \mathcal {C} is pullback-positive if \mathcal {C}_\mathrm {det} admits pullbacks and, given a diagram of this form where P \to X is deterministic, there is a unique map P \to X \times _Z Y making the squares commute.

Note that a pullback-positive category is in particular positive by taking Z = I.

Remark [efr-A7K7]

The pullbacks appearing in Definition [efr-T3HM] are of course pullbacks in \mathcal {C}_\mathrm {det}, not \mathcal {C}, analogously to how X \otimes Y is a product in \mathcal {C}_\mathrm {det}, not \mathcal {C}. We will still use the notation X \times _Z Y for these pullbacks, which should not lead to any confusion. We may occasionally write X \times Y instead of X \otimes Y, if we are carrying out a construction which primarily involves \mathcal {C}_\mathrm {det}. Since essentially no Markov categories have Cartesian products (except when the tensor product is Cartesian), this should also not lead to any ambiguity.

Lemma [efr-0YP1]
  1. Suppose any category \mathcal {C}' admits products and intersections---that is, pullbacks U \times _X V whenever U,V are subobjects of X. Then it admits all finite limits.
  2. Suppose \mathcal {C}_\mathrm {det} admits and \mathcal {C}_\mathrm {det} \to \mathcal {C} preserves pullbacks along monomorphisms. Suppose further \mathcal {C} is positive. Then it is pullback-positive.

Proof

To see the first point, let f: X \to Z, g: Y \to Z be arbitrary maps. Note that X \times _Z Y = (X \times Y) \times _{X \times Y \times Z \times Z} X \times Y \times Z, where the horizontal map is given by (x,y) \mapsto (x,y,f(x),g(y)), and the top by (x,y,z) \mapsto (x,y,z,z)---in the sense that the universal property of this intersection is exactly the universal property of the given pullback.

Now suppose \mathcal {C}_\mathrm {det} \to \mathcal {C} preserves this intersection, and \mathcal {C} is positive. (Note that it doesn't follow that the inclusion preserves the pullback X \times _Z Y, because it doesn't preserve the products). This amounts to the claim that a map P \to X \otimes Y lifts to the pullback if and only if the composite P \to X \otimes Y \otimes Z \otimes Z lifts over the map 1_X \otimes 1_Y \otimes \mathrm {copy}_Z (note that the pullback of a monomorphism is a monomorphism).

This implies in particular such a lift is always unique. Since if \mathcal {C} is positive, given P \to X, P \to Y, if the latter is deterministic there is a unique pairing P \to X \otimes Y, this implies there is at most one map P \to X \times _Z Y pairing the two. On the other hand, since the composite P \to Y \to Z is deterministic and equal to the composite P \to X \to Z, they are both deterministic, and hence the pairing P \to Z \otimes Z factors over the diagonal. Applying positivity again, to the tensor product (X \otimes Y) \otimes (Z \otimes Z), since the latter component is deterministic, this pairing is independent, and hence the map P \to X \otimes Y \to X \otimes Y \otimes Z \otimes Z does indeed lift, finishing the proof.

The idea here is that a distribution on a subobject X' \subseteq X defined by some condition f(x \in X) \in U \subseteq Y is simply a distribution so that the condition is satisfied with probability 1. This is a natural condition which holds in many Markov categories.

The assumption that \mathcal {C} is pullback-positive will play a key role in the development of the theory of Markov fibrations. Although the theory could possibly be developed without assuming the base category has deterministic pullbacks, positivity seems to be an essential part.

Lemma [efr-MW29]

If \mathcal {C} is representable and positive, \mathcal {C}_\mathrm {det} has limits, and the monad P preserves intersections, then \mathcal {C} is pullback-positive.

Proof

This is clear, since if the monad P preserves a given limit, so does the inclusion into the Kleisli category (for completely abstract reasons), hence by Lemma [efr-0YP1] we are done.

We will need the notion of support in a Markov category, introduced in Reference [markov-supports], for certain examples, so we briefly record the definition and a few of its properties here.

Definition Support of a morphism [efr-AB57]

Let p: X \to Y, q: A \to Y be two morphisms in a Markov category. We say q is absolutely continuous with respect to p and write q << p if, whenever two maps Y \to Z are p-almost surely equal, they are also q-almost surely equal.

Let p: X \to Y be a morphism in a Markov category. The support of p, if it exists, is an object which represents the functor \mathcal {C}(-,Y)_{<<p} of morphisms into Y which are absolutely continuous with respect to p.

Proposition [efr-8MYE]
  1. The support of p: X \to A is equipped with a canonical deterministic monomorphism S_p \hookrightarrow A, so that a map into A is absolutely continuous with respect to p if and only if it factors over the support.
  2. Two maps A \otimes W \to B are p-almost surely equal if and only if they are strictly equal on the support.

Backlinks

Lemma [efr-MW29]

If \mathcal {C} is representable and positive, \mathcal {C}_\mathrm {det} has limits, and the monad P preserves intersections, then \mathcal {C} is pullback-positive.

Proof

This is clear, since if the monad P preserves a given limit, so does the inclusion into the Kleisli category (for completely abstract reasons), hence by Lemma [efr-0YP1] we are done.