Proposition [efr-0044]

Let \mathcal {C} be a Markov category. Then \mathcal {C}^\to \to \mathcal {C} is a Markov prefibration with Cartesian maps given by pullback squares, if and only if \mathcal {C} is pullback-positive.

Proof

Assume first \mathcal {C} is pullback-positive. It is clear that computing pullbacks in \mathcal {C}_\mathrm {det} gives the required Cartesian lifts---pullback positivity is precisely the claim that lifts exist uniquely in the definition of a Cartesian morphism (since the map to the base leg of the pullback is always deterministic in this case). Since Cartesian lifts can be taken to be deterministic (we have just constructed deterministic Cartesian lifts, and such lifts are unique up to unique isomorphism), the second condition also follows from this assumption, simply taking the other leg to be deterministic.

Conversely, suppose \mathcal {C}^\to \to \mathcal {C} is a Markov prefibration and suppose the Cartesian maps are given by the deterministic pullback squares. Let Y \to Z be an object of \mathcal {C}^\to and let X \to Z be a deterministic map, and form the pullback X \times _Z Y, which is Cartesian. Let P \to X be deterministic and let P \to Y be any map. Expanding the latter into a map from the object P \to P to Y \to Z, the Cartesian property of the square implies there is a unique pairing P \to X \times _Z Y

Context

Markov Prefibrations [efr-2IMZ]

Remark [efr-0045]

Markov categories generally do not have pullbacks, for the same reason that they usually don't have products. This issue generally hinders the construction of fibrations, in the ordinary sense, of Markov categories. However, we can go part of the way. The idea of the following definitions is that given a pullback in the deterministic category, say A \times _Y X, a map P \to A \times _Y X where the X-coordinate is deterministic should be uniquely determined by a choice of (deterministic) map P \to X and (stochastic) P \to A such that the square commutes---as we claimed above (and will see below), this holds for the Markov category of discrete probability Kl(\Delta ). The analogous statement for products---that a map P \to A \otimes X with deterministic X-component is uniquely determined by the projections (or marginals) P \to X, P \to A---is a consequence of positivity (see Proposition [efr-OYB6]), and hence holds in most Markov categories of interest.

Definition Markov prefibration [efr-0019]

Let \mathcal {C} be a Markov category, and let p: \mathcal {D} \to \mathcal {C} be a functor into it. Then we call p a Markov prefibration if the following two conditions hold:

  1. The pullback \mathcal {D} \times _\mathcal {C} \mathcal {C}_\mathrm {det} \to \mathcal {C}_\mathrm {det} is a (Grothendieck) fibration
  2. Given maps f: A \to C, g:B \to C in \mathcal {D}, such that p(f),p(g) are deterministic and f,g are Cartesian for the above fibration, p induces a bijection between maps h: A \to B \in \mathcal {C} such that gh = f, and maps h': p(A) \to p(B) so that p(g)h' = p(f). Note that when restricted to those maps where p(h) is deterministic, this being a bijection is the defining property of g being Cartesian (for any f, not necessarily a Cartesian one).

Given a Markov prefibration \mathcal {D}, we write \mathcal {D}|_\mathrm {det} for \mathcal {D} \times _\mathcal {C} \mathcal {C}_\mathrm {det}. We will refer to this as the deterministic part of \mathcal {D}---note that this does have the potential for confusion, as when \mathcal {D} is itself a Markov category, this is not necessarily the same as the deterministic subcategory of \mathcal {D}. When f \in \mathcal {D} lies inside \mathcal {D}|_\mathrm {det}, and is Cartesian for that fibration, we will simply refer to it as a Cartesian map in \mathcal {D} (there are no other types of Cartesian maps, so this should not lead to confusion). A morphism of Markov prefibrations is a functor \mathcal {D} \to \mathcal {D}' over \mathcal {C} which preserves Cartesian maps. The category of Markov prefibrations over \mathcal {C} thus defined is denoted \mathsf {MarkPreFib}(\mathcal {C}). Taking the deterministic part defines a functor (-)|_\mathrm {det}: \mathsf {MarkPreFib}(\mathcal {C}) \to \mathsf {Fib}(\mathcal {C}_\mathrm {det}).

Remark On 2-category theory [efr-EQ41]

Since we will shortly be working with a number of functors between categories whose objects are themselves categories with some structure, it may be thought that we should give some consideration to the strictness of our constructions---for example, we will shortly construct a left adjoint to (-)|_\mathrm {det}: \mathsf {MarkPreFib}(\mathcal {C}_\mathrm {det}) \to \mathsf {Fib}(\mathcal {C}), and it may well be asked how strict this adjoint is, whether we need to consider the definition of pseudomonad when we get so far, et cetera.

However, we can largely avoid this issue. The key observation is that none of our functors will alter the objects of the underlying category (since \mathcal {C}_\mathrm {det} \to \mathcal {C} is identity on objects,). Hence, all the natural transformations that we would ordinarily ask to be equivalences of categories will instead be isomorphisms, and we can largely ignore considerations of higher category theory---similarly, all our functors will be strictly functorial. As a simple example of this, observe that the pullback functor (-)|_\mathrm {det} is automatically strict---it simply consists in restriction to a subset of the morphisms in \mathcal {D} (which is automatically closed under composition), and thus clearly preserves composition strictly.

Definition [efr-DINO]

In a Markov prefibration p: \mathcal {D} \to \mathcal {C} (as previously noted), a morphism f: \bar {X} \to \bar {Y} in \mathcal {D} is called Cartesian if p(f) is deterministic and f is Cartesian in the fibration \mathcal {D}|_\mathrm {det} \to \mathcal {C}_\mathrm {det}. It is called vertical if p(f) is an identity. It is called a stochastic-Cartesian if there exists a Cartesian map r: \bar {Y} \to \bar {X} so that rf = 1_{\bar {X}} (recall that in this case f is uniquely determined by r and p(f)). Note that if f is stochastic-Cartesian and p(f) is deterministic, then f is Cartesian.

The introduction to this chapter contains the argument that Kl(\Delta ) is a Markov prefibration. This is a key motivating example.

Example Markov prefibrations over Cartesian base [efr-CJTH]

Let \mathcal {C} be a Markov category which is Cartesian (that is, one where all morphisms are deterministic). Then a Markov prefibration over \mathcal {C} is simply a Grothendieck fibration.

Proposition [efr-0044]

Let \mathcal {C} be a Markov category. Then \mathcal {C}^\to \to \mathcal {C} is a Markov prefibration with Cartesian maps given by pullback squares, if and only if \mathcal {C} is pullback-positive.

Proof

Assume first \mathcal {C} is pullback-positive. It is clear that computing pullbacks in \mathcal {C}_\mathrm {det} gives the required Cartesian lifts---pullback positivity is precisely the claim that lifts exist uniquely in the definition of a Cartesian morphism (since the map to the base leg of the pullback is always deterministic in this case). Since Cartesian lifts can be taken to be deterministic (we have just constructed deterministic Cartesian lifts, and such lifts are unique up to unique isomorphism), the second condition also follows from this assumption, simply taking the other leg to be deterministic.

Conversely, suppose \mathcal {C}^\to \to \mathcal {C} is a Markov prefibration and suppose the Cartesian maps are given by the deterministic pullback squares. Let Y \to Z be an object of \mathcal {C}^\to and let X \to Z be a deterministic map, and form the pullback X \times _Z Y, which is Cartesian. Let P \to X be deterministic and let P \to Y be any map. Expanding the latter into a map from the object P \to P to Y \to Z, the Cartesian property of the square implies there is a unique pairing P \to X \times _Z Y

Remark [efr-0040]

In a general Markov category, not every isomorphism is necessarily deterministic. This means that, in general, fibres over isomorphic objects in a Markov prefibration are not necessarily isomorphic or even equivalent as categories. This seemingly immoral situation is, in fact, in accordance with other results indicating that deterministic isomorphism is really the proper notion of identification in a Markov category. See eg Reference [rischel-fritz-infinite-products], Section 4, for further discussion of this point. (Since the basic idea of a Markov category involves objects equipped with some structure which is not preserved by all the morphisms, it is not so paradoxical that an isomorphism in this situation should be insufficient to render two objects identical).

Under very weak assumptions on the Markov category \mathcal {C}, such as positivity, all isomorphisms are deterministic. This implies that all Markov prefibrations over \mathcal {C} are isofibrations, and thus rules out any sort of behavior like the above. As noted, we are only concerned with positive Markov categories.

Relatedly, in the proof of Proposition [efr-0044], a careless prover may have erroneously concluded after the first step that all Cartesian lifts are deterministic---but since Cartesian lifts are characterized only up to isomorphism, not necessarily deterministic isomorphism, this does not automatically follow. (But of course replacing a nondeterministic lift with an isomorphic deterministic one in this situation cannot alter the unique existence of the factorization, so it does not matter).

Proposition [efr-0042]

Let p: \mathcal {D} \to \mathcal {C} be a Markov prefibration, let \mathcal {C}' \subseteq \mathcal {C}, \mathcal {D}' \subseteq \mathcal {D} be full subcategories so that p(\mathcal {D}') is contained in \mathcal {C}', and suppose \mathcal {C}' is a monoidal subcategory (which is then automatically a sub-Markov category). Suppose finally \mathcal {D}' is stable under pullback along deterministic morphisms in \mathcal {C}'. Then \mathcal {D}' \to \mathcal {C}' is again a Markov prefibration.

Proof

By assumption, given Y \in \mathcal {D}' and f: X \to p(Y) \in \mathcal {C}', the Cartesian lift X' \to Y is again in \mathcal {D}'. The fullness of the subcategory inclusions suffices to prove the existence and uniqueness of the required lifts so that this is still Cartesian after restricting. For the same reason, since we have just observed that the Cartesian lifts are the same as in \mathcal {D} \to \mathcal {C}, the second part of the definition also holds.

Example \mathsf {Stoch}^\to as Markov prefibration [efr-NC7D]

Recall that the deterministic maps in \mathsf {Stoch} are those kernels valued in \{0,1\}-valued measures. (And that these are not the same thing as the measurable maps). Given a pair f:X \to Z, g: Y \to Z of such maps, we claim that the subset of X \times Y given by those points where f(x) = g(y) as measures on Z, equipped with the subset \sigma -algebra and its inclusions into X and Y, is a pullback in \mathsf {Stoch}_\mathrm {det}.

To see this, observe that \mathsf {Stoch}_\mathrm {det} is the Kleisli category for the submonad G_{0,1} of the Giry monad which takes a space to the subspace of 0,1-valued probability measures on it. Note that by the general theory of Markov categories this has products given by the products in \mathsf {Meas}. It hence suffices to prove that the pullback of f \times g: X \times Y \to Z \times Z along the diagonal Z \to Z \times Z exists---if it does, it has the universal property of the product X \times _Y Z.

To see that it does (and that it's given by the space described above), note that the diagonal is a split monomorphism, so it suffices to show that h: P \to X \times Y \in \mathsf {Stoch}_\mathrm {det} factors over X \times _Y Z if and only if the composite to Z \times Z lifts over the diagonal.

Now this lift over Z exists if and only if the probability of the diagonal \operatorname {im}(Z) \subseteq Z \times Z under the composite is 1. By definition, it is \int f(\operatorname {im}(Z) \mid x) g(\operatorname {im}(Z) \mid y) h(dx,y \mid p) Since the function being integrated is an indicator, this is simply the measure of the set \{(x,y) : \mathbb {P}(\operatorname {im}(Z) \mid x,y) = 1\}. If the probability of the diagonal is one, clearly the two marginals agree. Conversely, since \mathsf {Stoch}_\mathrm {det} is Cartesian, it must be the case that if the marginals agree the probability of the diagonal is 1. Therefore this is equal to the subset X \times _Z Y \subseteq X \times Y described at the start. But for this to have measure 1 for all p \in P is equivalent to the desired lifting property. This finishes the argument.

Moreover, this argument relied only on the 0,1-valuedness of the maps f,g, not h: P \to X \times Y or its marginals. Hence this also proves that the pullback along the diagonal is preserved by the inclusion \mathsf {Stoch}_\mathrm {det} \to \mathsf {Stoch}. Since \mathsf {Stoch} is known to be positive, this implies \mathsf {Stoch}^\to \to \mathsf {Stoch} is a Markov prefibration.

Proposition [efr-0041]

The codomain functor \mathsf {BorelStoch}^\to \to \mathsf {BorelStoch} is a Markov prefibration.

Proof

We wish to apply Proposition [efr-0042]. The only thing to check is that standard Borel spaces are stable under pullbacks in \mathsf {Meas}. But standard Borel spaces are known to be stable under products and measurable subsets, and this is enough (see eg. Reference [srivastava-borelsets] propositions 3.1.23 and 3.3.15)

Corollary [efr-0043]

\mathsf {FinStoch}^\to \to \mathsf {FinStoch} is a Markov prefibration.

Example [efr-8B5X]

The functor \mathsf {Optic}(\mathsf {BorelStoch}) \to \mathsf {BorelStoch} is not a Markov prefibration, although its pullback over \mathsf {BorelStoch}_\mathrm {det} is a Grothendieck fibration.

To see this, first consider the deterministic pullback. An optic \binom {A}{X} \to \binom {B}{Y} with deterministic base can be identified with a map X \otimes B \to A (and the base deterministic map X \to Y). To see this, first observe that the subset of \mathsf {BorelStoch}(X, Y \otimes M) with the marginal X \to Y deterministic is in bijection with \mathsf {BorelStoch}_\mathrm {det}(X,Y) \times \mathsf {BorelStoch}(X,M), since \mathsf {BorelStoch} is positive. Hence we can calculate \int ^M \mathsf {BorelStoch}_\mathrm {det}(X,Y) \times \mathsf {BorelStoch}(X,M) \times \mathsf {BorelStoch}(M \otimes B, A) \cong \mathsf {BorelStoch}_\mathrm {det}(X,Y) \times \mathsf {BorelStoch}(X \times B, A), using the ninja yoneda lemma as in Proposition [efr-M19V]. Hence this part is a fibration with the fiber over X being the coKleisli category of the X \times - monad, and the pullback functors given by reindexing these parametrized maps. The Cartesian lift of a map X \to Y at \binom {B}{Y} is given by the optic \binom {B}{X} \to \binom {B}{Y} with unit residual and identity backwards component.

Now, let g: I \to \mathbb {R} denote the standard Gaussian distribution, let f: \mathbb {R} \otimes \mathbb {R} \to \mathbb {R} be the function given by f(x,y) = 0 if x=y and y otherwise, and consider the two optics \binom {\mathbb {R}}{*} \to \binom {\mathbb {R}}{\mathbb {R}} given by (I, g: I \to \mathbb {R}, 1_\mathbb {R}: \mathbb {R} \to \mathbb {R}), (\mathbb {R}, \mathrm {copy}_\mathbb {R} g : I \to \mathbb {R} \otimes \mathbb {R}, f: \mathbb {R} \otimes \mathbb {R} \to \mathbb {R}) (where we recall that the first argument is the residual). They cannot be equal, as postcomposition with the optic \binom {\mathbb {R}}{\mathbb {R}} \to \binom {*}{*} given by the identity \mathbb {R} \to \mathbb {R} yields, for the former, the standard Gaussian g: I \to \mathbb {R}, and for the latter, the constant zero map. But postcomposition with the projection \binom {\mathbb {R}}{\mathbb {R}} \to \binom {\mathbb {R}}{*} does give the same optic (the identity), because, for every fixed y \in \mathbb {R}, when x is normally distributed, f(x,y) = y with probability one. Hence the unique lifting of Cartesian maps over Cartesian maps cannot hold.

This counterexample indicates that, although \mathsf {BorelStoch}^\to is a Markov prefibration, we can not expect a dual version of this prefibration---in fact, since over deterministic maps \mathsf {Optic}(\mathsf {BorelStoch}) is the fiberwise dual of (the restriction to trivially-indexed objects of) \mathsf {BorelStoch}^\to , this example shows that there is no Markov prefibration whose deterministic part is the fiberwise dual of \mathsf {BorelStoch}. Moreover, as the example indicates, this is not a mere technical issue, but an unavoidable fact about optics in general measurable spaces---even up to behavioral equivalence, they simply don't satisfy the conditions of being a Markov prefibration. (But see Theorem [efr-K6NM])

On the other hand, we have:

Proposition [efr-UDS9]

Let \mathcal {C} be a positive Markov category with supports. Then \mathsf {Optic}(\mathcal {C}) \to \mathcal {C} is a Markov prefibration.

Proof

As above, we see that the deterministic part is a fibration, so take X \to Y \leftarrow Z deterministic maps, and let \binom {A}{X} \to \binom {A}{Z} be an optic so that the induced triangle with the two Cartesian lifts to \binom {A}{Y} commutes. Let the two parts be f: X \to M \otimes Y, g: M \otimes A \to A. The implication is that X \to M \otimes Y \to M -almost surely, g is equal to the projection to A (and X \to M \otimes Y \to Y renders the triangle in \mathcal {C} commutative). Note that f factors over the support of this map, hence we can assume the marginal X \to M has full support. Hence up to sliding equivalence, g is strictly equal to the projection. This implies the lift is uniquely determined as desired.

The existence of supports rules out the pathological behaviour. Essentially, in the presence of supports, we can sensibly reason about "the points of measure zero" and exclude them from consideration---and Proposition [efr-8MYE] implies that the independent pairing of two measures always have the least "points of measure zero", and so that what can be proven equivalent under the assumption of independence will always be equivalent. By contrast, the map f: \mathbb {R} \times \mathbb {R} \to \mathbb {R} from Example [efr-8B5X] satisfies f(x,y) = y for almost all x when x is normally distributed, for all y, but this does not imply that for all measures on x,y with this marginal, f(x,y) is distributed as the marginal of y.

One point of view is that the map f is simply pathological, and we should restrict our attention to maps that are continuous in some sense (from the point of view of computer science, one argument for this is that computable maps are necessarily continuous). The category \mathsf {TychStoch} of Tychonoff spaces and weakly continuous kernels does indeed have supports. However, since it lacks conditionals, it is still not ideal from our point of view.

Backlinks

Remark [efr-0040]

In a general Markov category, not every isomorphism is necessarily deterministic. This means that, in general, fibres over isomorphic objects in a Markov prefibration are not necessarily isomorphic or even equivalent as categories. This seemingly immoral situation is, in fact, in accordance with other results indicating that deterministic isomorphism is really the proper notion of identification in a Markov category. See eg Reference [rischel-fritz-infinite-products], Section 4, for further discussion of this point. (Since the basic idea of a Markov category involves objects equipped with some structure which is not preserved by all the morphisms, it is not so paradoxical that an isomorphism in this situation should be insufficient to render two objects identical).

Under very weak assumptions on the Markov category \mathcal {C}, such as positivity, all isomorphisms are deterministic. This implies that all Markov prefibrations over \mathcal {C} are isofibrations, and thus rules out any sort of behavior like the above. As noted, we are only concerned with positive Markov categories.

Relatedly, in the proof of Proposition [efr-0044], a careless prover may have erroneously concluded after the first step that all Cartesian lifts are deterministic---but since Cartesian lifts are characterized only up to isomorphism, not necessarily deterministic isomorphism, this does not automatically follow. (But of course replacing a nondeterministic lift with an isomorphic deterministic one in this situation cannot alter the unique existence of the factorization, so it does not matter).