Empirical Measures and
Strong Laws of Large Numbers
in Categorical Probability
March 27, 2025
The Glivenko–Cantelli theorem is a uniform version of the strong law of large numbers. It states that for every IID sequence of random variables, the empirical measure converges to the underlying distribution (in the sense of uniform convergence of the CDF). In this work, we provide tools to study such limits of empirical measures in categorical probability. We propose two axioms, namely permutation invariance and empirical adequacy, that a morphism of type \(X^\mathbb{N}\to X\) should satisfy to be interpretable as taking an infinite sequence as input and producing a sample from its empirical measure as output. Since not all sequences have a well-defined empirical measure, such empirical sampling morphisms live in quasi-Markov categories, which, unlike Markov categories, allow for partial morphisms.
Given an empirical sampling morphism and a few other properties, we prove representability as well as abstract versions of the de Finetti theorem, the Glivenko–Cantelli theorem and the strong law of large numbers.
We provide several concrete constructions of empirical sampling morphisms as partially defined Markov kernels on standard Borel spaces. Instantiating our abstract results then recovers the standard Glivenko–Cantelli theorem and the strong law of large numbers for random variables with finite first moment. Our work thus provides a joint proof of these two theorems in conjunction with the de Finetti theorem from first principles.
Laws of large numbers are widely regarded among the most important results in probability theory both in technical and conceptual terms. Conceptually, they provide self-consistency to the idea of a probability measure: Although the actual expectation value of a function \(f\) under an unknown distribution \(\mu\) cannot be inferred from a finite sequence of samples from \(\mu\), its empirical averages converge with probability \(1\) to this expectation value as the number of observations grows. In formulas, we have \[\label{eq:LLN95intro} \lim_{n \to \infty} \frac{f(x_1) + \dots + f(x_n)}{n} \;=_{\mu\text{-a.s.}}\; \int f(x) \, \mu(\mathrm{d}x),\tag{1}\] where \(=_{\mu\text{-a.s.}}\) indicates equality \(\mu\)-almost surely. This is why, given a finite number of samples \((x_1, \dots, x_n)\), one can reasonably approximate the expectation value on the right by the empirical average, which is the fraction on the left.
In particular, consider \(f\) to be the indicator function of a measurable set \(T \subseteq X\). We obtain that the relative frequency of the event \(T\) in the sequence \((x_i)_{i \in \mathbb{N}}\) converges almost surely to its probability: \[\label{eq:rel95freq95conv} \lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \in T \}|}{n} \;=_{\mu\text{-a.s.}}\; \mu(T).\tag{2}\] As \(T\) varies, one can interpret the fraction on the left as the probability of \(T\) under the empirical measure \[\label{eq:finite95empirical95distribution} \frac{1}{n} \mathopen{}\mathclose{\left( \delta_{x_1} + \dots + \delta_{x_n} }\right)\tag{3}\] of the first \(n\) elements of the sequence, where \(\delta_{x_i}\) stands for the Dirac measure at \(x_i\). One might therefore expect that the sequence of empirical measures in some sense converges to \(\mu\). The details of this convergence are subtle, and we will see that there are several reasons why it may fail. However, there also are many positive results that avoid these pitfalls and provide conditions that ensure the desired convergence [1]. One such result that is of primary interest to us is the Glivenko–Cantelli theorem. It applies to \(x_i\) valued in \(\mathbb{R}\) and establishes the uniform convergence of the relative frequencies of 2 as \(T\) ranges over all intervals in \(\mathbb{R}\).
We regard such theorems on the convergence of empirical measures as the conceptually most fundamental laws of large numbers. In this vein, we can think of a standard strong law of large numbers as a consequence obtained by taking the expectation value of \(f\) on both sides of 2 .1
The main goal of this paper is to develop results like this in the framework of categorical probability theory. This recent approach to probability theory strives to redevelop the main results of probability theory in a structured manner. It is based on a more abstract starting point than measure theory. Namely, the idea is to capture the essential features of reasoning in probability theory as properties of certain categories (oftenMarkov categories) that generalize the category of measurable spaces and Markov kernels. One benefit of this higher-level language is its focus on fundamental properties while leaving irrelevant details aside.
In order to develop laws of large numbers in this framework, we need to express limits mentioned above in the categorical language. One approach would be to equip the hom-sets with a topology and to consider convergence in this topology [2]. Here, we pursue a more abstract approach instead:
For every standard Borel space \(X\), we construct a Markov kernel \(X^\mathbb{N}\to X\) that takes an infinite sequence \((x_i)_{i \in \mathbb{N}}\) as input and returns a sample from its empirical measure as output. Since the limit of empirical measures (of the first \(n\) elements) as \(n \to \infty\) need not exist, as we discuss on the next page, this kernel is only partially defined. Instead of specifying a topology that would determine when these limits converge, we thus have the notion of the domain of the Markov kernel that tells us which infinite sequences have a well-defined empirical measure.
In Markov categories, we axiomatize the properties that a partial morphism \({\mathsf{es}_X : X^\mathbb{N}\to X}\) should satisfy in order to carry the interpretation of an empirical sampling morphism. Our two axioms are permutation invariance and empirical adequacy. The former states that \(\mathsf{es}\) should be invariant under finite permutations of the input sequence. Empirical adequacy roughly states that sampling from an exchangeable distribution \(\mu\) on \(X^\mathbb{N}\) is the same thing as iterated empirical sampling applied to a sampled sequence.
Permutation invariance and empirical adequacy are not only important properties to give \(\mathsf{es}_X\) the intended interpretation, but they are also useful in synthetic proofs of results involving empirical measures.
Given a Markov category2 with empirical sampling morphisms, we derive abstract versions of the de Finetti theorem ([cor:dF]), the Glivenko–Cantelli theorem ([thm:lln]) and the strong law of large numbers ([cor:genericLLN]). Another one of our key technical contributions is a constructions of concrete empirical sampling morphisms in measure-theoretic probability and, in particular, proofs that they satisfy the two axioms mentioned above. To set the stage for these developments, we also prove a number of technical results on Kolmogorov products in quasi-Markov categories and on the passage to partial morphisms, which are of independent interest. Particularly relevant here is the assumption of \(\sigma\)-continuity ([def:count95meets]), by which we mean the existence of countable directed meets in the hom-sets and their preservation by composition and tensor. In measure-theoretic probability, this turns out to be related to the fact that probability measures are \(\sigma\)-continuous as functions on the \(\sigma\)-algebra ([prop:sigma95parborelstoch]).
Together, our abstract theorems and the concrete constructions recover the de Finetti theorem for standard Borel spaces [3], the Glivenko–Cantelli theorem ([thm:glivenko]) and the strong law of large numbers for real-valued random variables with finite first moment ([cor:strong95lln]).
Our framework thus provides a structured proof of these three fundamental results from first principles. We believe that this joint proof is short compared to the traditional purely measure-theoretic treatment, and moreover displays enhanced conceptual clarity.
Translating probabilistic concepts and results into a categorical framework is often not straightforward, but it can be very valuable. The above summary demonstrates that empirical sampling morphisms are an invaluable tool when translating laws of large numbers and related theorems. Furthermore, we suggest that they are a key concept in probability theory that has been underappreciated so far. We hope that this realization will facilitate further progress on categorical probability theory. For example, we expect empirical sampling morphisms to be useful for the development of ergodic theorems in the categorical framework.
The rest of the Introduction provides a more detailed overview of our results.
For a finite standard Borel space \(F\), we can construct an empirical sampling morphism (in this case, a partial Markov kernel) according to the intuition above. The transition probability of an event \(T \subseteq F\) given a sequence \((x_i)_{i \in \mathbb{N}}\) is the limiting relative frequency of the occurence of the event within the sequence, i.e. \[\label{eq:desired95es} \mathsf{es}_F \bigl( T \,|\, (x_i) \bigr) \;\mathrel{\vcenter{:}}=\; \lim_{n\to\infty} \frac{ \@ifstar{\abs}{\abs*}{ \@ifstar{\Set}{\Set*}{ i \le n x_i \in T } } }{n}\tag{4}\] whenever the limit exists.
There are three types of subtleties with this construction, and a substantial part of our work is devoted to addressing them.
One could try to get around this by forcing every sequence to have well-defined limits, for example by using ultrafilter convergence or Banach limits (with respect to which every bounded sequence has a limit). However, this is not what we want, because we would not recover the convergence in the \(\varepsilon\)-\(\delta\) sense as part of the conclusion of our results. Therefore, we formalize empirical sampling as a partial Markov kernel whose domain is a subset of \(X^\mathbb{N}\). The question of which sequences should be included in the domain is itself subtle and mathematically interesting. There is a certain flexibility in the choice of domain which is closely related to the assumption of finite first moment in the strong law of large numbers (see 3.3).
To address this second issue, we require the limits in 4 to be uniform on sets of the form \(T = \{1,\ldots,t\}\),3 and take \(\mathsf{es}_\mathbb{N}\) to be undefined on all sequences that do not satisfy this requirement (see [prop:eq95uniform] for a classification of such sequences).
For uncountable \(X\), we cannot expect 4 to hold for every measurable set \(T \subseteq X\). Requiring this would entail no sequence with mutually distinct elements has an empirical measure, which is clearly undesirable.
Indeed if \((x_i)\) is such a sequence and 4 is postulated for all measurable sets, then the empirical measure will assign probability \(1\) to the (countable) support of the sequence, but probability \(0\) to every individual point in the support, contradicting \(\sigma\)-additivity.
Therefore for uncountable \(X\), we need to restrict the validity of 4 to a certain class of measurable sets. We do this in 3.2 for \(X = \mathbb{R}\) by restricting to intervals and requiring the uniform existence of the limit on these.
As already indicated, we identify two structural properties satisfied by the above constructions that serve as axioms to define an abstract empirical sampling morphism.
Permutation invariance: For every measurable \(T\subseteq X\), the probability \(\mathsf{es}_X (T|(x_i))\) is invariant under finite permutations of the sequence \((x_i)\).
This encapsulates the fact that the relative frequencies do not depend on the order of outcomes appearing in the sequence \((x_i)\), provided that one keeps almost all of them fixed.
Empirical adequacy:4 If \(\mu\) is an exchangeable probability measure on \(X^\mathbb{N}\), then we have \[\label{eq:invariance} \int_{X^n} \mathsf{es}(T_1|(x_i)) \, \cdots \, \mathsf{es}(T_n|(x_i)) \, \mu_{1\ldots n}(\mathrm{d}x_1 \times \dots \times \mathrm{d}x_n) \;=\; \mu_{1\ldots n} \bigl( T_1\times\dots\times T_n \bigr),\tag{5}\] where \(\mu_{1\ldots n}\) denotes the marginal of \(\mu\) on the first \(n\) factors. For \(\mu = \mu_1^{\otimes \mathbb{N}}\) a product measure and \(n = 1\), this says that applying empirical sampling to a sequence of IID samples from \(\mu_1\) produces another sample from \(\mu_1\) as expected.
For our particular constructions in measure-theoretic probability, this property follows from 111 , where we show that the resampling kernel \(X^\mathbb{N}\to X^\mathbb{N}\) defined as on the left of 5 , \[\mathsf{resamp} \bigl( T_1\times\dots\times T_n \times X \times \dots \,|\, (x_i) \bigr) \; \mathrel{\vcenter{:}}= \; \mathsf{es}(T_1|(x_i)) \, \cdots \, \mathsf{es}(T_n|(x_i)),\] can be written as the application of a uniformly random permutation to the sequence elements.
As we then show in 4, the existence of a kernel with these two properties features as the main common ingredient in proofs of the de Finetti theorem, the Glivenko–Cantelli theorem and the strong law of large numbers.
All of the above takes a simpler and more intuitive form in the categorical framework, which we now briefly recap.
Markov categories [4], [5] are an abstract generalization of the category of measurable spaces and Markov kernels. Research on categorical probability via Markov categories rests on the idea that the main concepts of probability theory, such as statistical (in)dependence, determinism, conditioning, invariance under symmetries, etc., can be abstractly generalized from categories of Markov kernels to more general Markov categories. Many of these notions can be captured in terms of universal properties. To illustrate this, consider the Markov category \(\mathsf{BorelStoch}\), which has standard Borel spaces as objects and Markov kernels between them as morphisms and is the Markov category of primary interest for measure-theoretic probability. Its subcategory of deterministic morphisms is \(\mathsf{BorelMeas}\), consisting of standard Borel spaces and measurable functions between them. Now given a standard Borel space \(X\), we can characterize the measurable space \(PX\) of probability measures on \(X\) [6] in terms of a universal property: It is equipped with a natural bijection \[\mathsf{BorelStoch}(A,X) \;\cong\; \mathsf{BorelMeas}(A,PX)\] between Markov kernels \(A \to X\) and measurable functions \(A \to PX\) defined for every standard Borel space \(A\) [7]. Additionally, the de Finetti theorem can be formulated as the fact that the space \(PX\) is the limit — in the categorical sense — of the diagram of all finite permutations acting on the space \(X^\mathbb{N}\) [3], [8].
Abstractions like these allow us to formulate and prove theorems of probability and related fields by means of diagram manipulation, where measure theory is needed only for showing that the relevant axioms are satisfied for the Markov category \(\mathsf{BorelStoch}\). Results that have been developed like this over the past few years feature the Kolmogorov and Hewitt–Savage zero-one laws [9], the de Finetti theorem [3], [8], the d-separation theorem for graphical models [10], the ergodic decomposition theorem [11], [12], the Blackwell–Sherman–Stein theorem [7] and the Aldous–Hoover theorem [13].5 In addition to the categorical proofs often being simpler and more intuitive than the measure-theoretic ones, they also allow for greater generality, as the categorical results can often be instantiated in Markov categories that model other kinds of uncertainty than measure-theoretic probability.
In this work we follow the same approach, focusing on the study of empirical sampling as introduced above. The axioms on empirical sampling morphisms, in the form of the permutation invariance and empirical adequacy discussed above, have simple and natural categorical formulations ([def:es]).
As already indicated, empirical sampling morphisms are partial maps that need not be defined for every input sequence. Formulating this in categorical probability therefore requires going beyond the standard theory of Markov categories. Notions of partiality for Markov categories have been first given in [19]–[21]. For our purposes, we assume quasi-totality [19] and don’t need conditionals, and thus our approach differs from the earlier ones. To this end, we develop the theory of quasi-Markov categories in 2, where the main technical contribution is a functorial version of Kolmogorov products in this setting. This framework is adequate for our purposes and general enough to include any category constructed from any “partializable” Markov category \(\mathsf{C}\) by adding formal partial versions of morphism from \(\mathsf{C}\), as shown by one of the authors in [22].
In measure-theoretic probability, there is ample literature on empirical processes, including textbooks such as [1], [23]. This literature generally focuses on the empirical measure of a finite sequence \((x_1,\ldots,x_n)\), and then studies this as a stochastic process as \(n\) varies, proving various results on when this process converges to the underlying distribution.
On the other hand, we are not aware of any prior literature on the question of when a general infinite sequence \((x_i)_{i \in \mathbb{N}}\) has a well-defined empirical measure. There seems to be remarkably little literature on empirical measures of infinite sequences, even in the measure-theoretic setting. One reference where these have been considered, in a similar spirit as in the present manuscript, is in a 2014 paper by Austin and Panchenko [24]. We will comment on this further in [ex:es95domain].
In 2, we introduce our framework of quasi-Markov categories and its features. 3 then concerns empirical sampling morphisms. We first give the categorical definition in 3.1 and subsequently construct concrete instances thereof in measure-theoretic probability. Proving that our constructions satisfy the definition is somewhat technical, which is why we include the proofs in the appendix ([sec:measure_theory,sec:proofs]). Finally, in 4 we prove our main theorems, most notably the synthetic Glivenko–Cantelli theorem, and show how they recover the standard measure-theoretic results.
We thank Alexander Glazman, Andreas Klingler and Christian Weiß for helpful discussions. Research for Paolo Perrone is funded, at the time of writing, by Sam Staton’s Consolidator Grant “BLaSt – a Better Language for Statistics” from the European Research Council. Tobias Fritz, Antonio Lorenzin and Areeb Shah Mohammed acknowledge funding by the Austrian Science Fund (FWF) [doi:10.55776/P35992]. Tomáš Gonda has been funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/ESP3451824 and the Start Prize Y1261-N. Areeb Shah Mohammed has also been supported by the Doctoral Scholarship of the University of Innsbruck. Additionally, Antonio Lorenzin has received support from the ARIA Safeguarded AI TA1.1 programme.
Before delving into our main contributions, the study of empirical sampling morphisms (3) and synthetic laws of large numbers (4), let us set the stage for this discussion by introducing quasi-Markov categories ([def:quasi-total]). In 2.1 we also introduce our key instance that supports measure-theoretic interpretation ([ex:par95borelstoch]). More general construction of quasi-Markov categories through which one can obtain further examples can be found in [22].
In 2.2, we spell out a few basic definitions that are familiar to readers accustomed to the theory of Markov categories. Unlike Markov categories, quasi-Markov ones come with a canonical (and non-trivial) ordering among morphisms that reminds one of other types of categories to model partiality [25]. We discuss this partial order in 2.3 and use it to develop tools for working with infinite tensor products in quasi-Markov categories in 2.4, which were initially introduced for Markov categories in [9]. 2.5 then introduces distribution objects in quasi-Markov categories. Finally, following the arguments laid out in [26], we show how a specific equalizer of permutations of a countable sequence of objects (a de Finetti object) is in fact also a distribution object ([thm:defin95obs]).
We first sketch the definition of CD categories, of which quasi-Markov categories are a special case. For more details, we refer the reader to [4], [5].
A copy-discard (CD) category is a symmetric monoidal category in which every object \(X\) is equipped with a distinguished commutative comonoid structure, compatible with the tensor product. The comonoid structure maps \[\mathrm{copy}_X : X\to X\otimes X, \qquad \mathrm{del}_X : X\to I\] are called copy and delete, respectively.
It is helpful to draw morphisms in CD categories in terms of string diagrams. In our conventions, we draw diagrams from bottom to top, and copy and delete like this: \[\tikzfig{comultiplication} \qquad \qquad \tikzfig{counit}\] Morphisms from the monoidal unit \(I\), referred to as states, are represented by triangles: \[\tikzfig{state}\]
A morphism \(f : A \to X\) in a CD category is total if it satisfies \[\label{equation:CDTotalDef} \tikzfig{CDTotalDef}\tag{6}\] A CD category is a Markov category if every morphism is total, or equivalently if the monoidal unit is terminal.
We can interpret Markov categories as models of information flow that may involve randomness or nondeterminism. A morphism \(X \to Y\) is then viewed as a (potentially noisy) channel from \(X\) to \(Y\). The copy map duplicates the information perfectly, and the delete map discards it.
Here are two of the most prominent examples of Markov categories.
The category \(\mathsf{FinStoch}\) has:
As objects, finite sets;
As morphisms \(X\to Y\), stochastic matrices with entries denoted by \(f(y|x)\) and the usual composition: For \(f : X\to Y\) and \(g :Y\to Z\), we have \[(g \mathchoice{\,}{\,}{}{} f)(z|x) = \sum_{y\in Y} g(z|y)\cdot f(y|x) ;\]
The tensor product is given by the cartesian product of finite sets and the tensor (or Kronecker) product of matrices, with entries given by \(f(x|a)\cdot g(y|b)\) for \(f : A\to X\) and \(g : B\to Y\);
The copy and delete maps are given by the following matrices: \[\mathrm{copy}_X (x_1,x_2|x) = \begin{cases} 1 & ifx_1=x_2=x ;\\ 0 & else; \end{cases} \qquad \qquad \mathrm{del}_X( \ast | x ) = 1;\] where the monoidal unit \(I\) is the singleton set \(\{\ast\}\).
This category is the prototype for discrete probability theory.
The \(\mathsf{BorelStoch}\) category has:
As objects, standard Borel spaces, i.e.measurable spaces whose \(\sigma\)-algebra can be expressed as the Borel \(\sigma\)-algebra of a Polish space;
As morphisms \(X\to Y\), Markov kernels, with their usual (Chapman–Kolmogorov) composition: For \(f : X\to Y\) and \(g : Y\to Z\), and given a measurable set \(A \subseteq Z\), we have \[\label{eq:ChapmanKolmogorov} (g \mathchoice{\,}{\,}{}{} f)(A|x) = \int_Y g(A|y)\cdot f(\mathrm{d}y|x) ;\tag{7}\]
The tensor product is given by the cartesian product of measurable spaces and the product of measures;
The copy and delete maps are given by the following matrices: \[\mathrm{copy}_X ( {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}| x) = \delta_{(x,x)} \qquad\qquad \mathrm{del}_X(\{\ast\}| x) = 1.\]
This category is the prototype for measure-theoretic probability theory. It contains \(\mathsf{FinStoch}\) as a full subcategory.
In order to model partial Markov kernels, we need to relax 6 , since it forces a Markov kernel \(f\) to produce an output for each input. Partial Markov kernels satisfy the following weaker condition, which will play an important role in our proofs.
A morphism \(f : A \to X\) in a CD category is quasi-total if it satisfies \[\label{eq:quasi-total} \tikzfig{quasi-total}\tag{8}\] A quasi-Markov category is then a CD category in which every morphism is quasi-total.
Trivially, every total morphism is quasi-total and every Markov category is quasi-Markov. We can interpret quasi-Markov categories as a variant of Markov categories in which a morphism is allowed to fail, i.e.it may not produce any output for some of its input values. This failure is, however, deterministic in a sense that we illustrate for \({\mathsf{FinSubStoch}}\), the variant of \(\mathsf{FinStoch}\) without the normalization condition. A morphism \(f : X \to Y\) in \({\mathsf{FinSubStoch}}\) (i.e.a substochastic matrix) is quasi-total if and only if for every input value \(a \in A\), we have either \[f(x | a) = 0 \quad \forall x \in X\] or \[\sum_{x \in X} f(x | a) = 1.\] In the former case, we say that \(f\) is undefined on input \(a\), i.e.\(f\) does not produce any output. In the latter case, \(a\) is said to be in the domain of \(f\) (cf.[def:domain]), i.e.\(f\) applied to \(a\) produces an output (with probability 1).
The quasi-totality condition therefore forces \(f\) to be normalized for every input where it does not fail. Contrast this with the totality condition, which requires, in addition, that \(f\) produces an output for every input, i.e.that \(f\) is a stochastic matrix.
Both \(\mathsf{FinStoch}\) and \(\mathsf{BorelStoch}\) are Markov categories, i.e.all of their morphisms are total. For each, we can consider a corresponding quasi-Markov category which additionally includes partial morphisms. Here, let us merely introduce the version of \(\mathsf{BorelStoch}\) with partial morphisms added. This is the key example for us, in which we will instantiate our categorical results from 4.
Specifically, we denote the resulting category \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) and call it the partialization of \(\mathsf{BorelStoch}\) [22]. It has:
As objects, standard Borel spaces;
As morphisms \(X\to Y\), partial Markov kernels, which are pairs \((D_f,f)\) consisting of a measurable set \(D_f \subseteq X\) called domain and a Markov kernel \(f : D_f \to Y\).
We often write \(f : X \to Y\) by abuse of notation for both the partial Markov kernel with domain \(D_f\) and the ordinary Markov kernel \(f : D_f \to Y\).
Composition of \(f : X \to Y\) and \(g : Y \to Z\) is \(g \mathchoice{\,}{\,}{}{} f : X \to Z\) with domain \[\label{eq:dom95comp} D_{g \mathchoice{\,}{\,}{}{} f} \mathrel{\vcenter{:}}= \@ifstar{\Set}{\Set*}{ x \in D_f f(D_g|x) = 1 }.\tag{9}\] and with the Markov kernel \(g \mathchoice{\,}{\,}{}{} f : D_{g \mathchoice{\,}{\,}{}{} f} \to Z\) defined as in 7 .6
The tensor product of \(f : A \to X\) and \(g : B \to Y\) is given by the partial Markov kernel \({f \otimes g : A \times B \to X \times Y}\) with domain \[D_{f \otimes g} = (D_f \times B) \cap (A \times D_g),\] and defined on this domain as the product measure, just as in \(\mathsf{BorelStoch}\).
Copy and delete morphisms are as in \(\mathsf{BorelStoch}\).
We leave it to the reader to verify that this indeed forms a quasi-Markov category, either by direct verification or by noting that this category is the partialization of \(\mathsf{BorelStoch}\) in the sense of [22].
The term “partialization” used above follows a tradition in category theory, where it refers to categories whose morphisms are spans with monic left legs [25]. Indeed, in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), morphisms can be represented as spans \[X \hookleftarrow D_f \xrightarrow{f} Y,\] where the left leg is a deterministic monomorphism (see [22] for further details on this connection).
In contrast, in category-theoretic approaches to probability, the term “partial Markov categories” has been used to refer to categories such as \({\mathsf{FinSubStoch}}\) [19], where not all morphisms are quasi-total. This also motivates our use of the term “quasi-Markov categories”, which avoids a clash of terminology with the existing literature. Partial Markov categories will not be discussed further in this paper.
An important feature of quasi-Markov categories is the following property, which will be particularly relevant in the discussion of representability ([sec:representable,sec:dF_obs_rep]).
Every monomorphism \(m : A \to X\) in a quasi-Markov category is total.
Proof. Under these assumptions, we have \[\tikzfig{quasi-total-mono}\qquad \implies\qquad \tikzfig{quasi-total-mono-cancelled}\qquad \implies\qquad \tikzfig{quasi-total-mono-total}\] where the first implication holds because \(m\) is a monomorphism and the second follows by applying \(\mathrm{del}_X\) to the output. As a result, quasi-totality of \(m\) (the antecedent) implies its totality (the final consequent). ◻
To get a suitable language for discussing probability, we need some natural generalizations of existing notions for Markov categories. Namely, we define what it means for a morphism to be deterministic, almost sure equalities, and the positivity axiom.
Let \(\mathsf{C}\) be a quasi-Markov category.
A morphism \(f : X\to Y\) in \(\mathsf{C}\) is copyable if it commutes with copying: \[\label{eq:copyable} \tikzfig{multiplication_natural}\tag{10}\] \(f\) is deterministic if it is both total and copyable.
The wide subcategory of \(\mathsf{C}\) consisting of copyable morphisms is denoted by \(\mathsf{C}_{\rm cop}\).
Clearly all copyable morphisms are quasi-total. In a Markov category, a morphism is deterministic if and only if it is copyable. We think of a copyable \(f\) as a channel which gives the same result (with probability \(1\)) when applied twice to the same input.
In many examples, copyable morphisms correspond indeed to what one would expect.
In \(\mathsf{FinStoch}\), copyable morphisms are precisely the deterministic stochastic matrices, i.e.those that contain only zero and one entries;
In \(\mathsf{BorelStoch}\), a Markov kernel \(f : X\to Y\) is copyable if and only if \(f(T|x) \in \{0,1\}\) for all \({x \in X}\) and all measurable \(T \subseteq Y\). These are precisely those Markov kernels of the form \({f({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em},x)=\delta_{g(x)}}\), where \(g : X\to Y\) is a measurable function (necessarily unique). Thus \(\mathsf{BorelStoch}_{\rm cop}\) is isomorphic to \(\mathsf{BorelMeas}\), the category of standard Borel spaces and measurable functions between them.
In \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), the copyable morphisms are those partial Markov kernels that are deterministic on their domain, i.e. of the form \(f({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}|x) = \delta_{g(x)}\) for some measurable \(g : D_f \to Y\). In particular, \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)_{\rm cop}\) coincides with \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelMeas}}}\right)\) (this is a general fact of partialization of Markov categories, see [22]). Such an \(f\) is deterministic if \(D_f = X\) in addition.
Throughout this paper, almost sure equalities play an important role. The definition is the same as for Markov categories [5], [27] or more generally CD categories [4].
In a quasi-Markov category \(\mathsf{C}\), consider a morphism \(p : A \to X\) and two parallel morphisms \(f,g : X \to Y\). We say that \(f\) and \(g\) are \(\boldsymbol{p}\) \(\boldsymbol{p}\) equal, and write \(f =_{p\text{-a.s.}} g\), if the following equality holds: \[\label{eq:as} \tikzfig{as_eq}\tag{11}\]
The following additional axiom is useful in the context of Markov categories [5]. Its name is motivated by the fact that its satisfaction is related to the non-negativity of measures [5].
A quasi-Markov category is positive if for each \(f : X\to Y\) and \(g : Y\to Z\), whose composite \(g \mathchoice{\,}{\,}{}{} f : X\to Z\) is copyable, the following equation holds: \[\label{positivity} \tikzfig{positivity}\tag{12}\]
To get an intuition, consider the case of \(X\) being the monoidal unit \(I\). Then positivity means that coarse-graining a state \(m : I\to Y\) to a copyable state \(g \mathchoice{\,}{\,}{}{} m : I\to Z\) makes \(Y\) and \(Z\) necessarily independent in the sense that \[\tikzfig{positivity_unit}\] holds. Thus the positivity axiom can be also seen as a requirement that a deterministic variable cannot display correlation with other variables [28].
Our main example, \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), is a positive quasi-Markov category. One can prove this by adapting the proof for \(\mathsf{BorelStoch}\) [5] or by using the general results of [22] and the fact that \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) is the partialization of \(\mathsf{BorelStoch}\).
In categorical probability, conditionals [5], [20] also play a central role. However, in this paper, they are only of tangential relevance, and we will merely comment on them for readers familiar with the concept. Nonetheless, \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) does have conditionals [22].
Let us first recall some terminology introduced in earlier works such as [29], [30], and [31].
Let \(f : A \to X\) be a morphism in a quasi-Markov category. Then the domain of \(f\), denoted also by \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\), is the morphism \[\label{eq:domain} \tikzfig{domain}\tag{13}\]
By quasi-totality, it is easy to see that the domain of any morphism is copyable and an idempotent. For a total morphism, the domain is simply the identity. This matches with its semantics in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), where the domain of a morphism \(f : A \to X\) is the inclusion \(D_f \hookrightarrow A\), considered as the partial Markov kernel \(A\to A\) that acts as the identity on its domain \(D_f\) and is undefined elsewhere. It is therefore only a slight abuse of terminology to use “domain” for both \(D_f\) and for 13 .
In terms of domains, quasi-totality ([def:quasi-total]) amounts to every morphism absorbing its domain in the sense that \(f \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right) = f\) holds. Consequently, the domain of a quasi-total monomorphism is simply the identity, which matches the totality of [lem:mono95total].
Moreover, for arbitrary composable morphisms \(f\) and \(g\), we have \[\label{eq:dom95repeat} \tikzfig{dom_repeat}\tag{14}\] which can also be written as \(\mathrm{dom}\mathopen{}\mathclose{\left(f \mathchoice{\,}{\,}{}{} g}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \mathchoice{\,}{\,}{}{} g}\right)\). If \(g\) is moreover copyable, we also have \[\label{eq:dom95comp95copyable} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \mathchoice{\,}{\,}{}{} g = g \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f \mathchoice{\,}{\,}{}{} g}\right).\tag{15}\]
For any two parallel morphisms \(f, g : A \to X\) in a quasi-Markov category, we say that \(f\) extends \(g\), denoted \(f \sqsupseteq g\), if we have \[\label{eq:eq95on95domain} \tikzfig{eq_on_domain}\tag{16}\]
For example, \(\mathrm{del}_X : X \to I\) extends any morphism of type \(X \to I\). The extension relation \(\sqsupseteq\) is a partial order on each hom-set of a quasi-Markov category [29] (see also [21]). Moreover, assuming positivity, we can show that it gives rise to an enrichment in posets.
Let \(\mathsf{C}\) be a positive quasi-Markov category. Then the extension partial order \(\sqsupseteq\) makes \(\mathsf{C}\) a category monoidally enriched in posets, i.e. composition and tensor are monotone in each argument.
Proof. The fact that \(\sqsupseteq\) is preserved under tensoring is an immediate consequence of the fact that the copy is compatible with the tensor product. We therefore focus on the composition: Consider parallel morphisms \(f\) and \(g\) such that \(f \sqsupseteq g\) holds. We first show compatibility with pre-composition by a morphism \(h\), i.e.we show \({f \mathchoice{\,}{\,}{}{} h \sqsupseteq g \mathchoice{\,}{\,}{}{} h}\). Since \(\mathrm{del}{} \mathchoice{\,}{\,}{}{} g \mathchoice{\,}{\,}{}{} h\) is copyable by quasi-totality of \(g \mathchoice{\,}{\,}{}{} h\), positivity gives \[\tikzfig{quasi-MarkovEnrichmentPreCompLem}\] and thus we find \[\tikzfig{quasi-MarkovEnrichmentPreComp}\] as desired. To show compatibility with post-composition by a morphism \(k\), we need to prove \(k \mathchoice{\,}{\,}{}{} f \sqsupseteq k \mathchoice{\,}{\,}{}{} g\). Using the quasi-totality of \(g\) in combination with \(f \sqsupseteq g\), we get7 \[\tikzfig{quasi-MarkovEnrichmentPostComp}\] and therefore \[\tikzfig{quasi-MarkovEnrichmentPostCompConc}\] holds as desired. ◻
In \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), the extension ordering is exactly what one would expect: \(f \sqsupseteq g\) holds if and only if we have both \(D_f \supseteq D_g\) and that \(f\) and \(g\) agree when restricted to \(D_g\). Specifically, we have \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) if and only if \(D_f \supseteq D_g\) holds, so that the meet of \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\) and \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) is the partial Markov kernel \((D_f \cap D_g, \mathrm{id})\), which also equals \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) in this category (see [ex:par95borelstoch]).
This fact holds more generally, as we now show.
Let \(\mathsf{C}\) be a quasi-Markov category, and \(f : A \to X\), \(g: A \to Y\) two morphisms in \(\mathsf{C}\). The meet of \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\) and \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) is given by \[\label{eq:meet95of95domains} \tikzfig{meet_of_domains}\tag{17}\]
Proof. The fact that this morphism is a lower bound follows from \[\tikzfig{meet_lb}\] which establishes that \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\) extends it, and an analogous argument shows that so does \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\).
Now consider another lower bound \(h : A \to A\), which also extends the morphism from 17 . That is, we have \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \sqsupseteq h\), \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right) \sqsupseteq h\), and \(h \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\), which can be expanded to: \[\begin{gather} \tag{18}\tikzfig{meet_lb_2}\\ \tag{19}\tikzfig{meet_lb_4} \end{gather}\] Combining the two equations from 18 gives the first two equations in \[\tikzfig{meet_lb_5}\] while the last one follows directly from 19 upon discarding the output. In conclusion, the morphism from 17 is indeed the greatest common lower bound of \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\) and \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\). ◻
One of the basic properties of the extension partial order that we need in the following section is that copyability is preserved by restricting the domain of a morphism.
Consider two morphisms in a quasi-Markov category that satisfy \(f \sqsupseteq g\).
If \(f\) is copyable, then so is \(g\).
We have \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\).
If \(f\) is an idempotent, then \(f \mathchoice{\,}{\,}{}{} g = g\) holds.
If \(f\) is an identity, then \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right) = g\) holds.
Proof. The condition \(f \sqsupseteq g\) means that \(g = f \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\). Quasi-totality ensures that \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) is copyable, so the composite \(g\) is copyable provided that \(f\) is. Explicitly, \[\tikzfig{copyable_dom_rest}\] which is precisely saying that \(g\) is copyable.
For the second part, we need to prove \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\), which amounts to \[\label{eq:dom95monotone} \tikzfig{dom_monotone}\tag{20}\] where we use the definition of \(f \sqsupseteq g\) in the second equation.
For the third part, we conclude directly from the definition of the extension partial order: \[\tikzfig{idempotent_dom_rest}\] Part [it:domain95dom95rest] follows directly from 16 when we replace \(f\) by the identity. ◻
We now turn to infinite tensor products in quasi-Markov categories. These are particularly relevant to us, since we want to study empirical measures of infinite sequences of samples. The definition of Kolmogorov products has been introduced for Markov categories in [9] and generalized to CD categories in [8]. However, in the presence of non-total morphisms we will need to exercise care with respect to domains of definition while performing certain constructions that are standard in Markov categories. While a lax notion of Kolmogorov product suitable for quasi-Markov categories is introduced in [22], for the purposes of this article we will work with Kolmogorov products and domains of definition directly. Here we restrict ourselves to countable families, but it is worth noting that the definition (as well as the results below) generalize straightforwardly to arbitrary families of objects.
Let \((X_i)_{i \in \mathbb{N}}\) be a sequence of objects in a quasi-Markov category \(\mathsf{C}\). Then a limit cone in \(\mathsf{C}\) of the diagram \[\label{eq:kolmogorov95diagram} \begin{tikzcd} \dots \ar{r} & X_1 \otimes \dots \otimes X_n \ar{r} & \dots \ar{r} & X_1 \otimes X_2 \ar{r} & X_1, \end{tikzcd}\tag{21}\] in which the arrows are given by deletion of the last tensor factor, is a Kolmogorov product \(\bigotimes_{i \in \mathbb{N}} X_i\) if the following conditions hold:
The cone components \(\pi_n : \bigotimes_{i \in \mathbb{N}} X_i \to \bigotimes_{i \le n} X_i\) are deterministic;
The limit cone is preserved by \({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}\otimes \mathrm{id}_Y\) for every \(Y \in \mathsf{C}\).
In \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), countable Kolmogorov products exist and are (as in \(\mathsf{BorelStoch}\)) given by products of measurable spaces with their product \(\sigma\)-algebras [22].
In order to simplify the exposition, for positive integers \(m < n\) we write \[\label{eq:products95of95objects} X_m^n \coloneq \bigotimes_{i = m}^n X_i \qquad \qquad X_m^\mathbb{N}\coloneq \bigotimes_{i \ge m} X_i,\tag{22}\] where the latter is a countable Kolmogorov product as defined above. Similarly, for a family of morphisms \((f_i : X_i \to Y_i)_{i=m}^n\), we write \[\label{eq:products95of95morphisms} f_m^n \coloneq \bigotimes_{i = m}^n f_i\tag{23}\] for their parallel composite, which is of type \(X_m^n \to Y_m^n\).
Consider a family \({\mathopen{}\mathclose{\left(g_n : A \to X_1^n }\right)}_{n \in \mathbb{N}}\) that forms a cone over Diagram (21 ), meaning that its elements satisfy \(\mathrm{del}_{X_{n+1}} \mathchoice{\,}{\,}{}{} g_{n+1} = g_n\) for all \(n \in \mathbb{N}\). Then:
The morphisms \(g_n\) in the family have identical domains.
The domain of \(g : A \to X_1^\mathbb{N}\), the morphism induced by the universal property, is equal to the common domain of morphisms in the family.
The morphism \(g : A \to X_1^\mathbb{N}\) is copyable if and only if each \(g_n\) is copyable.
Proof. Claim [item:Kolmogorov95cone95domains] can be proven by induction. Since every marginalization map \({\mathrm{del}_{X_{n+1}} : X_1^{n+1}}\) \(\to X_1^{n}\) is total, we have \[\mathrm{dom}\mathopen{}\mathclose{\left(g_{n}}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(\mathrm{del}_{X_{n+1}} \mathchoice{\,}{\,}{}{} g_{n+1}}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(g_{n+1}}\right)\] for every \(n \in \mathbb{N}\), which proves the claim.
Claim [item:Kolmogorov95map95domain] follows from [item:Kolmogorov95cone95domains] and the assumption that the Kolmogorov cone projections are total, since we have \(g_n = \pi_n \mathchoice{\,}{\,}{}{} g\) by the universal property.
Claim [item:Kolmogorov95map95copyablity] is a consequence of the assumption that the Kolmogorov cone legs \(\pi_n\) are copyable by [def:kolmogorov]. In particular, if \(g : A \to X_1^\mathbb{N}\) is copyable, then each \(g_n = \pi_n \mathchoice{\,}{\,}{}{} g\) is copyable as a composite of copyable morphisms.
Conversely, if each \(g_n\) is copyable, then we have, for any \(n \in \mathbb{N}\), \[\label{eq:copyable95n} \tikzfig{copyable_n}\tag{24}\] Thanks to the fact that Kolmogorov products are preserved by tensor products, applying the universal property to the first output yields \[\label{eq:copyable95n952} \tikzfig{copyable_n_2}\tag{25}\] and doing the same for the second output shows that \(g\) itself is copyable. ◻
Unfortunately, this direct instantiation of the notion of Kolmogorov products from Markov categories is insufficient to perform some of the constructions we need in quasi-Markov categories. In particular, we would often like to have a version of the universal property that can be applied to cones that do not have identical domains, which by [lem:KP95dom95cop] [item:Kolmogorov95cone95domains] is not possible with plain Kolmogorov products.
For instance, in a Markov category one can construct an infinite parallel composite of morphisms \({f_i : X_i \to Y_i}\) as the unique morphism \(X_1^{\mathbb{N}} \to Y_1^{\mathbb{N}}\) induced by the cone given by the composites \({f_1^n \mathchoice{\,}{\,}{}{} \pi_n : X_1^{\mathbb{N}} \to Y_1^{n}}\). However, in a quasi-Markov category, these maps need not have the same domain; and hence they cannot form a cone over Diagram (21 ). Intuitively, the morphism \(f_1^n \mathchoice{\,}{\,}{}{} \pi_n\) is only defined on those sequences \((x_i)_{i \in \mathbb{N}}\) for which each the first \(n\) elements is in the domain of the corresponding \(f_i\). This is typically a smaller space as \(n\) increases, and hence the domains of the \(f^n \mathchoice{\,}{\,}{}{} \pi_n\) need not agree.
For this reason, when using the Kolmogorov product to construct a morphism \(X_1^{\mathbb{N}} \to Y_1^{\mathbb{N}}\) from a family of morphisms \(f_i : X_i \to Y_i\), the induced morphism should only be defined on those input sequences \({\mathopen{}\mathclose{\left(x_i}\right)}_{i \in \mathbb{N}}\) for which all \(f_i(x_i)\) are defined. This domain is the meet of the domains in the family \(\mathopen{}\mathclose{\left(f^n \mathchoice{\,}{\,}{}{} \pi_n}\right)_{n \in \mathbb{N}}\). Moreover, this meet is additionally directed, because the sequence of domains is decreasing. We will see that this is semantically related to \(\sigma\)-additivity of probability measures, since in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), countable meets of domains correspond to countable intersections of the associated measurable sets.
To ensure that Kolmogorov products behave in a manner reflecting their intended behavior in probability theory, we need the following more explicit handle on intersections of domains of morphisms.
A positive quasi-Markov category \(\mathsf{C}\) with poset enrichment given by the extension relation \(\sqsupseteq\) is termed \(\boldsymbol{\sigma}\)-continuous if:
The hom-sets of \(\mathsf{C}\) have countable directed meets in the sense that for any descending sequence of morphisms \(\mathopen{}\mathclose{\left(f_n : X \to Y }\right)_{n \in \mathbb{N}}\), the meet \(\bigwedge_{j \in \mathbb{N}} f_{j}\) exists;
This meet is preserved by sequential and parallel composition.
Property [it:count95meets95comp] means that we get an enrichment in the category of posets with countable directed meets and monotone maps which preserve those (with the Cartesian product as the monoidal structure).
Before we turn to proving that \(\sigma\)-continuity holds in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) in [prop:sigma95parborelstoch], let us illustrate its consequences. The common domain of two morphisms \(f, g : X \to Y\), i.e.the meet of their domains, is given by the composite \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) as we saw in [lem:meet95of95domains]. Moreover, this lemma also implies that the meet of domains is preserved both by sequential and parallel composition. [def:count95meets] extends this property to arbitrary morphisms and to countable directed meets. Based on this, \(\sigma\)-continuity allows us to construct infinite parallel composites of morphisms as follows.
Let \(\mathsf{C}\) be a positive and \(\sigma\)-continuous quasi-Markov category with countable Kolmogorov products. Consider a countable sequence of morphisms \(f_i : X_i \to Y_i\) in \(\mathsf{C}\). Then the composite morphisms (one for each \(n \in \mathbb{N}\)) \[\label{eq:finite95tensor95morphisms} X_1^{\mathbb{N}} \xrightarrow{\bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \pi_m}\right)} X_1^{\mathbb{N}} \xrightarrow{\pi_n} X_1^{n} \xrightarrow{f_1^n} Y_1^{n},\tag{26}\] expressed using [not:products95of95objects], form a cone over the Kolmogorov diagram from (21 ).
Proof. We start by noting that \(\mathrm{del}_{Y_{n+1}} \sqsupseteq\mathrm{del}_{Y_{n+1}} \mathchoice{\,}{\,}{}{} f_{n+1}\) holds by the definition of the extension order, which implies \[\label{eq:inf95tensor951} \tikzfig{inf_tensor_1}\tag{27}\] by the fact that \(\sqsupseteq\) is a poset enrichment ([prop:enrichment]). The left-hand side of 27 is equal to \(f_1^n \mathchoice{\,}{\,}{}{} \pi_n\) because the \(\pi_n\) are the limit cone components and hence satisfy \({\mathrm{del}_{X_{n+1}} \mathchoice{\,}{\,}{}{} \pi_{n+1} = \pi_n}\). This leads to an inclusion of domains, \[\label{eq:inf95tensor953} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^n \pi_n}\right) \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(f_1^{n+1} \pi_{n+1}}\right)\tag{28}\] by [lem:copyable95dom95rest] [it:dom95monotone] and thus also \[\label{eq:inf95tensor952} f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^{n+1} \pi_{n+1}}\right) = \mathrm{del}_{Y_{n+1}} \mathchoice{\,}{\,}{}{} f_1^{n+1} \mathchoice{\,}{\,}{}{} \pi_{n+1}. \qquad\tag{29}\]
28 means that the morphisms \(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \pi_m}\right)\) form a descending sequence and thus their countable meet exists by \(\sigma\)-continuity. Let us simplify the notation and denote it by \[\label{eq:inf95tensor95meet} \varphi \coloneq \bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right).\tag{30}\]
For any \(k \in \mathbb{N}\), we then have \[\label{eq:inf95tensor954} \begin{align} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^k \pi_k}\right) \mathchoice{\,}{\,}{}{} \varphi &= \bigwedge_{m \in \mathbb{N}} \mathopen{}\mathclose{\left[ \mathrm{dom}\mathopen{}\mathclose{\left(f_1^k \mathchoice{\,}{\,}{}{} \pi_k}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) }\right] \\ &= \bigwedge_{m \ge k} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) \\ &= \varphi , \end{align}\tag{31}\] where the first equation is by [def:count95meets] [it:count95meets95comp], the second by [lem:meet_of_domains,eq:inf_tensor_3], and the last one by repeated application of 28 again.
We can use these ingredients to establish the claim by combining [eq:inf_tensor_2,eq:inf_tensor_4] to get \[\begin{align} \mathrm{del}_{Y_{n+1}} \mathchoice{\,}{\,}{}{} f_1^{n+1} \mathchoice{\,}{\,}{}{} \pi_{n+1} \mathchoice{\,}{\,}{}{} \varphi &= f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^{n+1} \mathchoice{\,}{\,}{}{} \pi_{n+1}}\right) \mathchoice{\,}{\,}{}{} \varphi \\[2pt] &= f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \varphi, \end{align}\] which is the equation required to establish that the morphisms from 26 form a cone over the Kolmogorov diagram. ◻
Consequently, we can define the infinite parallel composite \(f_1^\mathbb{N}: X_1^{\mathbb{N}} \to Y_1^{\mathbb{N}}\) of the family \((f_i)_{i \in \mathbb{N}}\) as the unique morphism induced by the cone from [lem:inf95tensor] via the universal property of the Kolmogorov product \(Y_1^\mathbb{N}\). As we show in [lem:inf95tensor95domain] below, its domain is given by the meet \(\varphi\) from 30 .
[lem:inf95tensor] demonstrates that, under the assumption of \(\sigma\)-continuity, Kolmogorov products are not only limits over the diagram 21 in the usual sense, but also restriction limits in the sense of Cockett and Lack [32]. In their terminology, a lax cone over the diagram 21 is a family of morphisms \((g_n : A \to X_1^n)_{n \in \mathbb{N}}\) satisfying the lax commutativity conditions \(g_n \sqsupseteq\mathrm{del}_{X_{n+1}} \mathchoice{\,}{\,}{}{} g_{n+1}\) for all \(n \in \mathbb{N}\).
The proof of [lem:inf95tensor], in particular 29 , demonstrates that the composite morphisms \[X^{\mathbb{N}} \xrightarrow{\pi_n} X^n \xrightarrow{f_1^n} Y^n\] form such a lax cone. Moreover, by restricting each of them to their common domain \(\varphi\), we obtain a strict cone in the sense of [def:kolmogorov].
One could generalize [lem:inf95tensor] to show that given any lax cone \((A \xrightarrow{g_n} X_1^n)_{n \in \mathbb{N}}\), there is a unique morphism \(A \xrightarrow{g} X_1^n\) such that for all \(n\), we have \(g_n \sqsupseteq\pi_n \mathchoice{\,}{\,}{}{} g\) and moreover we also have \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right) = \bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(g_{m}}\right)\). This is precisely the universal property of a restriction limit as formulated in [33]. More on this perspective can be found in [22]. For the purposes of the current work, where only infinite parallel composites arise, it suffices to work with the products and meets explicitly as in [lem:inf95tensor].
Given the same assumptions as in [lem:inf95tensor], we have \[\label{eq:inf95tensor95proj} \pi_n \mathchoice{\,}{\,}{}{} f_1^\mathbb{N}= \bigwedge_{m \ge n} \mathopen{}\mathclose{\left( \mathrm{del}_{Y_{n+1}^m} \mathchoice{\,}{\,}{}{} f_1^m \mathchoice{\,}{\,}{}{} \pi_m }\right),\tag{32}\] i.e.the projection of the infinite tensor product \(f_1^\mathbb{N}\) onto \(Y_1^{n}\) is given by the meet of the projections of the finite tensor products \(f_1^m\).
Proof. By [lem:inf_tensor,eq:inf_tensor_3], we have the first equation in \[\label{eq:inf95tensor95proj95intermediate} \begin{align} \pi_n \mathchoice{\,}{\,}{}{} f_1^{\mathbb{N}} &= f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \bigwedge_{m \geq n} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \pi_m}\right) \\ &= \bigwedge_{m \ge n} \Bigl(f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f^m \pi_m}\right)\Bigr), \end{align}\tag{33}\] while the second one is an application of the assumption that countable meets are preserved by sequential composition ([def:count95meets]). For any \(m>n\), we can apply 29 iteratively to obtain \[f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f^m \pi_m}\right) = \mathrm{del}_{Y_{n+1}^m} \mathchoice{\,}{\,}{}{} f_1^m \mathchoice{\,}{\,}{}{} \pi_m,\] which also holds for \(m = n\) by quasi-totality. Plugging this into 33 yields the desired result. ◻
In the next result, we establish that the domain of the parallel composite of a family \((f_i)_{i \in \mathbb{N}}\) is the infinite parallel composite of the individual domains. Consequently, it becomes clear that \(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right)\) is an infinite parallel composite of copyable morphisms, and hence can be studied also from the perspective of restriction products and cartesian bicategories [32], [34].
Given the same assumptions as in [lem:inf95tensor], we have \[\label{eq:inf95tensor95domain} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right) = \bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) = \bigotimes_{i \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_i}\right).\tag{34}\]
Proof. Let us once again use the notation from 30 . In order to compute the domain of the infinite parallel composite, according to [lem:KP95dom95cop] [item:Kolmogorov95map95domain] we can equivalently compute the domain of either one of the legs of its cone. To this end, we find \[\begin{align} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \varphi}\right) &= \mathrm{dom}\mathopen{}\mathclose{\left(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^n \mathchoice{\,}{\,}{}{} \pi_n}\right) \mathchoice{\,}{\,}{}{} \varphi}\right) \\[2pt] &= \mathrm{dom}\mathopen{}\mathclose{\left(\varphi}\right) \end{align}\] where the first equation is by 14 and the second one by 31 . Since countable meets are preserved by sequential and parallel composition ([def:count95meets]), we can express \(\mathrm{dom}\mathopen{}\mathclose{\left(\varphi}\right)\) as \[\label{eq:count95meet95domain} \tikzfig{count_meet_domain_1} \;\;\; = \;\, \bigwedge_{m \in \mathbb{N}} \mathopen{}\mathclose{\left( \;\tikzfig{count_meet_domain_2} \, }\right) \;\; = \;\, \bigwedge_{m \in \mathbb{N}} \varphi_m\tag{35}\] where we denote \(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \pi_m}\right)\) by \(\varphi_m\), which satisfies \(\mathrm{dom}\mathopen{}\mathclose{\left(\varphi_m}\right) = \varphi_m\). Since the right-hand side of 35 equals \(\varphi\), this establishes \(\mathrm{dom}\mathopen{}\mathclose{\left(\varphi}\right) = \varphi\) and hence the first equality in 34 .
To prove the second equality, it suffices to consider its composition with \(\pi_n\) for each \(n \in \mathbb{N}\). Using [lem:inf95tensor95proj], we can compute \(\pi_n \mathchoice{\,}{\,}{}{} \bigotimes_{i \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_i}\right)\) as the meet of morphisms \[\tikzfig{dom_prod_marginal_3}\] over \(m \geq n\), where we have used the copyability of \(\pi_m\) as well as \(f_1^m = f_1^{n} \otimes f_{n+1}^m\) to establish the equation. Using \(\pi_n = \mathrm{del}_{X_{n+1}^m} \mathchoice{\,}{\,}{}{} \pi_m\) and \(\sigma\)-continuity, we thus obtain the first equation in \[\begin{align} \pi_n \mathchoice{\,}{\,}{}{} \bigotimes_{i \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_i}\right) &= \pi_n \mathchoice{\,}{\,}{}{} \bigwedge_{m \geq n} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) \\ &= \pi_n \mathchoice{\,}{\,}{}{} \bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right), \end{align}\] where the second equation is by 28 . By the universal property of Kolmogorov products, we have therefore shown the second equality in 34 . ◻
One can also state a version of [lem:KP95dom95cop] for the infinite parallel composite.
Given the same assumptions as in [lem:inf95tensor]:
If each \(f_i\) is copyable, then so is the infinite parallel composite \(f_1^\mathbb{N}\).
If each \(f_i\) is total, then so is \(f_1^\mathbb{N}\).
Proof. The first part follows from [lem:KP95dom95cop] [item:Kolmogorov95map95copyablity]. Indeed, each leg \(f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right)\) of the defining cone is a composite of copyable morphisms, where we make use of [lem:inf95tensor95domain].
The second follows from [lem:KP95dom95cop] [item:Kolmogorov95map95domain]. If each \(f_i\) is total, then so is each \(f^n \mathchoice{\,}{\,}{}{} \pi_n\). In this case the meet \(\bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f^m \mathchoice{\,}{\,}{}{} \pi_m}\right)\) is the identity, so that their composite is total as well. ◻
The converses of the two assertions in [lem:inf95tensor95cop] hold provided that all the morphisms \(f_i\) are equal to each other. While the case of totality is clear from definition, the converse for copyability can be shown as a consequence of the upcoming [prop:IID95inf95copy] and quasi-totality.
One of the most important properties that is ensured by \(\sigma\)-continuity is the functoriality of forming infinite parallel composites.
Let \(\mathsf{C}\) be a positive and \(\sigma\)-continuous quasi-Markov category with countable Kolmogorov products. Then the infinite parallel composite construction from [lem:inf95tensor] defines a functor \(\mathsf{C}^{\mathbb{N}} \to \mathsf{C}\).
Proof. The preservation of identities is straightforward to verify. Indeed, if \(f_1^n\) is given by \(\mathrm{id}_{X^n}\), then the morphism from 26 equals \(\pi_n\), i.e.we get the limit cone itself.
For the preservation of composites, consider sequences of morphisms \(f_i : X_i \to Y_i\) and \(g_i : Y_i \to Z_i\) for \(i \in \mathbb{N}\) in \(\mathsf{C}\), and define \(h_i \coloneq g_i \mathchoice{\,}{\,}{}{} f_i\). The task is to show that \[h_1^\mathbb{N}= g_1^\mathbb{N} \mathchoice{\,}{\,}{}{} f_1^\mathbb{N}.\] To obtain this, it suffices show that the projections of both sides onto \(Z_1^n\) coincide. According to [lem:inf95tensor95proj], applying \(\pi_n\) gives \[\label{eq:projection951} \pi_n \mathchoice{\,}{\,}{}{} h_1^\mathbb{N}= \bigwedge_{m \ge n} \mathopen{}\mathclose{\left( \mathrm{del}_{Z_{n+1}^m} \mathchoice{\,}{\,}{}{} g_1^m \mathchoice{\,}{\,}{}{} f_1^m \mathchoice{\,}{\,}{}{} \pi_m }\right)\tag{36}\] and \[\label{eq:projection952} \pi_n \mathchoice{\,}{\,}{}{} g_1^\mathbb{N} \mathchoice{\,}{\,}{}{} f_1^\mathbb{N}= \bigwedge_{m \ge n} \mathopen{}\mathclose{\left( \mathrm{del}_{Z_{n+1}^m} \mathchoice{\,}{\,}{}{} g_1^m \mathchoice{\,}{\,}{}{} \pi_m \mathchoice{\,}{\,}{}{} f_1^\mathbb{N}}\right),\tag{37}\] respectively, where we have used \(\sigma\)-continuity to pull \(f_1^\mathbb{N}\) inside the meet in the latter case. Using the definition of the infinite parallel composite and [lem:inf95tensor95domain], we also have \[\label{eq:projection953} \pi_m \mathchoice{\,}{\,}{}{} f_1^\mathbb{N}= f_1^m \mathchoice{\,}{\,}{}{} \pi_m \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right).\tag{38}\] Combining [eq:projection_1,eq:projection_2,eq:projection_3], we get \[\label{eq:projection954} \pi_n \mathchoice{\,}{\,}{}{} g_1^\mathbb{N} \mathchoice{\,}{\,}{}{} f_1^\mathbb{N}= \pi_n \mathchoice{\,}{\,}{}{} h_1^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right) = \pi_n \mathchoice{\,}{\,}{}{} h_1^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(h_1^\mathbb{N}}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right)\tag{39}\] where in the second step we use quasi-totality to replace \(h_1^\mathbb{N}\) by \(h_1^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(h_1^\mathbb{N}}\right)\). By [lem:meet95of95domains], the composite \(\mathrm{dom}\mathopen{}\mathclose{\left(h_1^\mathbb{N}}\right) \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right)\) equals the meet of these two morphisms, and so once we show \(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right) \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(h_1^\mathbb{N}}\right)\), we can drop \(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right)\) from the right-hand side of 39 and obtain the desired result.
To prove \(\mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right) \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(h_1^\mathbb{N}}\right)\), note that \(\mathrm{del}_{Y_{1}^m} \sqsupseteq\mathrm{del}_{Z_{1}^m} \mathchoice{\,}{\,}{}{} g_1^m\) trivially holds and implies \[\mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) \sqsupseteq\mathrm{dom}\mathopen{}\mathclose{\left(g_1^m \mathchoice{\,}{\,}{}{} f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right)\] by [prop:enrichment]. Thus, we also get \[\mathrm{dom}\mathopen{}\mathclose{\left(f_1^\mathbb{N}}\right) = \bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) \sqsupseteq\bigwedge_{m \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(g_1^m \mathchoice{\,}{\,}{}{} f_1^m \mathchoice{\,}{\,}{}{} \pi_m}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(h_1^\mathbb{N}}\right)\] by [lem:inf95tensor95domain] and the proof is complete. ◻
In order to make use of these results on \(\sigma\)-continuity for quasi-Markov categories in our path towards synthetic strong laws of large numbers, we must establish that this property holds in measure-theoretic probability.
\(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) is \(\sigma\)-continuous.
Proof. We can verify this explicitly via monotone \(\sigma\)-continuity of measures. We consider a generic countable descending chain of morphisms \({\mathopen{}\mathclose{\left(u_n : A \to X}\right)}_{n \in \mathbb{N}}\) in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) with representatives \[A \supseteq D_n \xrightarrow{f_n} X,\] where each \(f_n\) is a Markov kernel. First, let us prove the existence of their meet. By \(u_n \sqsupseteq u_{n+1}\) and the characterization of the extension relation in measure-theoretic probability ([ex:domext95PBS]), we have \[\label{eq:descending95kernels} D_n \supseteq D_{n+1} \qquad \text{and} \qquad f_{n+1} \mathopen{}\mathclose{\left( E \,\vert\, a}\right) = f_{n}\mathopen{}\mathclose{\left(E \,\vert\, a}\right)\tag{40}\] for all \(n\in\mathbb{N}\), all \(a \in D_{n+1}\), and all measurable \(E \subseteq X\). The intersection of all the domains \(D_f \mathrel{\vcenter{:}}= \bigcap_{n \in \mathbb{N}} D_n\) is measurable as a countable intersection of measurable sets. Moreover, we can define a Markov kernel \(f : D_f \to Y\) via \(f\mathopen{}\mathclose{\left(E \,\vert\, a}\right) \mathrel{\vcenter{:}}= f_n\mathopen{}\mathclose{\left(E \,\vert\, a}\right)\) by picking any \(n\), which is independent of \(n\) since the \(f_n\) agree on \(D_f\) by 40 . This gives us a partial Markov kernel \(u\) represented by \[A \supseteq D_f \xrightarrow{f} X.\] We argue that \(u\) is the meet of the chain we started with. To this end, consider any partial Markov kernel \(w\), represented by \[A \supseteq D_h \xrightarrow{h} X,\] which satisfies \(u_n \sqsupseteq w\) for all \(n\). By [ex:domext95PBS], we have \(D_n \supseteq D_h\) for all \(n\), which implies \(D_f \supseteq D_h\). Furthermore, for any \(a \in D_g\), we also have \({h \mathopen{}\mathclose{\left(E \,\vert\, a}\right) = f_n\mathopen{}\mathclose{\left(E \,\vert\, a}\right)}\), thus showing the desired \(u \sqsupseteq w\). This establishes the existence of countable directed meets in any hom-set of \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\).
To show that the meet \(u = \bigwedge_n u_n\) is preserved by tensoring, consider an arbitrary partial Markov kernel \(v\) represented by \[B \supseteq D_g \xrightarrow{g} Y.\] Then we have a descending chain with elements \(u_n \otimes v\) given by \[A \times B \supseteq D_n \times D_g \xrightarrow{f_n \otimes g} X \times Y.\] The meet \(\bigwedge_{n \in \mathbb{N}} \mathopen{}\mathclose{\left(u_n \otimes v }\right)\) has domain \[\bigcap_n \, \mathopen{}\mathclose{\left(D_n \times D_g}\right) = \biggl( \, \bigcap_n D_n \biggr) \times D_g = D_f \times D_g.\] On cylinder sets \(E \times F \subseteq X \times Y\), the meet gives the transition probability \[\bigwedge_n \, \mathopen{}\mathclose{\left(u_n \otimes v}\right) \bigl( E \otimes F \, \vert \, (a,b) \bigr) = f_n\mathopen{}\mathclose{\left(E \,\vert\, a}\right) \, g\mathopen{}\mathclose{\left(F \,\vert\, b}\right) = f\mathopen{}\mathclose{\left(E \,\vert\, a}\right) \, g\mathopen{}\mathclose{\left(F \,\vert\, b}\right)\] for all \(\mathopen{}\mathclose{\left(a,b}\right) \in D_f \times D_g\). Comparing on cylinder sets is enough to ensure that this coincides with \(f \otimes g\), and so we conclude \(\bigwedge_{n \in \mathbb{N}} \mathopen{}\mathclose{\left(u_n \otimes v }\right) = u \otimes v\) as needed.
Now we check compatibility of the above meet with post-composition by an arbitrary partial Markov kernel \(w\) represented by \[X \supseteq D_g \xrightarrow{g} Y.\] Recalling 9 , composites of the form \(w \mathchoice{\,}{\,}{}{} u_n\) have domain \(E_n = \mathopen{}\mathclose{\left\{ a \in D_n \quad \middle| }\right. \vphantom{\}}\) \(\mathopen{}\mathclose{\left. \vphantom{\{}f_n \mathopen{}\mathclose{\left(D_g \, \vert \, a }\right)= 1 }\right\}\), and they form a descending chain. Per the above construction of meets, \(\bigwedge_n \mathopen{}\mathclose{\left(w \mathchoice{\,}{\,}{}{} u_n}\right)\) has domain \[\begin{align} \bigcap_n E_n &= \@ifstar{\Set}{\Set*}{ a \in \bigcap_n D_n \forall n \in \mathbb{N}\; : \; f_n\mathopen{}\mathclose{\left(D_g \, \vert \, a}\right)= 1 } \\[2pt] &= \@ifstar{\Set}{\Set*}*[\Big]{ a \in D_f f \mathopen{}\mathclose{\left(D_g \, \vert \, a }\right)= 1 }, \end{align}\] where the second equality follows because \(f_n\mathopen{}\mathclose{\left(D_g \, \vert \, a}\right) = 1\) holds if and only if \(f\mathopen{}\mathclose{\left(D_g \, \vert \, a}\right) = 1\) does for any \(a \in \bigcap_n D_n = D_f\). This set is also the domain of \(w \mathchoice{\,}{\,}{}{} u\). Furthermore, on this domain, \(f_n\) and \(f\) are concentrated pointwise on \(D_g\), and act the same. Hence the composites act the same as well, and we have \(\bigwedge_n \mathopen{}\mathclose{\left(w \mathchoice{\,}{\,}{}{} u_n}\right) = w \mathchoice{\,}{\,}{}{} u\).
Finally, we check compatibility with pre-composition by an arbitrary partial Markov kernel \(v\) represented by \[B \supseteq D_g \xrightarrow{g} A.\] Each composite \(u_n \mathchoice{\,}{\,}{}{} v\) has domain \(F_n \mathrel{\vcenter{:}}= \@ifstar{\Set}{\Set*}{b \in D_g g\mathopen{}\mathclose{\left(D_n \, \vert \, b}\right) = 1 }\), and these again remain a descending chain. Therefore the meet \(\bigwedge_n \mathopen{}\mathclose{\left(u_n \mathchoice{\,}{\,}{}{} v}\right)\) has domain \[\label{eq:dom1} \bigcap_n F_n = \@ifstar{\Set}{\Set*}*[\Big]{ b \in D_g \forall n \in \mathbb{N}\; : \; g\mathopen{}\mathclose{\left(D_n \, \vert \, b}\right) = 1 }.\tag{41}\] On the other hand, the domain of \(u \mathchoice{\,}{\,}{}{} v\) is \[\label{eq:dom2} \@ifstar{\Set}{\Set*}{b \in D_g g\biggl( \,\bigcap_n D_n \, \Big\vert \, b \biggr) = 1 }.\tag{42}\] Since the \(D_n\) form a descending chain of measurable sets, and for any \(b \in D_g\) the probability measure \(g \mathopen{}\mathclose{\left({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}\, \vert \, b}\right)\) is \(\sigma\)-continuous from above [35], meaning \[g \biggl( \, \bigcap_n D_n \, \Big\vert \, b \biggr) = \inf_{n \in \mathbb{N}} g\mathopen{}\mathclose{\left(D_n \,\vert\, b }\right),\] we conclude that \(g \mathopen{}\mathclose{\left( D_n \, \vert \, b }\right) = 1\) holds for all \(n \in \mathbb{N}\) if and only if \(g\mathopen{}\mathclose{\left(\, \bigcap_n D_n \, \vert \, b }\right) = 1\) does. Therefore the two domains from 41 and 42 coincide. Moreover, on this domain \(g\) is concentrated entirely on \(D_f\) by construction. Since each \(f_n\) agrees pointwise with \(f\) on \(D_f\), the composites \(u_n \mathchoice{\,}{\,}{}{} v\) and \(u \mathchoice{\,}{\,}{}{} v\) coincide on their domain, hence establishing \(\bigwedge_n \mathopen{}\mathclose{\left(u_n \mathchoice{\,}{\,}{}{} v}\right) = u \mathchoice{\,}{\,}{}{} v\). ◻
Suppose now that all \(f_i : X_i \to Y_i\) are identical, which is the case of interest for us in the rest of this article. Then we also write \(X^\mathbb{N}\) for the Kolmogorov product \(\bigotimes_{i \in \mathbb{N}} X\) and refer to it as a Kolmogorov power. Similarly, we denote the infinite parallel composite of countably many instances of \(f\) by \({f^\mathbb{N}: X^\mathbb{N}\to Y^\mathbb{N}}\). Given any morphism \(f : A \to X\), we can also form a compatible family \(\mathopen{}\mathclose{\left( f^{(n)} : A \to X^n }\right)_{n \in \mathbb{N}}\), in the sense that it provides a cone over the Kolmogorov diagram 21 , by defining \[\label{eq:notation95fN} f^{(n)} \mathrel{\vcenter{:}}= f^n \mathchoice{\,}{\,}{}{} \mathrm{copy},\tag{43}\] i.e.\(f^{(n)}\) is the composite of the \(n\)-fold copy morphism \(\mathrm{copy}: A \to A^n\) followed by the \(n\)-fold tensor power of \(f\). Thanks to the quasi-totality of \(f\), this defines a cone over the Kolmogorov diagram (21 ). If the Kolmogorov product \(X^\mathbb{N}\) exists, we obtain a morphism \[\label{eq:IID} f^{(\mathbb{N})} : A \longrightarrow X^\mathbb{N},\tag{44}\] which commonly appears in categorical probability. It is the unique morphism \(A \to X^\mathbb{N}\) whose finite marginals are the 43 . Intuitively, it corresponds to a probabilistic process that produces infinitely many samples, which are conditionally independent given \(A\) and identically distributed.
For string-diagrammatic manipulations with such IID morphisms, we use the plate notation [13]: \[\label{eq:plate} \tikzfig{plate_notation}\tag{45}\] For \(f= \mathrm{id}_A\) the above construction gives us the \(\mathbb{N}\)-fold copy morphism \(\mathrm{id}^{(\mathbb{N})} : A \to A^\mathbb{N}\).
Under the additional assumption of \(\sigma\)-continuity, we can prove that IID morphisms indeed display conditional independence given \(A\) in the following sense.
Let \(\mathsf{C}\) be a positive and \(\sigma\)-continuous quasi-Markov category with countable Kolmogorov products. Then for any morphism \(f : A \to X\) in \(\mathsf{C}\), we have \[\label{eq:IID95inf95copy} f^{\mathopen{}\mathclose{\left(\mathbb{N}}\right)} = f^{\mathbb{N}} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})}.\tag{46}\]
Proof. Let us first show a useful intermediate result. Namely, our claim is that \(\mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\) is “countably-copyable” in the following sense: \[\label{eq:dom95inf95copyable} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right)^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} = \mathrm{id}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right).\tag{47}\] To show this, we use [lem:inf95tensor95domain] and \(\sigma\)-continuity to deduce \[\begin{align} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right)^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} &= \bigwedge_{n \in \mathbb{N}} \Bigl[ \mathrm{dom}\mathopen{}\mathclose{\left(f^n \mathchoice{\,}{\,}{}{} \pi_n}\right) \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} \Bigr] \\ &= \bigwedge_{n \in \mathbb{N}} \Bigl[ \mathrm{id}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})}}\right) \Bigr] \\ &= \mathrm{id}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \bigwedge_{n \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f^n \mathchoice{\,}{\,}{}{} \mathrm{id}^{(n)}}\right) = \mathrm{id}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right), \end{align}\] where the second equation is by 15 , the third one is by the definition of the \(\mathbb{N}\)-fold copy and \(\sigma\)-continuity, and the last one by copyability of domains which implies \(\mathrm{dom}\mathopen{}\mathclose{\left(f^{(n)}}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(f}\right)\).
Turning our attention to the claim 46 now, it suffices to show that the finite projections of both sides agree. For the left-hand side, we have \(\pi_n \mathchoice{\,}{\,}{}{} f^{\mathopen{}\mathclose{\left(\mathbb{N}}\right)} = f^n \mathchoice{\,}{\,}{}{} \mathrm{id}^{(n)}\) by construction. On the other hand, we can compute \[\begin{align} \pi_n \mathchoice{\,}{\,}{}{} f^{\mathbb{N}} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} &= f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right)^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} \\ &= f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right) \\ &= f^n \mathchoice{\,}{\,}{}{} \mathrm{id}^{(n)} \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f}\right) = f^n \mathchoice{\,}{\,}{}{} \mathrm{id}^{(n)}, \end{align}\] where the first equation is by the definition of the infinite parallel composite \(f^\mathbb{N}\) and [lem:inf95tensor95domain], the second one uses 47 , and the last two are as in the previous paragraph. Therefore the marginals agree for all \(n \in \mathbb{N}\), and we conclude \(f^{\mathopen{}\mathclose{\left(\mathbb{N}}\right)} = f^{\mathbb{N}} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})}\). ◻
Let \(\mathsf{C}\) be a quasi-Markov category with countable Kolmogorov products and consider two morphisms \(f \colon X \to Y\) and \(g \colon Y \to Z\).
If \(\mathsf{C}\) is positive and \(\sigma\)-continuous, then we have \[\label{eq:IID95naturality} \tikzfig{IID_naturality1}\tag{48}\]
If \(f\) is copyable, then we have \[\label{eq:IID95naturality2} \tikzfig{IID_naturality2}\tag{49}\]
Proof. The first equation is a direct consequence of [prop:inf_tensor_composition,prop:IID_inf_copy]. For the second, we consider the finite marginals to find \[\tikzfig{IID_naturality_finite}\] The first and third equalities use the definition of \(g^{\mathopen{}\mathclose{\left(\mathbb{N}}\right)}\) and \((g \circ f)^{\mathopen{}\mathclose{\left(\mathbb{N}}\right)}\), while the second one follows from the copyability of \(f\). ◻
In particular, we can now generalize 47 : Taking \(g = \mathrm{id}_Y\) in 49 and using [prop:IID95inf95copy] shows that if \(f\) is copyable, then it is also “countably-copyable”, in the sense of \[\label{eq:countably-copyable} f^\mathbb{N} \mathchoice{\,}{\,}{}{} \mathrm{id}^{(\mathbb{N})} = \mathrm{id}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} f.\tag{50}\]
For any injective function \(\sigma : \mathbb{N}\to \mathbb{N}\), we can apply the universal property to obtain an action on the Kolmogorov power \(X^\mathbb{N}\), which we denote by \[X^\sigma : X^\mathbb{N}\longrightarrow X^\mathbb{N}.\] It is the unique morphism whose finite marginals \(\pi_n \mathchoice{\,}{\,}{}{} X^\sigma\) are given by \(X^{\sigma{|_{n}}} \mathchoice{\,}{\,}{}{} \pi_m\) where we define \(X^{\sigma{|_{n}}} \colon X^{m} \to X^n\) with \(m \coloneq \max_{i \leq n}\{\sigma(i)\}\) to be the composite of discarding maps and structure isomorphisms which maps the \(i\)-th input to the \(\sigma^{-1}(i)\)-th output whenever \(i\) is in the forward image of \(\{1,\ldots,n\}\) under \(\sigma\) and discards the \(i\)-th input otherwise.8 See [9] and [13] for more details. By [lem:KP95dom95cop] and the fact that every \(X^{\sigma{|_{n}}} \mathchoice{\,}{\,}{}{} \pi_m\) is a deterministic morphism, we can also conclude that \(X^\sigma\) is deterministic.
It is not hard to show that the assignment \(\sigma \mapsto X^\sigma\) is contravariant. Indeed, if \(\tau : \mathbb{N}\to \mathbb{N}\) is another injective function, we have \[\label{eq:perm95contravariance} \pi_n \mathchoice{\,}{\,}{}{} X^\sigma \mathchoice{\,}{\,}{}{} X^\tau = X^{\sigma{|_{n}}} \mathchoice{\,}{\,}{}{} \pi_m \mathchoice{\,}{\,}{}{} X^\tau = X^{\sigma{|_{n}}} \mathchoice{\,}{\,}{}{} X^{\tau{|_{m}}} \mathchoice{\,}{\,}{}{} \pi_k = X^{(\tau \mathchoice{\,}{\,}{}{} \sigma){|_{n}}} \mathchoice{\,}{\,}{}{} \pi_k = \pi_n \mathchoice{\,}{\,}{}{} X^{\tau \mathchoice{\,}{\,}{}{} \sigma},\tag{51}\] where \(k \coloneq \max_{j \leq m}\{\tau(j)\}\) is also equal to \(\max_{i \leq n}\{\tau \mathchoice{\,}{\,}{}{} \sigma(i)\}\). Thus, we conclude \(X^\sigma \mathchoice{\,}{\,}{}{} X^\tau = X^{\tau \mathchoice{\,}{\,}{}{} \sigma}\).
We mainly consider \(X^\sigma\) in the case where \(\sigma\) is a finite permutation, which is a bijection that leaves all but finitely many elements of \(\mathbb{N}\) fixed. In this way, we obtain an action of the finite permutation group \(S_\infty\) on \(X^\mathbb{N}\). The morphisms fixed by this action are particularly relevant to the present work, as will become clearer in [sec:dF_obs_rep,sec:es_def].
Let \(\mathsf{C}\) be a quasi-Markov category such that the Kolmogorov power \(X^{\mathbb{N}}\) exists for an object \(X\). A morphism \(f: A \to X^{\mathbb{N}}\otimes Y\) is exchangeable in the first factor if \[\tikzfig{exchangeable}\] holds. If \(Y = I\), i.e.if \(f\) is of type \(A \to X^{\mathbb{N}}\), we simply say that \(f\) is exchangeable.
As one would expect, IID morphisms as defined in 2.4.3 are exchangeable:
Let \(\mathsf{C}\) be a quasi-Markov category and let \(X^\mathbb{N}\) be a Kolmogorov power. Then, for any \(f : A \to X\), the IID morphism \(f^{(\mathbb{N})} : A \to X^\mathbb{N}\) is exchangeable.
Proof. By the universal property, we need to show that \[\pi_n \mathchoice{\,}{\,}{}{} X^\sigma \mathchoice{\,}{\,}{}{} f^{(\mathbb{N})} = \pi_n \mathchoice{\,}{\,}{}{} f^{(\mathbb{N})}\] for any \(n \in \mathbb{N}\) and any finite permutation \(\sigma\).
The right-hand side is given by \(f^{(n)}\), which is also the right-hand side of 43 . Let us show that the left-hand side is the same. To this end, we use the definition of the marginals of \(X^\sigma\) with the notation \(X^{\sigma|_{n}}\) and \(m\coloneq \max_{i \leq n}\{\sigma(i)\}\) being just as in the paragraphs above [def:exchangeable]: \[\label{eq:fN95exchangeable95LHS} \begin{align} \pi_n \mathchoice{\,}{\,}{}{} X^\sigma \mathchoice{\,}{\,}{}{} f^{(\mathbb{N})} &= X^{\sigma{|_{n}}} \mathchoice{\,}{\,}{}{} \pi_m \mathchoice{\,}{\,}{}{} f^{(\mathbb{N})} \\ &= X^{\sigma{|_{n}}} \mathchoice{\,}{\,}{}{} f^{(m)} \\ &= f^{(n)} \end{align}\tag{52}\] The second equality in 52 follows by the definition of \(f^{(\mathbb{N})}\). The third one follows by the fact that \(X^{\sigma{|_{n}}}\) essentially discards \(m-n\) of the inputs, yielding \(f^{(n)}\) by quasi-totality of \(f\), and permutes the remaining \(n\) of them, which preserves \(f^{(n)}\). ◻
Just as finite tensor products, infinite parallel composites are also permutation-covariant in the following sense.
Let \(\mathsf{C}\) be a positive and \(\sigma\)-continuous quasi-Markov category with Kolmogorov powers \(X^\mathbb{N}\) and \(Y^\mathbb{N}\). For any morphism \(f : X \to Y\) in \(\mathsf{C}\) and a finite permutation \(\nu : \mathbb{N}\to \mathbb{N}\) we have \[\label{eq:perm-covariance} Y^\nu \mathchoice{\,}{\,}{}{} f^\mathbb{N}= f^\mathbb{N} \mathchoice{\,}{\,}{}{} X^\nu.\tag{53}\]
Proof. As usual, it suffices to prove that 53 holds when post-composed with an arbitrary finite projection. Applying \(\pi_n\) to the left-hand side yields (once again we use the notation \(X^{\nu|_{n}}\) and \(m\coloneq \max_{i \leq n}\{\nu(i)\}\) as in the paragraphs above [def:exchangeable]) \[\label{eq:perm-covariance951} \tikzfig{perm-covariance_1}\tag{54}\] where use the definition of \(Y^\nu\) (and \(X^\nu\)) in steps 1 and 4; the definition of \(f^\mathbb{N}\) and [lem:inf95tensor95domain] in step 2; the definition of \(Y^{\nu|_{n}}\) (and \(X^{\nu|_{n}}\)) and quasi-totality of \(f\) in step 3; and copyability of \(\pi_m\) in step 4. By [lem:inf95tensor95domain] and 31 , the right-hand side of 54 can be simplified to \[f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} X^\nu \mathchoice{\,}{\,}{}{} \bigwedge_{k \in \mathbb{N}} \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right).\] By the fact that the infinite meet is of a descending sequence (28 ), we can also write it as \[\label{eq:perm-covariance953} f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} X^\nu \mathchoice{\,}{\,}{}{} \bigwedge_{k \geq w} \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right) = f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \bigwedge_{k \geq w} \Bigl[ X^\nu \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right) \Bigr].\tag{55}\] for an arbitrary \(w \in \mathbb{N}\).
Let us pick the \(w\) such that \(\nu(i) = i = \nu^{-1}(i)\) holds for all \(i \geq w\), which is possible since \(\nu\) is a finite permutation. We now argue that \(X^\nu\) and \(\mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right)\) commute for any \(k \geq w\). By 51 , the former has inverse \(X^{\nu^{-1}}\) and thus we can express the composite \(X^\nu \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right)\) as \[\label{eq:perm-covariance952} \tikzfig{perm-covariance_2}\tag{56}\] where, thanks to our choice of \(w\), we can use \(k = \max_{i \leq k}\{\nu^{-1}(i)\}\) and the fact that \(X^{\nu^{-1}|_{k}}\) merely permutes the tensor factors of \(X^k\) (i.e.it involves no discarding maps). Thus, we get \[\label{eq:perm-covariance954} X^\nu \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right) \mathchoice{\,}{\,}{}{} X^\nu.\tag{57}\]
Combining [eq:perm-covariance_1,eq:perm-covariance_3,eq:perm-covariance_4], we thus obtain \[\begin{align} \pi_n \mathchoice{\,}{\,}{}{} Y^\nu \mathchoice{\,}{\,}{}{} f^\mathbb{N}&= f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \bigwedge_{k \geq w} \Bigl[ \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right) \mathchoice{\,}{\,}{}{} X^\nu \Bigr] \\ &= f^n \mathchoice{\,}{\,}{}{} \pi_n \mathchoice{\,}{\,}{}{} \bigwedge_{k \geq w} \Bigl[ \mathrm{dom}\mathopen{}\mathclose{\left(f^k \mathchoice{\,}{\,}{}{} \pi_k}\right) \Bigr] \mathchoice{\,}{\,}{}{} X^\nu \\ &= \pi_n \mathchoice{\,}{\,}{}{} f^\mathbb{N} \mathchoice{\,}{\,}{}{} X^\nu, \end{align}\] which completes the proof by the universal property of the Kolmogorov power \(Y^\mathbb{N}\). ◻
One can think of a Markov kernel either as a channel with a random outcome or as a deterministic map whose output is a probability distribution. Formulating this idea for Markov categories in general leads to the definition of representable Markov category [7]. We now extend this notion to quasi-Markov categories.
Let \(\mathsf{C}\) be a quasi-Markov category.
For \(X \in \mathsf{C}\), a distribution object is \(PX \in \mathsf{C}\) together with bijections \[\label{eq:representability} \mathsf{C}(A,X) \, \cong \, \mathsf{C}_{\rm cop}(A,PX)\tag{58}\] natural in \(A \in \mathsf{C}_{\rm cop}\).
A quasi-Markov category is representable if every object has a distribution object.
If \(f : X\to Y\) is a morphism in a representable quasi-Markov category \(\mathsf{C}\), then we denote its counterpart under 58 by \(f^\sharp : X\longrightarrow PY\).
The correspondence of 58 can be used to define a functor \(P\) that is right adjoint to the inclusion \(\mathsf{C}_{\rm cop} \hookrightarrow \mathsf{C}\). This adjunction induces a monad \((P,\mu,\delta)\) on \(\mathsf{C}_{\rm cop}\), which we also denote by \(P\), and \(\mathsf{C}\) can be seen as the Kleisli category of \(P\). The unit of the adjunction at \(X\) is a copyable morphism \[\delta_X : X\longrightarrow PX,\] while the counit of the adjunction at \(X\) is a morphism \[\mathsf{samp}_X : PX \longrightarrow X,\] namely the counterpart of the copyable \(\mathrm{id}_{PX}\) under 58 . The sampling morphism gives us a concrete implementation of Bijection 58 , i.e.we have \(f = \mathsf{samp}_X \mathchoice{\,}{\,}{}{} f^\sharp\) for every morphism \(f : A \to X\). In the opposite direction, we can write \(f^\sharp\) as \(Pf \mathchoice{\,}{\,}{}{} \delta_A\). Furthermore, since every morphism in \(\mathsf{C}(A,I)\) is trivially copyable by quasi-totality, we can conclude that \(\mathsf{samp}_I : PI\cong I\) is an isomorphism, making the monad \(P\) an affine monad.
One of the triangle identities is that each \(\delta_X\) is a section of \(\mathsf{samp}_X\). As a consequence, \(\delta_X\) is monic, and is thus total by [lem:mono95total]. We leave open the question as to whether \(\mathsf{samp}_X\) is total in general. At present, we only know how to ensure this fact under the stronger assumption of observational representability introduced in [def:obs95rep] below. Whenever the sampling maps are total, the bijection \({\mathsf{C}(A,X) \cong \mathsf{C}_{\rm cop}(A,PX)}\) restricts to a bijection \[\label{eq:representability95res} {\mathsf{C}_{\rm tot}(A,X) \,\cong\, \mathsf{C}_{\rm \mathrm{det}}(A,PX)}.\tag{59}\] for all objects \(A\) and \(X\). This also means that a morphism \(f\) is total if and only if \(f^\sharp\) is.
\(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) is representable, with \(PX\) being the measurable space of probability measures on \(X\), which is a standard Borel space again [6]. Indeed one obtains a natural bijection as in 58 by sending a partial Markov kernel \(f : A \to X\) to the partial measurable function \[\begin{align} f^\sharp : A & \longrightarrow PX \\ x & \longmapsto f({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}|x), \end{align}\] where the second row applies whenever \(x \in D_f\) and \(f^\sharp(x)\) is undefined otherwise. Then the above discussion instantiates to the following:
The unit \(\delta:X\to PX\) is the measurable function assigning to each \(x\in X\) the Dirac delta \(\delta_x\in PX\);
The counit \(\mathsf{samp}:PX\to X\) is the Markov kernel that takes a measure \(\mu \in PX\) as input and returns a sample from \(\mu\) as output. Formally, for all measurable \(T \subseteq X\), we have \[\mathsf{samp}(T|\mu) \;=\; \mu(T)\] for all measurable subsets \(T\subseteq X\).
In particular, since \(\mathsf{samp}\) is total, the monad \(P\) on \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelMeas}}}\right)\!\!\cong\!\! \mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)_{\rm cop}\) restricts to the Giry monad on \(\mathsf{BorelMeas}\), and we thus recover the standard fact that \(\mathsf{BorelStoch}\) is its Kleisli category [6].
In [8], a strengthening of representability has been introduced, which abstracts the idea that distinct measures can be distinguished by iterated sampling. More details about this axiom can be found in [27]. We generalize it now to the quasi-Markov setting.
A representable quasi-Markov category \(\mathsf{C}\) is observationally representable if for each \(X\), the collection of morphisms \((\mathsf{samp}^{(n)} : PX \to X^n)_{n \in \mathbb{N}}\) is jointly monic.9
If \(\mathsf{C}\) also has countable Kolmogorov products, then it is easy to see that observational representability is equivalent to \(\mathsf{samp}^{(\mathbb{N})} : PX \to X^\mathbb{N}\) being monic.
In an observationally representable quasi-Markov category \(\mathsf{C}\) with countable Kolmogorov products,10 every sampling morphism \(\mathsf{samp}: PX \to X\) is total. Furthermore, we have \[\label{eq:rep95ext} f \sqsupseteq g \; \iff \; f^\sharp \sqsupseteq g^\sharp\tag{60}\] for all morphisms \(f, g : A \to X\) in \(\mathsf{C}\).
As highlighted in 2.5, this also means that the restricted bijection 59 holds, and that a morphism \(f\) is total if and only if \(f^{\sharp}\) is.
Proof. As noted above, the morphism \(\mathsf{samp}^{(\mathbb{N})} : PX \to X^\mathbb{N}\) is a monomorphism by observational representability, and thus total by [lem:mono95total]. Since the cone components of a Kolmogorov product are assumed to be total, we get that \(\mathsf{samp}\), which can be obtained as \({\pi_1 \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})}}\), is itself total.
Totality of sampling means that for every morphism \(g : A \to X\), we have \[\label{eq:dom95of95det} \tikzfig{dom_of_det}\tag{61}\] which can be also written as \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right) = \mathrm{dom}\mathopen{}\mathclose{\left(g^\sharp}\right)\) by using the \(\mathrm{dom}\mathopen{}\mathclose{\left(g}\right)\) notation to refer to the domain of \(g\) ([def:domain]) and recalling that \(g=\mathsf{samp} \mathchoice{\,}{\,}{}{} g^{\sharp}\) holds. Since \(\delta\) is natural with respect to copyable morphisms, we have \[\label{eq:dom95sharp} (\mathrm{dom}\mathopen{}\mathclose{\left(g}\right))^\sharp = P\bigl( \mathrm{dom}\mathopen{}\mathclose{\left(g}\right) \bigr) \mathchoice{\,}{\,}{}{} \delta_A = \delta_X \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right).\tag{62}\] Thus we get the desired 60 via \[\begin{align} f \sqsupseteq g \; &\iff \; f \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right) = g \\ &\iff \; Pf \mathchoice{\,}{\,}{}{} (\mathrm{dom}\mathopen{}\mathclose{\left(g}\right))^\sharp = g^\sharp \\ &\iff \; f^\sharp \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g}\right) = g^\sharp \\ &\iff \; f^\sharp \mathchoice{\,}{\,}{}{} \mathrm{dom}\mathopen{}\mathclose{\left(g^\sharp}\right) = g^\sharp \\ &\iff \; f^\sharp \sqsupseteq g^\sharp \end{align}\] where the first and last equivalences are by definition, the second one is by Bijection 58 , the third one by 62 , and finally the fourth one by 61 . ◻
Our aim in the rest of this section is to show that observational representability can be derived from the existence of abstract de Finetti representations of exchangeable measures (and suitable compatibility conditions thereof).
Let \(\mathsf{C}\) be a quasi-Markov category \(\mathsf{C}\) with countable Kolmogorov products and \(X \in \mathsf{C}\). Then a de Finetti object for \(X\) is \(QX \in \mathsf{C}\) together with a morphism \(\ell : QX \to X\) such that:
The morphism \[\ell^{(\mathbb{N})} : QX \to X^{\mathbb{N}}\] makes \(QX\) into the equalizer of all finite permutations \({X}^{\sigma} : X^{\mathbb{N}} \to X^{\mathbb{N}}\).
This limit is preserved by \({{\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}} \otimes \mathrm{id}_Y\) for every object \(Y\).
In [3], we proved that if \(\mathsf{C}\) is an -compatibly representable Markov category with countable Kolmogorov products and conditionals, then \(PX\) together with \(\mathsf{samp}: PX \to X\) satisfies the existence part of the universal property required for a de Finetti object. In other words, this means that every exchangeable morphism \(p : A\to X^\mathbb{N}\) factors across \(\mathsf{samp}^{(\mathbb{N})}\). If the representability assumption is strengthened to observational representability, then every \(X\) has a de Finetti object given by \(PX\) [8].11\({}^{,}\)12 The universal property is illustrated by the diagram: \[\begin{tikzcd} &&& X^\mathbb{N}\arrow[dd,bend left,"X^\sigma"] \\ A \arrow[urrr,bend left=20,"p"]\arrow[drrr,bend right=20,swap,"p"] \ar{rr}[near end]{\mu} && PX \ar{ur}[swap,inner sep=0.5mm]{\mathsf{samp}^{(\mathbb{N})}} \ar{dr}{\mathsf{samp}^{(\mathbb{N})}} \\ &&& X^\mathbb{N} \end{tikzcd}\]
Taking \(A = I\) in \(\mathsf{BorelStoch}\), this says that every exchangeable probability measure \(p\) on \(X^\mathbb{N}\) can be expressed as a unique convex mixture of IID measures, i.e.it is in the form \[p(T_1\times\dots\times T_n \times X \times \dots ) \;=\; \int_{q\in PX} q(T_1)\cdots q(T_n)\,\mu(\mathrm{d}q)\] for a unique probability measure \(\mu\) on \(PX\), the so-called de Finetti measure of \(p\). Moreover, the analogous statement is true for every exchangeable Markov kernel \(p : A\to X^\mathbb{N}\) for general \(A\), which expresses the universal property in general.
The following result now can be thought of as an approximate converse.
Let \(\mathsf{C}\) be a quasi-Markov category with countable Kolmogorov products such that every object has a de Finetti object. Then \(\mathsf{C}\) is observationally representable with distribution objects \(QX\) and sampling morphisms \(\ell : QX \to X\).
This theorem and its proof are variations on [26], which is a similar result for involutive Markov categories. We provide the complete proof here to emphasize the role of quasi-totality.
Proof. We need to show that the morphism \(\ell : QX \to X\) gives a representation of the functor \({\mathsf{C}\mathopen{}\mathclose{\left( {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em},X}\right): \mathsf{C}_{\rm cop}^\mathrm{op}\to \mathsf{Set}}\). This is sufficient to also conclude observational representability, since \(\ell^{(\mathbb{N})}\) is monic as the universal morphism of an equalizer. Thus we need to show that for every \(A \in \mathsf{C}\), the mapping \[\ell \mathchoice{\,}{\,}{}{} {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}\; : \; \mathsf{C}_{\rm cop} (A, QX)\to \mathsf{C}(A,X)\] is a bijection.
Let us first prove the injectivity, so suppose that \(\ell \mathchoice{\,}{\,}{}{} f = \ell \mathchoice{\,}{\,}{}{} g\) holds for some copyable \(f,g : Z \to A\). Then we have \[\label{eq:dF95rep0} \tikzfig{dF_rep0}\tag{63}\] where we use [lem:IID95naturality] twice. Since \(\ell^{(\mathbb{N})}\) is monic, we obtain \(f = g\) as required.
To prove surjectivity, we consider an arbitrary morphism \(f : A \to X\) and aim to show that it factors through a copyable morphism of type \(A \to QX\). By the assumed properties of the de Finetti object \(QX\) as a limit, we can factor the exchangeable morphism \(f^{(\mathbb{N})} : A \to X^{\mathbb{N}}\) as \[\label{eq:exch95factorization} f^{(\mathbb{N})} = \ell^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mu\tag{64}\] for a suitable morphism \(\mu : A \to QX\). In the rest of the proof, we show that \(\mu\) must be copyable.
By the universal property of \(X^\mathbb{N}\), 64 implies \(f = \ell \mathchoice{\,}{\,}{}{} \mu\), and thus we can rewrite 64 as \[\tikzfig{dF_rep4}\] which upon composition with the finite projection \(\pi_n\) implies the same equality with \(\mathbb{N}\) replaced by any finite \(n \in \mathbb{N}\). Thinking of \(n\) as an \(n\)-element set, we can use these equations together with the definition of Kolmogorov products and associativity of copy to obtain \[\label{eq:dF95rep2} \tikzfig{dF_rep2_finite}\tag{65}\] where we omit an implicit isomorphism \(X^n \otimes X^n \cong X^{n \sqcup n}\), the choice of which is irrelevant by the exchangeability of the IID morphisms involved. Since 65 holds for any \(n\) and Kolmogorov products are preserved by tensor products, we can use the universal property to get \[\tikzfig{dF_rep5}\] and finally \[\label{eq:dF95rep6} \tikzfig{dF_rep6}\tag{66}\]
Since \(\ell^{(\mathbb{N})} \otimes\mathrm{id}\) is monic by virtue of the limit \(QX\) being preserved by tensor products, the morphism \(\ell^{(\mathbb{N})} \otimes\ell^{(\mathbb{N})}\) is also monic. Therefore, 66 implies that \(\mu\) is copyable, which proves the surjectivity of the map \(\ell \mathchoice{\,}{\,}{}{} {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}\). ◻
The key idea of this paper is that the limiting behaviour of infinite sequences of observations can be encapsulated by morphisms satisfying a few properties expressible in the language of quasi-Markov categories (see 3.1). We devote [sec:es_BorelStoch,sec:es_integration] to the construction of instances of such morphisms, i.e.of partial Markov kernels between standard Borel spaces. It is non-trivial to show that they satisfy the requisite properties, and we defer the technical proofs to 6. Nevertheless, these two sections are markedly different in style from the rest of the article in their heavier use of measure-theoretic rather than category-theoretic language.
Here we give our axiomatization of empirical sampling morphisms. As mentioned in the Introduction, in measure-theoretic probability we want to associate to suitable sequences \((x_i)_{i \in \mathbb{N}}\) of points in a measurable space \(X\) a probability measure formed out of limiting relative frequencies \[\lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \in T \}|}{n}.\] When such a limiting probability measure exists, we call it empirical measure. Sampling from this empirical measure gives a random element of \(X\). As mentioned in the Introduction, a number of subtleties arise in the precise constructions. For example, the limits above do not exist for every sequence. Therefore our constructions of empirical sampling morphisms will be partial morphisms in \(\mathsf{BorelStoch}\), or equivalently morphisms in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\). This is why we formulate the general definition in terms of quasi-Markov categories rather than Markov categories.
The following two key properties were motivated and informally discussed in the Introduction.
Let \(\mathsf{C}\) be a quasi-Markov category with countable Kolmogorov products and \(X \in \mathsf{C}\). An empirical sampling morphism for \(X\) is a morphism \[\mathsf{es}\: : \: X^\mathbb{N}\longrightarrow X\] satisfying the following conditions:
Permutation invariance: For every finite permutation \(\sigma\) of \(\mathbb{N}\), \(\mathsf{es}\) is invariant under pre-composition by the corresponding permutation \({X^\sigma : X^\mathbb{N}\to X^\mathbb{N}}\), we have \[\mathsf{es} \mathchoice{\,}{\,}{}{} X^\sigma \;=\; \mathsf{es}.\]
Empirical adequacy: If a morphism \(f : A \to X^\mathbb{N}\otimes Y\) is exchangeable in the first factor,13 then we have \[\label{eq:es95invariance} \tikzfig{empirical_distribution_axiom}\tag{67}\]
These two conditions are the general categorical formulations of the corresponding properties of empirical sampling mentioned in the Introduction.
The converse of Property [it:es95invariance] holds automatically: Any \(f\) satisfying 67 is exchangeable in the first factor, since the \(\mathsf{es}^{(\mathbb{N})}\) appearing in the diagram on the left is exchangeable by [lem:fN95exchangeable].
Constructing interesting examples of empirical sampling morphisms, which we devote [sec:es_BorelStoch,sec:es_integration] to, requires a fair amount of measure-theoretic details. Before doing so, let us note that we cannot expect empirical sampling morphisms to be natural transformations in \(X\), at least not in \(\mathsf{BorelStoch}\) (see [rem:es95not95natural]). Nevertheless, they can be transported along copyable retracts, which can be thought of as a weak form of naturality.
Let \(\mathsf{C}\) be a positive and \(\sigma\)-continuous quasi-Markov category with Kolmogorov powers \(X^\mathbb{N}\) and \(Y^\mathbb{N}\). Let \(\mathsf{es}_X : X^\mathbb{N}\to X\) be an empirical sampling morphism for \(X\). Then for any copyable morphism \(\iota : Y \to X\) with left inverse \(\pi : X \to Y\), the morphism \[\tikzfig{transfer_es}\] is an empirical sampling morphism for \(Y\).
Proof. The permutation invariance of \(\mathsf{es}_Y\) is a direct consequence of the naturality of braiding and the permutation invariance of \(\mathsf{es}_X\).
Concerning empirical adequacy, let \(f : A \to Y^{\mathbb{N}} \otimes Z\) be exchangeable in the first factor. Then we have \[\label{eq:transfer95es95proof295noplate} \tikzfig{transfer_es_proof2}\tag{68}\] where the first step uses that \(\iota^\mathbb{N}\) is copyable ([lem:inf95tensor95cop]) as well as [lem:IID95naturality], the second is by empirical adequacy of \(\mathsf{es}_X\) (exchangeability of \(\iota^\mathbb{N} \mathchoice{\,}{\,}{}{} f\) in the first factor follows from [lem:perm-covariance]), and the last one by [prop:inf95tensor95composition]. ◻
Our goal now is to construct an empirical sampling morphism for every standard Borel space ([cor:standard95borel95es]). By Kuratowski’s theorem, it is enough to show that every finite set as well as \(\mathbb{N}\) and \(\mathbb{R}\), with their usual Borel \(\sigma\)-algebras, have empirical sampling morphisms. In fact, since every standard Borel space is a measurable retract of \(\mathbb{R}\), by [lem:transfer95es] it would even be sufficient to construct an empirical sampling morphism for \(\mathbb{R}\) and we would automatically get it for every standard Borel space. However, in order to progressively build up to \(\mathbb{R}\) as the most challenging case, we start with the finite case, followed by \(\mathbb{N}\), and only then deal with all the nuances in the continuous case.
Proofs of the theorems stated here can be found in 6.
Let \(F\) be a finite set equipped with the discrete \(\sigma\)-algebra. For a given sequence \((x_i) \in F^\mathbb{N}\) and a subset \(T \subseteq F\) we define \[\label{eq:es95finite} \mathsf{es}_F \bigl( T | (x_i) \bigr) \coloneq \lim_{n \to \infty} \frac{\@ifstar{\abs}{\abs*}{ \@ifstar{\Set}{\Set*}{i \le n x_i \in T }}}{n}\tag{69}\] whenever this limit exists for all \(T\) and leave it undefined otherwise.
Given any finite set \(F\), the kernel \(\mathsf{es}_F : F^\mathbb{N}\to F\) defined as in 69 is an empirical sampling morphism for \(F\) in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\).
In the infinite case we would like to use the same ideas, but this meets further subtleties. For example, the sequence \((1,2,3,\dots)\) over \(\mathbb{N}\) has well-defined relative frequencies in the limit, since every single number has limiting frequency zero. Therefore, even though all the relative frequencies have well-defined limits, \(\sigma\)-additivity fails and we do not get a probability measure on \(\mathbb{N}\). So already for countably infinite spaces, the definition of \(\mathsf{es}\) is not as straightforward as in the finite case, and only requiring the limits to exist is not enough. To avoid situations such as the above case, we require additionally the following equivalent conditions.
For every sequence \((x_i)\in \mathbb{N}^\mathbb{N}\) for which the limiting relative frequencies of singletons \[\lim_{n \to \infty} \frac{|\{ i \le n \mid x_i = t \}|}{n}\] exist, the following properties are equivalent:
The sequence of finite empirical measures is tight:14 For every \(\varepsilon> 0\) there is a \(t \in \mathbb{N}\) such that for all \(n \gg 1\), we have \[\label{eq:es95tight} \frac{|\{ i \le n \mid x_i \ge t \}|}{n} < \varepsilon.\tag{70}\]
The limits \[\label{eq:es95uniform} \lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \le t \}|}{n}\tag{71}\] exist uniformly in \(t \in \mathbb{N}\).15
The limiting relative frequencies of singletons sum up to \(1\), \[\label{eq:es95sum} \sum_{t \in \mathbb{N}} \lim_{n \to \infty} \frac{|\{ i \le n \mid x_i = t \}|}{n} = 1.\tag{72}\]
Whenever these conditions are satisfied, then for every \(T \subseteq \mathbb{N}\), its probability coincides with its limiting relative frequency, \[\label{eq:es95additive} \sum_{t \in T} \lim_{n \to \infty} \frac{|\{ i \le n \mid x_i = t \}|}{n} = \lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \in T \}|}{n}.\tag{73}\]
Informally, one may think of the tightness property as saying that no mass should “escape to infinity”. All three properties fail for the sequence \((1,2,3,\dots)\).
Proof. The tightness condition (Property [it:es95tight]) implies that the limits \[\lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \ge t \}|}{n}\] are uniform in \(t\): For a given \(\varepsilon> 0\) and large \(t\), the right-hand side is less than \(\varepsilon\) for every \(n\), and therefore we are effectively dealing with a finite range of \(t\), where uniform convergence is trivial. Considering the complementary events (characterized by \(x_i < t\)) instead now shows that [it:es95uniform] holds. The converse follows by similar arguments.
The equivalence with [it:es95norm] follows by standard conditions on the interchange of limit and summation [36], since the tightness is exactly the statement that the sums \(\sum_{t \in \mathbb{N}} \frac{|\{ i \le n \mid x_i = t \}|}{n}\) converge uniformly in \(n\).
Let us now show 73 , i.e.that the probability of any \(T \subseteq \mathbb{N}\) coincides with its limiting relative frequency. The inequality \(\le\) follows easily by taking the supremum over all finite subsets of \(T\). The equality then follows upon combining the same inequality applied to \(\mathbb{N}\setminus T\) combined with the normalization condition given by 72 . ◻
Let \(\mathbb{N}\) be equipped with the discrete \(\sigma\)-algebra. We define \(\mathsf{es}_\mathbb{N}: \mathbb{N}^\mathbb{N}\to \mathbb{N}\) as the partial Markov kernel where:
A sequence \((x_i)\) belongs to \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{N}}\right)\) if and only if it satisfies Property [it:es95uniform] above.
In this case, we take \[\label{eq:es95countable} \mathsf{es}_\mathbb{N}\bigl(T \,|\, (x_n) \bigr) \coloneq \lim_{n \to \infty} \frac{ \@ifstar{\abs}{\abs*}{ \@ifstar{\Set}{\Set*}{ i \le n x_i \in T }}}{n} .\tag{74}\] for every \(T \subseteq \mathbb{N}\).
The partial Markov kernel \(\mathsf{es}_\mathbb{N}: \mathbb{N}^\mathbb{N}\to \mathbb{N}\) from [def:es95N] is an empirical sampling morphism for \(\mathbb{N}\) in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\).
Let us now turn to the construction of an empirical sampling morphism for \(\mathbb{R}\). As explained in the Introduction, we now cannot even expect the equation \[\label{eq:es95rel95freq} \mathsf{es}_\mathbb{R}\bigl( T | (x_i) \bigr) = \lim_{n \to \infty} \frac{ \@ifstar{\abs}{\abs*}{\{ i \le n \mid x_i \in T\}}}{n}\tag{75}\] to hold for all measurable \(T\). Indeed, sequences over \(\mathbb{R}\) with all elements mutually distinct are generic, and so the failure of \(\sigma\)-additivity mentioned for case of the very special sequence \((1,2,3,\ldots)\) in \(\mathbb{N}\) would now be a generic feature of elements of \(\mathbb{R}^\mathbb{N}\).
We therefore need to relax the requirement that 75 holds for all measurable sets \(T\) to a smaller class of events. In the case of \(\mathbb{N}\) above, we characterize the viable sequences by requiring the relative frequencies of events \(T = \{1,2, \ldots, t\}\) to converge uniformly in \(t\) ([prop:eq95uniform]). Similarly, let us consider subsets of the form \(T=(-\infty,t]\) here. In other words, we view probability measures through their cumulative distribution functions (CDF), which are monotone right continuous functions \(F : \mathbb{R}\to [0,1]\) satisfying \[\label{limit95cdf} \lim_{t \to -\infty} F(t) = 0, \qquad \lim_{t \to \infty} F(t) = 1.\tag{76}\] It is a basic fact that the probability measures \(\mu\) on \(\mathbb{R}\) are in bijection with these functions, according to the assignment \(F(t) \mathrel{\vcenter{:}}= \mu((-\infty,t])\) for all \(t \in \mathbb{R}\). We can therefore define a probability measure \(\mathsf{es}_\mathbb{R}({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}| (x_i))\) on \(\mathbb{R}\) by specifying its CDF, as long as we ensure that this function has the requisite properties. Moreover, the right continuity determines such a function uniquely from its values on \(\mathbb{Q}\), as every monotone and right continuous function on \(\mathbb{Q}\) satisfying 76 extends uniquely to such a function on \(\mathbb{R}\). Therefore from now on, we consider the domain of CDFs to be \(\mathbb{Q}\). Its countability facilitates our arguments for measurability.
This discussion motivates the following construction of an empirical sampling morphism for \(\mathbb{R}\).
Let \(\mathbb{R}\) be equipped with its Borel \(\sigma\)-algebra. We define \(\mathsf{es}_\mathbb{R}: \mathbb{R}^\mathbb{N}\to \mathbb{R}\) as the partial Markov kernel where:
A sequence \((x_i)\) belongs to \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) if and only if the limits \[\label{eq:es95cdf} \lim_{n \to \infty} \frac{ \@ifstar{\abs}{\abs*}{\{ i \le n \mid x_i \le t\}}}{n}\tag{77}\] exist uniformly in \(t \in \mathbb{Q}\).
In this case, we define \(\mathsf{es}_\mathbb{R}({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}|(x_i))\) to be the unique probability measure on \(\mathbb{R}\) satisfying \[\label{eq:es95intervals} \mathsf{es}_\mathbb{R}\bigl(T \,|\, (x_i)\bigr) = \lim_{n \to \infty} \frac{ \@ifstar{\abs}{\abs*}{\{ i \le n \mid x_i \in T\}}}{n}\tag{78}\] for all intervals \(T \subseteq \mathbb{R}\).
A priori it is not clear whether Equation 78 defines a probability measure at all, since it does not construct the measure explicitly. While the uniqueness of the measure is clear from the fact that intervals form a generating \(\pi\)-system for Borel sets, the existence is most easily seen via standard properties of cumulative distribution functions. We spell this out in the proof of the following result (which can be found in 6). As detailed there, the uniformity of the limit plays a role and indeed guarantees that 77 defines a CDF.
The partial Markov kernel \(\mathsf{es}_\mathbb{R}: \mathbb{R}^\mathbb{N}\to \mathbb{R}\) from [def:es95R] is an empirical sampling morphism for \(\mathbb{R}\) in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\).
We illustrate \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) with two simple examples, and compare it with the weak convergence of empirical measures as in 3 .
The sequence \((1, 1/2, 1/3, \ldots)\) has well-defined limiting relative frequencies given by \[\lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \le t\}|}{n} = \begin{cases} 1 & \text{if t > 0}, \\ 0 & \text{if t \le 0}. \end{cases}\] But the convergence is not uniform in \(t\). Indeed this limit function is not a CDF, and therefore does not correspond to a probability measure. The sequence of empirical measures, however, converges weakly to \(\delta_0\), which gives empirical probability \(1\) to the singleton event \(\{0\}\), despite that fact that \(0\) never appears in the sequence.
The similar sequence \((-1, -1/2, -1/3, \ldots)\) also has well-defined limiting relative frequencies given by \[\lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \le t\}|}{n} = \begin{cases} 1 & \text{if t \ge 0}, \\ 0 & \text{if t < 0}, \end{cases}\] and again the finite empirical measures converge weakly to \(\delta_0\). However, now the convergence of CDFs is uniform in \(t\), and therefore this sequence belongs to \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) and its empirical measure is \(\delta_0\). Once again \(0\) does not appear in the sequence.
This shows that \(\mathsf{es}_\mathbb{R}\) is not invariant under the isomorphism \(x \mapsto -x\) of \(\mathbb{R}\) and thus that empirical sampling morphisms are not unique. In fact, we construct another inequivalent empirical sampling morphism for \(\mathbb{R}\) in 3.3.
It is conceivable that the domain of \(\mathsf{es}_\mathbb{R}\) could be extended to include both of the above sequences, e.g.by requiring the weak convergence of finite empirical measures instead of the uniform convergence of the CDF. The considerations of Austin and Panchenko [24] suggest that this could indeed be the case on \([0,1]\), but we have not explored this possibility further so far.
In discrepancy theory [37], an important topic is the study of sequences \((x_i)\) whose finite empirical measures converge quickly to the uniform distribution on \([0,1]\). In this context, one studies the speed of convergence also in terms of the sup-norm-distance between the corresponding CDFs. This matches our requirement of uniform convergence in 77 .
In \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), every standard Borel space \(X\) admits an empirical sampling morphism.
Proof. By Kuratowski’s theorem, every standard Borel space is either finite or isomorphic to \(\mathbb{N}\) with the discrete \(\sigma\)-algebra or to \(\mathbb{R}\) with the Borel \(\sigma\)-algebra. By [lem:finite_es,lem:countable_es,lem:real_es], these cases are covered. Moreover, by [lem:transfer95es], we know that empirical sampling morphisms can be transferred along isomorphisms. ◻
By applying [lem:transfer95es] to the empirical sampling morphism \(\mathsf{es}_\mathbb{R}\), we can construct an empirical sampling morphism on \(\mathbb{N}\subseteq \mathbb{R}\) and on any finite subset \(F \subseteq \mathbb{R}\). This exactly reproduces the empirical sampling morphisms \(\mathsf{es}_F\) and \(\mathsf{es}_\mathbb{N}\) from [def:es_finite,def:es_N] respectively. In particular, it is easy to check that any sequence in \(\mathbb{N}\) belongs to the domain of \(\mathsf{es}_\mathbb{N}\) if and only if it is in the domain of \(\mathsf{es}_\mathbb{R}\).
We leave open the question of whether empirical sampling morphisms exist for other kinds of measurable spaces, and what kind of structure is needed in order to construct them.
Before we conclude this section, let us also discuss why the naturality of empirical sampling morphisms cannot hold in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\). We already saw that our construction of \(\mathsf{es}_\mathbb{R}\) is not invariant under isomorphisms, since [ex:es95domain] shows that its domain is not invariant under the map \(x \mapsto -x\).
Given that an empirical sampling morphism exists on every object of \(\mathsf{BorelStoch}\), one might ask whether these constitute can be constructed as a natural transformation, in the sense that the square \[\label{eq:es95naturality} \begin{tikzcd}[row sep=small] {X^\mathbb{N}} && X \\ & \\ {Y^\mathbb{N}} && Y \arrow["{\mathsf{es}_Y}"', from=3-1, to=3-3] \arrow["{f^\mathbb{N}}"', from=1-1, to=3-1] \arrow["f", from=1-3, to=3-3] \arrow["{\mathsf{es}_X}", from=1-1, to=1-3] \end{tikzcd}\tag{79}\] commutes for every measurable map \(f : X \to Y\). However, naturality is too much to ask for in general, because then taking \(f \mathrel{\vcenter{:}}= \mathrm{del}_X\) shows that \(\mathsf{es}_X\) would have to be total. Although this could be achieved at least for finite \(X\), e.g. by using ultralimits in 69 , this is not what we want, since the very existence of the limit is an important part of results like the Glivenko–Cantelli theorem ([thm:glivenko]).
More plausibly, one might hope for empirical sampling morphisms to satisfy lax naturality instead, by which we mean \[\label{eq:es95lax95naturality} \mathsf{es}_Y \mathchoice{\,}{\,}{}{} f^\mathbb{N}\sqsupseteq f \mathchoice{\,}{\,}{}{} \mathsf{es}_X\tag{80}\] for every \(f\), where \(\sqsupseteq\) is the extension relation of [def:dom95ext]. In \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) and for total \(f\), this states that whenever a sequence \((x_i)\) has a well-defined empirical measure, then the image sequence \((f(x_i))\) has an empirical measure as well, and it is given by the pushforward measure. [lem:relu95lax95naturality] gives one example where this holds. However, lax naturality must fail in general, since it entails the empirical sampling morphism on \(\mathbb{R}\) to be total, and we already noted that this is not desirable.
To prove this, take any diffuse probability measure \(\mu\) on \(\mathbb{R}\). Sampling from \(\mu\) produces a sequence of mutually distinct elements with probability \(1\), and therefore there must be at least one such sequence \((x_i)\) in \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}}\right)\) by empirical adequacy. Take any other sequence \((y_i) \in \mathbb{R}^\mathbb{N}\). There exists a measurable function \(f\) satisfying \(f(x_i) = y_i\) for all \(i\). Lax naturality thus implies \((y_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}}\right)\) and consequently that \(\mathsf{es}\) is total.
Even though we have now shown that every object in the quasi-Markov category \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) has an empirical sampling morphism, we have also seen how delicate is the choice of its domain. We can liken this choice to the choice of a topology for a space — it specifies for which sequences do we consider their limiting empirical measure to be well-defined. In intuitive terms, enlarging the domain makes it easier for statements involving \(\mathsf{es}\) to hold with high probability (e.g.with probability \(1\)). On the other hand, restricting the domain can encode additional properties or assumptions about the sequences considered.
Given a sequence \((x_i)\in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}}\right)\) and any bounded measurable function \(f : X \to \mathbb{R}\), one might hope that its integral is given by the empirical average of \(f\) as in the right-hand side of \[\label{eq:es95integral} \int_{y \in X} f(y) \, \mathsf{es}\bigl(\mathrm{d}y \,|\, (x_i) \bigr) \stackrel{?}{=} \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n f(x_i).\tag{81}\] The reason for why one might expect this is because its finite analogue trivially holds: The expectation value of \(f\) with respect to the finite empirical measure from 3 is the empirical average \(\frac{1}{n} \sum_{i=1}^n f(x_i)\).
It is not hard to show that also the full version of 81 holds for any finite \(X\). However, it is too much to hope for in general: For instance, take \(X = \mathbb{R}\) and any sequence whose empirical measure has no atoms, and let \(f\) be the indicator function of the support \(\{x_i\}_{i \in \mathbb{N}}\) of the sequence. Then the left-hand side of 81 is \(0\) while its right-hand side is \(1\).
The aim of this section is to show that the domain of \(\mathsf{es}_\mathbb{R}\) from [def:es95R] can be restricted in such a way that
81 holds for \(f = \mathrm{id}\), and
the permutation invariance and empirical adequacy axioms still hold.
To begin our analysis, note the following weaker statement that is true also for the original \(\mathsf{es}_\mathbb{R}\), and with the same proof also for \(\mathsf{es}_\mathbb{N}\) (in which case the continuity is trivial).
81 holds for \(\mathsf{es}_\mathbb{R}\) from [def:es95R] and for every function \({f : \mathbb{R}\to \mathbb{R}}\) for which the left and right limits \[\lim_{s \nearrow t} f(s), \qquad \lim_{s \searrow t} f(s)\] exist and are finite for every \(t \in \mathbb{R}\), as well as for \(t = +\infty\) (left limit only) and \(t = -\infty\) (right limit only).
The following proof uses the fact that every such function is a uniform limit of step functions. Thus, every such function is measurable and bounded.
Proof. By definition of \(\mathsf{es}_\mathbb{R}\), the desired 81 holds for \(f = 1_{(-\infty,t]}\) for all \(t \in \mathbb{R}\). We show first that it also holds for indicator functions of the form \(f = 1_{(-\infty,t)}\). This is because by the assumed uniform convergence, the left limits of the finite empirical CDFs converge to the left limit of the limiting CDF. By combining these two cases for \(f\) and using linearity, it follows that 81 holds for all step functions.
Moreover, clearly 81 is preserved under uniform limits. Therefore it holds for all functions that can be written as uniform limits of step functions. On compact intervals, it is a standard fact that such functions are exactly those with left and right limits [38]. The same arguments also prove the relevant statement in the case of \(\mathbb{R}\) (although only the converse inclusion is needed). ◻
As a special case of [prop:es95integral], note that every continuous function \(f\) which converges at both \(\pm \infty\) necessarily satisfies 81 . However, we would like the equation to hold also for suitable unbounded \(f\), and in particular for \(f = \mathrm{id}_\mathbb{R}\). The reason is that the right-hand side of 81 then becomes the empirical average appearing in the statement of the strong law of large numbers. By relating it to the mean of the empirical measure, we will show that our synthetic strong law of large numbers ([cor:genericLLN]) indeed recovers the standard result.
As the following example shows, this is not true for the empirical sampling morphisms from 3.2.
Consider the sequence \((x_n)\) over \(\mathbb{N}\) given by \[x_n \mathrel{\vcenter{:}}= \begin{cases} n + 1 & \text{if n is a power of 2}, \\ 1 & \text{otherwise}. \end{cases}\] Then the limit \[\lim_{n \to \infty} \frac{|\{ i \le n \mid x_i \le t\}|}{n}\] of relative frequencies is equal to \(1\) for every \(t \in \mathbb{N}\),16 since almost all elements of the sequence are one. The convergence is uniform by monotonicity in \(t\). Therefore this sequence lies in \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{N}}\right)\) and we have \[\mathsf{es}_\mathbb{N}\bigl( {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}\,|\, (x_n) \bigr) = \delta_1.\] By [rem:es95relation], the same holds when considering \((x_n)\) as a sequence in \(\mathbb{R}\), and for the map \(\mathsf{es}_\mathbb{R}\).
Consider now the condition 81 for \(f=\mathrm{id}\), which gives \[\label{eq:emp95av} \int_{y \in \mathbb{R}} y \, \mathsf{es}_\mathbb{R}\bigl(\mathrm{d}y \,|\, (x_n) \bigr) \stackrel{?}{=} \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i.\tag{82}\] The left-hand side evaluates to \(1\), while the limit on the right-hand side does not even exist: The sequence of averages oscillates between \(1\) and \(3/2\) indefinitely.
Let us rectify this issue by constructing a revised empirical sampling morphism \(\overline{\mathsf{es}}_{\mathbb{R}}\). It coincides with \(\mathsf{es}_\mathbb{R}\), except in that its domain is restricted such that 82 is guaranteed to hold.
The partial Markov kernel \(\overline{\mathsf{es}}_{\mathbb{R}} : \mathbb{R}^\mathbb{N}\to \mathbb{R}\) is defined just as \(\mathsf{es}_\mathbb{R}\) from [def:es95R] but for the fact that its domain is restricted to those sequences for which additionally the sequence \(\mathopen{}\mathclose{\left(\frac{1}{n} \sum_{i=1}^n |x_i|}\right)\) converges in \(\mathbb{R}\cup \{\infty\}\) and satisfies \[\label{eq:es95integral95Eabs} \int_\mathbb{R}\@ifstar{\abs}{\abs*}{y} \, \overline{\mathsf{es}}_{\mathbb{R}} \bigl( \mathrm{d}y \mid (x_n) \bigr) = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n |x_i|\tag{83}\] and, moreover, such that if both sides of 83 are finite, then the sequence \(\mathopen{}\mathclose{\left( \frac{1}{n} \sum_{i=1}^n x_i }\right)\) converges and satisfies \[\label{eq:es95integral95E} \int_\mathbb{R}y \, \overline{\mathsf{es}}_{\mathbb{R}} \bigl( \mathrm{d}y \mid (x_n) \bigr) = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i.\tag{84}\]
We leave it understood that we include sequences for which both sides of 83 are infinite. The sequence from [ex:escaping95sequence] is excluded because the limit on the right-hand side does not exist.
The partial Markov kernel \(\overline{\mathsf{es}}_{\mathbb{R}}\) from [def:es95av] is an empirical sampling morphism in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\).
The proof can again be found in 6.
We now present our main synthetic results that follow from the existence of empirical sampling morphisms plus two auxiliary assumptions. Remarkably, these conditions imply representability of the category and the de Finetti theorem ([cor:dF]). We then prove a synthetic Glivenko–Cantelli theorem ([thm:lln]). One of its immediate consequences is a synthetic strong law of large numbers ([cor:genericLLN]).
Throughout this section, we assume the following.
Let \(\mathsf{C}\) be a quasi-Markov category such that
\(\mathsf{C}\) is positive and \(\sigma\)-continuous.
Countable Kolmogorov products exist in \(\mathsf{C}\).
All balanced idempotents [27] split in \(\mathsf{C}\).
Every object \(X\) has an empirical sampling morphism \(\mathsf{es}: X^\mathbb{N}\to X\).
As the reader may observe, balanced idempotents are the only concept whose details we defer to the literature. This is because they play a tangential role in the present work and appear only once, in the proof of [thm:representability], to ensure representability.
[assumptions] holds in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\). Indeed the existence of empirical sampling morphisms is [cor:standard95borel95es]. The \(\sigma\)-continuity was shown in [prop:sigma95parborelstoch]. For the other properties, we employ the abstract arguments in [22], which show that if a given Markov category \(\mathsf{D}\) satisfies one of these properties then so does its partialization [22]. The fact that these properties hold in \(\mathsf{BorelStoch}\) has been shown in the past: positivity in [5], existence of countable Kolmogorov products in [9], and the splitting of all idempotents in [27].
The splitting of balanced idempotents has been proven synthetically for any Markov category in [27] under the assumptions of positivity, observational representability, and the equalizer principle defined therein. If one generalized this result to quasi-Markov categories, one would obtain alternative synthetic results without splitting of idempotents among its assumptions. However, we would find this a bit less satisfactory, since one conclusion of our synthetic results in this section is the observational representability of \(\mathsf{C}\) (as a consequence of [thm:representability]).
Already our categorical formulation of the Glivenko–Cantelli theorem will involve a distribution object \(PX\). Even though its existence is not part of [assumptions], it is in fact ensured. In essence, we identify the distribution object \(PX\) via the splitting of a suitable idempotent.
As we show for our measure-theoretic construction of \(\mathsf{es}_\mathbb{R}\) in 111 , the resampling morphism \({\mathsf{es}^{(\mathbb{N})} : X^\mathbb{N}\to X^\mathbb{N}}\) may be seen as implementing a uniformly random permutation. Based on this, we might expect that it factors through the equalizer of all permutations on \(X^\mathbb{N}\) in general, which by definition is a de Finetti object ([def:dF95object]) and therefore also a distribution object ([thm:defin95obs]). Let us now make this argument precise.
Given [assumptions], \(\mathsf{C}\) is an observationally representable quasi-Markov category. In particular, for every object \(X\) we have a distribution object \(PX\) and a sampling morphism \({\mathsf{samp}: PX \to X}\).
Proof. First, for any finite permutation \(\sigma\) we have \[\label{eq:resamp95balanced} \tikzfig{resamp_balanced}\tag{85}\] where the first equality holds because \(X^\sigma\) is deterministic with inverse \(X^{\sigma^{-1}}\), the second one follows by permutation invariance of \(\mathsf{es}\) together with [lem:IID95naturality], and the last one is just the exchangeability of \(\mathsf{es}^{(\mathbb{N})}\), which is an instance of [lem:fN95exchangeable]. Therefore, the morphism on the right-hand side of 85 is exchangeable in its first \(X^\mathbb{N}\) output, and therefore empirical adequacy of \(\mathsf{es}\) implies \[\label{eq:resamp95idempotent} \tikzfig{resamp_idempotent}\tag{86}\] This is the defining equation of a balanced idempotent. By assumption, we obtain a splitting, i.e.a factorization as \(\mathsf{es}^{(\mathbb{N})} = \iota \mathchoice{\,}{\,}{}{} \pi\) satisfying \(\pi \mathchoice{\,}{\,}{}{} \iota = \mathrm{id}_{E}\) for some object \(E\).
Let us now show that \(\iota\) is IID, i.e.that it is equal to \(\ell^{(\mathbb{N})}\) for some \(\ell : E \to X\). Firstly, we introduce a diagrammatic notation for the isomorphism \(X^\mathbb{N}\cong X \otimes X^\mathbb{N}\) given in terms of the compatible family \[\label{eq:bifurcation} \tikzfig{bifurcation}\tag{87}\] of morphisms of type \(X^\mathbb{N}\to X \otimes X^{n}\) for any \(n \in \mathbb{N}\) and \(\pi_n\) defined as in [def:kolmogorov]. For any morphism \(f : A \to X\), we then have \[\label{eq:extract95copy} \tikzfig{extract_copy}\tag{88}\] which follows from \[\label{eq:extract95copy952} \tikzfig{extract_copy_2}\tag{89}\] that holds for any \(n \in \mathbb{N}\). Then we have \[\label{eq:iota95IID} \tikzfig{iota_IID}\tag{90}\] where the first and third equality follow from the splitting of \(\mathsf{es}^{(\mathbb{N})}\), second one is a version of 88 for \(f = \mathsf{es}\), and the last one is an application of the positivity assumption to the deterministic morphism \(\pi \mathchoice{\,}{\,}{}{} \iota = \mathrm{id}_{E}\). We can now apply the same argument repeatedly to obtain \[\tikzfig{det_displaycondind5}\] for any \(n \in \mathbb{N}\). By the universal property of the Kolmogorov product, we thus get \(\iota = \ell^{(\mathbb{N})}\) for \({\ell \mathrel{\vcenter{:}}= \mathsf{es} \mathchoice{\,}{\,}{}{} \iota}\).
Let us now show that \(E\) is a de Finetti object with universal arrow \(\iota : E \to X^\mathbb{N}\). By \(\iota = \ell^{(\mathbb{N})}\), we already know that \(\iota\) is invariant under finite permutations on \(X^\mathbb{N}\). Consider now a generic morphism \(f : A \to X^\mathbb{N}\otimes Y\) that is invariant under all finite permutations of \(X^\mathbb{N}\), i.e.one that is exchangeable. By the empirical adequacy of \(\mathsf{es}\) and the above splitting of \(\mathsf{es}^{(\mathbb{N})}\), we have \[\label{eq:es95defin} \tikzfig{es_defin}\tag{91}\] i.e.\(f\) factors through \(\iota \otimes \mathrm{id}_Y\) as required.
Observational representability now follows from [thm:defin95obs]. In particular, we can consider \(E\) as the distribution object \(PX\) of \(X\) with sampling morphism \(\ell = \mathsf{es} \mathchoice{\,}{\,}{}{} \iota : E \to X\). ◻
In addition to being a distribution object, the above proof in fact show that \(E\) is a de Finetti object. This fact may be interpreted as a synthetic de Finetti theorem.
Given [assumptions], the distribution object of any \(X \in \mathsf{C}\) is also a de Finetti object.
However, this differs significantly from the synthetic de Finetti theorems for Markov categories from earlier works, namely [3] and [13]. These two establish conditional independence of exchangeable morphisms, while here we have implicitly assumed this conditional independence in the empirical adequacy axiom. The non-trivial statement established by [cor:dF] is the fact that exchangeable morphisms must factor through the distribution object \(PX\), and the universal property by virtue of the uniqueness of this decomposition.
With the existence of distribution objects ensured, we can now aim for our main theorem, the synthetic Glivenko–Cantelli theorem. An important stepping stone towards it is the following result, which shows that the resampling morphism \({\mathsf{es}^{(\mathbb{N})} : X^\mathbb{N}\to X^\mathbb{N}}\) is a split idempotent given by infinitely many samples from the empirical measure.
Given [assumptions], the resampling morphism \(\mathsf{es}^{(\mathbb{N})}\) splits as17 \[\label{eq:es95splitting} \mathsf{es}^{(\mathbb{N})} = \mathsf{samp}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathsf{es}^\sharp, \qquad \mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})} = \mathrm{id}_{PX}.\tag{92}\]
Proof. By the representability proven in [thm:representability], we have \(\mathsf{es}= \mathsf{samp} \mathchoice{\,}{\,}{}{} \mathsf{es}^{\sharp}\). Since the morphism \({\mathsf{es}^{\sharp} : X^\mathbb{N}\to PX}\) is copyable by definition, we get \[\mathsf{samp}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathsf{es}^{\sharp} = \mathsf{es}^{(\mathbb{N})},\] which is the first equation in 92 .
To prove the second equation in 92 , consider \[\label{eq:lln95proof951} \mathsf{samp}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathsf{es}^{\sharp} \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})} = \mathsf{es}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})} = \mathsf{samp}^{(\mathbb{N})},\tag{93}\] where the second equality follows by empirical adequacy (67 ), since \(\mathsf{samp}^{(\mathbb{N})}\) is IID and hence exchangeable. Since \(\mathsf{C}\) is observationally representable ([thm:representability]), \(\mathsf{samp}^{(\mathbb{N})}\) is monic, and therefore we get \(\mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})} = \mathrm{id}\) from 93 . ◻
Plugging in the splitting of the resampling morphism into the empirical adequacy axiom of the empirical sampling morphism, i.e.into 67 , we obtain the following corollary of [lem:pre95lln]: Every morphism \(f : A \to X^\mathbb{N}\otimes Y\) that is exchangeable in \(X^\mathbb{N}\) satisfies \[\label{eq:de95finetti95rep} \tikzfig{de_finetti_rep}\tag{94}\] In particular, for \(Y = I\), 94 says that the de Finetti measure of \(f\) is given by \(\mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} f\).
Yet another corollary is that the resampling morphism is not just a balanced idempotent as shown in the proof of [thm:representability], but in fact a strong idempotent, which means that it satisfies \[\tikzfig{resamp_strong_idempotent}\] This follows from the splitting proven above and [27],18 since the projection of the splitting is \(\mathsf{es}^\sharp\) by [lem:pre95lln] and thus copyable.
Our Glivenko–Cantelli theorem for quasi-Markov categories is also not hard to derive once we have [lem:pre95lln]. Its name is justified by the measure-theoretic Glivenko–Cantelli theorem, which we recover as [thm:glivenko].
Consider an arbitrary exchangeable morphism \({f : A \to X^\mathbb{N}}\) and an arbitrary morphism \({p : A \to X}\) in a quasi-Markov category. Given [assumptions], they satisfy \[\label{eq:lln951} \tikzfig{lln_3} \qquad\quad \text{and} \qquad\quad \tikzfig{lln_1}\tag{95}\] respectively.
It is worth noting that the first equation establishes that \(\mathsf{es}^\sharp\) is a sufficient statistic for \(f\) in the sense of [5].
Proof. Let us start with the first equation in 95 , since the second one can be then derived as a consequence. To this end, we calculate \[\label{eq:es95splitting951} \tikzfig{es_splitting_1}\tag{96}\] where the first equality is by 94 , and the second by the positivity axiom applied to the morphism \(\mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})}\), which is equal to \(\mathrm{id}_{PX}\) by [lem:pre95lln].
Let us now move to the second equation in 95 , applicable to the specific exchangeable morphism given by \(p^{(\mathbb{N})}\). Since we can write \(p = \mathsf{samp} \mathchoice{\,}{\,}{}{} p^\sharp\) by representability and \(p^\sharp\) is copyable, we have the first equality in \[\label{eq:lln95proof952} \mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} p^{(\mathbb{N})} = \mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} \mathsf{samp}^{(\mathbb{N})} \mathchoice{\,}{\,}{}{} p^\sharp = p^\sharp,\tag{97}\] while the second one follows from [lem:pre95lln]. In particular, \(\mathsf{es}^\sharp \mathchoice{\,}{\,}{}{} p^{(\mathbb{N})}\) is copyable and we can apply the positivity axiom to obtain the desired equality. ◻
Instead of assuming the existence of empirical sampling morphisms for each object in \(\mathsf{C}\), we could also just consider a fixed object \(X\) and an empirical sampling morphism for it. In this case, the resulting synthetic Glivenko–Cantelli theorem still holds just as above with the same proof, but of course only for morphisms \(f\) and \(p\) for this fixed object \(X\).
To recover the standard measure-theoretic version of the theorem [35], we employ the empirical sampling morphism \(\mathsf{es}_\mathbb{R}\) constructed in [def:es95R].
Let \((x_i)_{i \in \mathbb{N}}\) be a sequence of real-valued random variables with an IID law \(p^\mathbb{N}\). Then we have \[\lim_{n \to \infty} \frac{| \{ i \le n \mid x_i \le t \}|}{n} = \undefined{x_1 \le t}\] \(p^\mathbb{N}\)-almost surely and uniformly in \(t \in \mathbb{R}\).
Proof. By [rem:borelstoch95assumptions], the category of partial Markov kernels between standard Borel spaces, \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), satisfies [assumptions]. Let us interpret the probability measure \(p\) as a morphism \(p : I \to \mathbb{R}\) in this category and consider the empirical sampling morphism \(\mathsf{es}_\mathbb{R}: P \mathbb{R}\to \mathbb{R}\) from [def:es95R]. With this, \(\mathsf{es}_\mathbb{R}^\sharp : \mathbb{R}^\mathbb{N}\to P\mathbb{R}\) is the measurable map that sends a sequence of real numbers to its empirical measure in the sense of [def:es95R], whenever it is defined.
By 95 , we thus have \[\label{eq:glivenko95proof951} \tikzfig{glivenko_proof_1}\tag{98}\] where \(p^\mathbb{N}\) is the IID measure on \(X^\mathbb{N}\). As shown in [5], this is the string-diagrammatic way to express measure-theoretic almost sure equality. In this case 98 says that, \(p^\mathbb{N}\)-almost surely, the empirical measure \(\mathsf{es}^\sharp\) does not depend on the sequence and is simply equal to the measure \(p^\sharp\): \[\label{eq:glivenko95proof952} \mathsf{es}^\sharp \bigl( (x_i) \bigr) \;=_{p^\mathbb{N}\text{-a.s.}}\; p^\sharp.\tag{99}\] Using the definition of \(\mathsf{es}_\mathbb{R}\) shows that 99 is exactly the desired statement. ◻
A well-known generalization of the Glivenko–Cantelli theorem is the Vapnik–Chervonenkis theorem [39], which replaces the collections of intervals \((-\infty, t]\) in \(\mathbb{R}\) by an arbitrary class of measurable sets satisfying a suitable “finite-dimensionality” condition and concludes almost sure uniform convergence on this class. It seems plausible to us that this could be incorporated into our framework by constructing an empirical sampling morphism for each such class of sets, but we have not yet worked out the details.
We turn to a few more consequences that can be formulated and proven synthetically. Comparing the empirical adequacy of empirical sampling with the statement of one version of the synthetic de Finetti theorem [13] suggests that \(\mathsf{es}\) could play the role of the tail conditional. Intuitively, both morphisms can be used to generate the individual outputs \(X\) of an exchangeable morphism given the full sequence in \(X^\mathbb{N}\). The following result makes this precise.
Given [assumptions], let \(f : A \to X^{\mathbb{N}}\otimes Y\) be exchangeable in the first factor. Then the morphism \[\mathrm{del}_A \otimes \mathsf{es}\otimes \mathrm{del}_Y \; : \; A \otimes X^\mathbb{N}\otimes Y \longrightarrow X\] is a conditional19 of \(f\) with respect to \(X^{\mathbb{N}\setminus\{1\}} \otimes Y\).
Proof. By the exchangeability of \(f\), we can restrict to the first \(X\) output without loss of generality. We then get20 \[\label{eq:es95tail95conditional} \tikzfig{es_tail_conditional}\tag{100}\] where we use the empirical adequacy of \(\mathsf{es}\) in the first and last equality, while the second one is a consequence of 95 with \(p\) given by \(\mathsf{es}\). The rightmost diagram includes a ‘splitting’ of the double wire, which stands for the isomorphism from 87 . 88 is also used in the last equality in 100 . We can then calculate \[\tikzfig{es_tail_conditional_2}\] where the first equation is by the spreadability lemma [3], which is a consequence of exchangeability21 and counitality of copying. This equation witnesses that the dashed box morphism \(\mathrm{del}_A \otimes \mathsf{es}\otimes \mathrm{del}_Y\) is a conditional \(f_{|X^{\mathbb{N}\setminus\{1\}} \otimes Y}\). ◻
The strong law of large numbers for bounded variables is an immediate consequence of the measure-theoretic Glivenko–Cantelli theorem. In the categorical formulation, our synthetic Glivenko–Cantelli theorem also specializes immediately to a synthetic strong law of large numbers.
Given [assumptions], we have22 \[\label{eq:genericLLN2} \tikzfig{genericLLN2}\tag{101}\] for arbitrary morphisms \({p : I \to X}\) and \({m : PX \to X}\).
Proof. This follows directly from 95 , with \(A = I\) as in 98 , upon post-composing with \(m \otimes \mathrm{id}_{X^\mathbb{N}}\). ◻
To recover a measure-theoretic law of large numbers, the idea is to take \(X = Y = \mathbb{R}\) and \(m : P \mathbb{R}\to \mathbb{R}\) to be the expectated value map which assigns to every probability measure its mean, \[E : \mu \longmapsto \int_\mathbb{R}x \, \mu(\mathrm{d} x).\] Of course, once again this is only a partial map \(P \mathbb{R}\to \mathbb{R}\), since the integral generally does not converge. For this reason, we define the domain of \(E\) to be the set of all probability measures with finite first moment: \[\mathrm{dom}\mathopen{}\mathclose{\left(E}\right) \mathrel{\vcenter{:}}= \mathopen{}\mathclose{\left\{ \mu \in P \mathbb{R}\;\bigg|\; \int_\mathbb{R}|x| \, \mu(\mathrm{d} x) < \infty }\right\}.\] The subtle ways in which \(E\) can be thought of as a partial \(P\)-algebra are discussed in [22].
The following observation is key for interpreting the left-hand side of 101 .
In \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) and with the empirical sampling morphism \(\overline{\mathsf{es}}_{\mathbb{R}} : \mathbb{R}^\mathbb{N}\to P \mathbb{R}\) from [def:es95av], every sequence \((x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\overline{\mathsf{es}}_\mathbb{R}}\right)\) satisfies:
\(E \mathchoice{\,}{\,}{}{} \overline{\mathsf{es}}_{\mathbb{R}}^\sharp\) is defined on \((x_i)\) if and only if the empirical measure \(\overline{\mathsf{es}}_{\mathbb{R}}^\sharp((x_i))\) has finite first moment.
In this case, we have \[\label{eq:empirical95averaging95recover} \mathopen{}\mathclose{\left( E \mathchoice{\,}{\,}{}{} \overline{\mathsf{es}}_{\mathbb{R}}^\sharp }\right) \bigl( (x_i) \bigr) = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i.\tag{102}\]
Proof. Property [it:empirical95averaging95domain] holds by the definition of \(E\) and Property [it:empirical95averaging95recover] by the definition of \(\overline{\mathsf{es}}_{\mathbb{R}}\), and in particular by 84 . ◻
Based on this, we can now instantiate [cor:genericLLN] to obtain Kolmogorov’s strong law of large numbers.
Let \((x_i)\) be a sequence of real-valued IID random variables with finite first moment. Then \[\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i = \E{x_1}\] almost surely.
Proof. Take \(p\) to be the law of the \(x_i\) in [cor:genericLLN]. Then the left-hand side of 101 becomes the empirical average \[\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i\] by 102 . The right-hand side of 101 is \(E \mathchoice{\,}{\,}{}{} p^\sharp\), which is the expectation value of the law \(p\), also written as \(\E{x_1}\). ◻
Note that it is important that we use the modified empirical sampling morphism \(\overline{\mathsf{es}}_{\mathbb{R}}\) instead of the original \(\mathsf{es}_{\mathbb{R}}\) from [def:es95R]. Although it is possible to instantiate [cor:genericLLN] with \(\mathsf{es}_{\mathbb{R}}\) and \(m = E\), this does not yield the strong law of large numbers in its usual form, since the left-hand side need not be the empirical average, as we saw in [ex:escaping95sequence].
Here, we develop some preliminary results towards proving empirical adequacy for \(\mathsf{es}_\mathbb{R}\) and \(\overline{\mathsf{es}}_{\mathbb{R}}\) introduced in [def:es_R,def:es_av] respectively. Specifically, the bounds that we derive in this section are used in 6 to show that the domain of the respective empirical sampling morphism has probability \(1\) with respect to any exchangeable measure. In other words, they ensure that the empirical measure of an exchangeable sequence of random variables exists almost surely.
The ingredients we need here are: Markov’s inequality [35] the Borel–Cantelli lemma [35] and elementary properties of cumulants [35]. It is important to note that our proof of the axioms of empirical sampling morphisms do not use results such as the Glivenko–Cantelli theorem. Otherwise, we could not claim to prove the standard version thereof ([thm:glivenko]) from basic principles, since the proof would have been circular.
As is customary in measure-theoretic probability, we denote random variables by uppercase letters in this section. This is in contrast to the rest of this document, where uppercase letters generally denote objects in a category.
Let \((Z_i)_{i \in \mathbb{N}}\) be an exchangeable sequence of \([0,1]\)-valued random variables and consider \[S_n \mathrel{\vcenter{:}}= \sum_{i=1}^n Z_i.\] Then:
For \(m, n \in \mathbb{N}\) and \(\varepsilon> 0\), we have \[\label{eq:exchangeable95concentration} \undefined*{ \, \vphantom{\rule{0mm}{6mm}} \@ifstar{\abs}{\abs*}{\frac{S_n}{n} - \frac{S_m}{m}} > \varepsilon \, } \;\le\; \frac{C}{\varepsilon^6 \min(m, n)^3}\tag{103}\] for some universal constant \(C\).
The sequence \(\mathopen{}\mathclose{\left(\frac{S_n}{n} }\right)_{n \in \mathbb{N}}\) converges almost surely.
While our proof bears similarity to a standard proof of the law of large numbers for bounded random variables [35], our bound is tighter and more general, as it also applies in the exchangeable case. Due to this tighter bound, the proof is harder and employs a less straightforward argument based on cumulants. On the other hand, we make no statement about what the limit of the sequence \(\mathopen{}\mathclose{\left(\frac{S_n}{n} }\right)_{n \in \mathbb{N}}\) is.
Proof. For [it:exchangeable95concentration], we assume \(m \ge n\) without loss of generality. Then Markov’s inequality gives \[\begin{align} \undefined*{ \, \vphantom{\rule{0mm}{6mm}} \@ifstar{\abs}{\abs*}{\frac{S_n}{n} - \frac{S_m}{m} } > \varepsilon \, } & = \undefined*{ \mathopen{}\mathclose{\left( m S_n - n S_m }\right)^6 > \varepsilon^6 m^6 n^6 } \nonumber\\ & \le \frac{1}{\varepsilon^6 m^6 n^6} \cdot \E*{(m S_n - n S_m)^6} \nonumber\\ & = \frac{1}{\varepsilon^6 m^6 n^6} \cdot \E*{\mathopen{}\mathclose{\left( (m - n) \sum_{i=1}^n Z_i - n \sum_{i=n+1}^m Z_i }\right)^6}. \label{eq:6th95moment95expression} \end{align}\tag{104}\] Thus we need to control the sixth moment of the “discrepancy” \[\label{def95D} D \mathrel{\vcenter{:}}= (m - n) \sum_{i=1}^n Z_i - n \sum_{i=n+1}^m Z_i.\tag{105}\] In the following, we will finish the proof by showing that this can be bounded by \(O(n^3 m^6)\).
When expanding out the sixth power and taking expectations, each term ends up being an expectation of a product of six of the \(Z_i\)’s. When all six factors are distinct, then we can use exchangeability to rewrite this expectation as \(\E{Z_1 \cdots Z_6}\). Similarly by exchangeability, all other terms are multiples of one of \[\E*{Z_1^2 Z_2 \cdots Z_6}, \quad \ldots, \quad \E*{Z_1^3 Z_2^2 Z_3}, \quad \ldots, \quad \E*{Z_1^6},\] which formally means that the terms are indexed by the partitions of \(6\). The coefficient of each term is a polynomial in \(n\) and \(m\).
Although these coefficient polynomials can be computed explicitly by performing this expansion, actually doing so to the relevant order is cumbersome, and we take a different route through the cumulants. Since the polynomials do not depend on the \(Z_i\), we can assume without loss of generality that the \(Z_i\) are independent. In this case, the additivity of cumulants under sums of independent variables together with the fact that the \(j\)-th cumulant is homogeneous of degree \(j\) lets us write the \(j\)-th cumulant of 105 as \[\label{eq:cumulants95bound} \kappa_j(D) = (m - n)^j n \, \kappa_j(Z_1) + (-n)^j m \, \kappa_j(Z_1) = O(n m^j).\tag{106}\] The second step uses \(m \ge n\), as well as the assumption that the \(Z_i\)’s are \([0,1]\)-valued so that the cumulants can be bounded by a universal constant. Using now the standard conversion formula23 expressing the sixth moment in terms of cumulants and specializing it to the case \(\kappa_1(D) = \E{D} = 0\), we get \[\E*{D^6} = \kappa_6(D) + 15 \kappa_4(D) \kappa_2(D) + 10 \kappa_3(D)^2 + 15 \kappa_2(D)^3.\] By 106 , this can be bounded by \[\E*{D^6} = O(n m^6) + O(n^2 m^6) + O(n^2 m^6) + O(n^3 m^6) = O(n^3 m^6),\] as was to be shown.
Concerning claim [it:exchangeable95convergence], the Borel–Cantelli lemma combined with Inequality 103 shows that the sequence \(\mathopen{}\mathclose{\left(\frac{S_n}{n} }\right)_{n \in \mathbb{N}}\) is almost surely Cauchy, and hence converges almost surely. ◻
Of course, using similar arguments one can establish analogous bounds for any exponent of \(\min(m, n)\) in the denominator of 103 , where larger exponents require more work. An exponent of \(2\) would be sufficient to conclude the strong law of large numbers for bounded random variables. The reason we use an exponent of \(3\) is that this is sufficient to make the following simple proof of a version of the Glivenko–Cantelli theorem work, while an exponent of \(2\) would not be.
Let \((W_i)_{i \in \mathbb{N}}\) be an exchangeable sequence of \(\mathbb{R}\)-valued random variables. Then the empirical cumulative distribution functions \(F_n : \mathbb{R}\to [0,1]\) defined by \[F_n(t) \mathrel{\vcenter{:}}= \frac{ \@ifstar{\abs}{\abs*}{ \@ifstar{\Set}{\Set*}{ i \le n W_i \le t } }}{n}\] satisfy:
For \(m, n \in \mathbb{N}\) and \(\varepsilon> 0\), we have \[\label{eq:exchangeable95ecdf95concentration} \undefined*{ \sup_{t \in \mathbb{R}} \, \@ifstar{\abs}{\abs*}{F_n(t) - F_m(t)} > \varepsilon} \le \frac{C}{\varepsilon^6 \min(m, n)^2}\tag{107}\] for some universal constant \(C\).
The sequence \((F_n)_{n \in \mathbb{N}}\) converges almost surely uniformly to the cumulative distribution function of a probability measure on \(\mathbb{R}\).
Our proof is similar in spirit to a standard proof of the Glivenko–Cantelli theorem from the strong law of large numbers [41].
Proof. For [it:exchangeable95ecdf95concentration], suppose again \(m \ge n\) without loss of generality. Then the function \(F_n\) jumps up at the points \(t = W_1, \ldots, W_n\) and is otherwise constant. Since \(F_m\) is also monotonically nondecreasing, this implies that the supremum is attained at one of the points \(W_i\) (if \(F_n\) is above \(F_m\) at the supremum) or just before (if \(F_n\) is below \(F_m\) at the supremum). Hence there are \(2n\) possibilities for where the supremum can be attained, and we can write the event on the left-hand side of 107 as \[\begin{align} \exists \, j \le n \: : \: \bigg( & \frac{|\@ifstar{\Set}{\Set*}{ i \le n W_i \le W_j }|}{n} - \frac{|\@ifstar{\Set}{\Set*}{ i \le m W_i \le W_j }|}{m} > \varepsilon \\ & \lor \quad \frac{|\@ifstar{\Set}{\Set*}{ i \le n W_i < W_j }|}{n} - \frac{|\@ifstar{\Set}{\Set*}{ i \le m W_i < W_j }|}{m} < -\varepsilon \bigg) \end{align}\] By [lem:exchangeable95convergence], we have the bounds24 \[\begin{align} \undefined*{ \frac{|\@ifstar{\Set}{\Set*}{ i \le n W_i \le W_j }|}{n} - \frac{|\@ifstar{\Set}{\Set*}{ i \le m W_i \le W_j }|}{m} > \varepsilon } \le \frac{C}{\varepsilon^6 n^3}, \\[1pt] \undefined*{ \frac{|\@ifstar{\Set}{\Set*}{ i \le n W_i < W_j }|}{n} - \frac{|\@ifstar{\Set}{\Set*}{ i \le m W_i < W_j }|}{m} < -\varepsilon } \le \frac{C}{\varepsilon^6 n^3}, \end{align}\] for every \(j\) and for some universal constant \(C\). The claimed 107 now follows by a union bound over the \(2n\) possibilities.
Finally, let us prove [it:exchangeable95ecdf95convergence]. Since we have a square in the denominator of 107 and \(\sum_{n=1}^\infty \frac{1}{n^2}\) converges, we can again apply the Borel–Cantelli lemma together with [it:exchangeable95ecdf95concentration] to conclude that the sequence \((F_n)\) is almost surely uniformly Cauchy. Furthermore, part [it:exchangeable95convergence] of [lem:exchangeable95convergence] implies that it almost surely converges pointwise. Combining these two things with the fact that the uniform limit of a sequence of cumulative distribution functions is a cumulative distribution function, we obtain the desired result. ◻
To deal with averages of unbounded random variables, we need some control over tails as provided by the following lemma. Our proof is essentially Garsia’s simple proof of the maximal ergodic theorem [42], although our statement is only the special case for exchangeable variables.
Suppose that \((Y_n)_{n \in \mathbb{N}}\) is an exchangeable sequence of nonnegative random variables with finite expectation. Then for every \(r > 0\), we have \[\label{eq:maximal95ergodic} \undefined*{ \sup_n \frac{1}{n} \sum_{i=1}^n Y_i > r } \le r^{-1} \E{Y_1}.\tag{108}\]
Note that the right-hand side is precisely the bound that one would get from Markov’s inequality for fixed \(n\) (if the supremum was not there).
Proof. Consider the sequence of measurable subsets of the underlying probability space \(\Omega\) given by \[E_n \mathrel{\vcenter{:}}= \@ifstar{\Set}{\Set*}{ \omega \in \Omega \mathopen{}\mathclose{\left( \max_{k=1,\dots,n} \frac{1}{k} \sum_{i=1}^k Y_i(\omega) }\right) > r }\] so that 108 can be expressed as \(\undefined{E_\infty} \le r^{-1} \E{Y_1}\), where \(E_\infty\) is \(\bigcup_n E_n\).
Consider now the shifted version \(Z_n \mathrel{\vcenter{:}}= Y_n - r\) of the sequence so that we can write \[E_n = \mathopen{}\mathclose{\left\{ \max_{k=0,\dots,n} \sum_{i=1}^k Z_i > 0 }\right\}\] using the more standard implicit notation for random variables. We use the convention \(\sum_{i=1}^0 Z_i = 0\), so that we can add the extra case of \(k = 0\), which is redundant as \(0 > 0\) never holds. By \[\label{eq:maximal95ergodic95proof952} \max_{k=0,\dots,n} \sum_{i=1}^k Z_i \;\le\; \max_{k=0,\dots,n+1} \sum_{i=1}^k Z_i ,\tag{109}\] we have \(E_n\subseteq E_{n+1}\) and also the pointwise inequality \[\label{eq:maximal95ergodic95proof} \max_{k=0,\dots,n} \sum_{i=1}^k Z_i \le 1_{E_n} Z_1 + \max_{k=0,\dots,n} \sum_{i=1}^{k} Z_{i+1}\tag{110}\] for each \(\omega \in \Omega\). Inequality 110 can be shown by distinguishing cases:
If \(E_n\) holds, then the maximum on the left is attained for some \(k \geq 1\). But then the very same terms appear on the right-hand side which can be rewritten as the right-hand side of Inequality 109 in this case.
If \(E_n\) does not hold, then the maximum on the left is attained at \(k = 0\), and the inequality simply states its right-hand side is nonnegative, which is trivial.
If we now take expectations on both sides of Inequality 110 , then the two maxima coincide by exchangeability. Therefore we obtain \[\E{1_{E_n} Z_1} \ge 0.\] Since the sequence of events \(E_n\) is increasing in \(n\), we obtain the same inequality for \(E_\infty\). Plugging in the definition of \(Z_1\) into \(\E{1_{E_\infty} Z_1} \ge 0\) then gives the second step in \[\E*{Y_1} \ge \E*{1_{E_\infty} Y_1} \ge \E*{1_{E_\infty}\, r} = r \, \undefined*{ \sup_n \frac{1}{n} \sum_{i=1}^n Y_i > r },\] which amounts to the desired result. ◻
This section is devoted to proving the theorems in 3.2 plus [prop:tightened95es] in 3.3 based on the results of 5.
Proof of [lem:finite95es]. First of all, to show that \(\mathsf{es}_F\) is indeed a partial Markov kernel, we need to prove that
the domain \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right)\) of \(\mathsf{es}_F\) (i.e.the set where the limit 69 exists) is a measurable subset of \(F^\mathbb{N}\),
\(\mathsf{es}_F(T | {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}) : \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right) \to [0,1]\) is a measurable map for each \(T \subseteq F\), and that
\(\mathsf{es}_F \bigl( {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}| (x_i) \bigr) : 2^F \to [0,1]\) is a probability measure for every \((x_i)\) in the domain.
To prove Property [it:esF95domain], it suffices to show that the set of sequences for which the limit exists for fixed \(T\) is measurable, since \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right)\) is a finite intersection of these. In order to show this, we can replace the existence of the limit by the equivalent condition that the sequence of relative frequencies is Cauchy. Namely, this set of sequences is characterized by requiring that for all \(\ell \in \mathbb{N}\), there exists \(N \in \mathbb{N}\) such that for all integers \(m,n \ge N\), we have \[\@ifstar{\abs}{\abs*}{ \frac{ \@ifstar{\abs}{\abs*}{\@ifstar{\Set}{\Set*}{ i \le n x_i \in T} } }{n} - \frac{ \@ifstar{\abs}{\abs*}{\@ifstar{\Set}{\Set*}{ i \le m x_i \in T} } }{m} } < \ell^{-1}.\] This shows that the set of sequences with well-defined empirical measure appears at level \(\mathbf{\Pi}^0_4\) of the Borel hierarchy [43], and is therefore measurable. The measurability of \(\mathsf{es}_F(T | {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em})\) on this domain, which is Property [it:esF95measurable], follows by a similar argument. Finally, the additivity of \(\mathsf{es}_F( {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}| (x_i))\) follows from the finite additivity of limits, and normalization holds because the relative frequency of \(T = F\) is \(1\) for every \(n\). In conclusion, \(\mathsf{es}_F\) is a partial Markov kernel \(F^\mathbb{N}\to F\), i.e.a morphism of \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\), as required.
Let us show now that the axioms of [def:es] are satisfied. Permutation invariance holds because both the existence and the values of the limits of relative frequencies are invariant under any finite permutation of the sequence \((x_i)\).
Proving empirical adequacy takes more work. We do so by first showing that the kernel \[\mathsf{es}_F^{(\mathbb{N})} : F^\mathbb{N}\to F^\mathbb{N}\] can be computed in terms of a limit of averaging over the finite permutation groups \(S_n\). Namely, we claim that for any subsets \(T_1, \ldots, T_m \subseteq F\) and any \(m \in \mathbb{N}\), we have \[\label{eq:es95random95permutation} \mathsf{es}_F^{(\mathbb{N})} \bigl( T_1 \times \cdots \times T_m \times F \times \dots \,|\, (x_n) \bigr) = \lim_{n \to \infty} \frac{1}{n!} \sum_{\sigma \in S_{n}} T_1(x_{\sigma(1)}) \, \cdots \, T_m(x_{\sigma(m)}),\tag{111}\] where \(T_i({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em})\) denotes the indicator function of \(T_i\), and we leave it understood that the limit is over \(n \ge m\) only. This formula suggests that we may think of \(\mathsf{es}_F^{(\mathbb{N})}\) as applying a uniformly random permutation to the given sequence \((x_i)\), whenever this makes sense (i.e.when the limits exist). As part of the claim that 111 coincides with 69 , we claim that the existence of the relevant limits holds on precisely the same set of sequences \((x_i)\).
To prove 111 , suppose first that \((x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right)\). We then need to show that the limits on the right-hand side exist for all \(m\) and that the equation holds. By definition of \(\mathsf{es}_F^{(\mathbb{N})}\), we can compute \[\begin{align} \mathsf{es}_F^{(\mathbb{N})} \bigl(T_1 \times \cdots \times T_m \times F \times \dots \,|\, (x_j) \bigr) & = \mathsf{es}_F \bigl(T_1 | (x_j) \bigr) \, \cdots \, \mathsf{es}_F \bigl(T_m | (x_j) \bigr) \\[3pt] &= \lim_{n \to \infty} \frac{\@ifstar{\abs}{\abs*}{\@ifstar{\Set}{\Set*}{ i_1 \le n \!\! x_{i_1} \in T_1 } } }{n} \, \cdots \frac{\@ifstar{\abs}{\abs*}{\@ifstar{\Set}{\Set*}{ i_m \le n \!\! x_{i_m} \in T_m } } }{n} \\ &= \lim_{n \to \infty} \frac{1}{n^m} \sum_{i_1, \dots, i_m = 1}^n T_1(x_{i_1}) \,\cdots\, T_m(x_{i_m}). \end{align}\] Thinking of \(k \mapsto i_k\) as a map \(\{1, \ldots, m\} \to \{1, \ldots, n\}\) shows that this amounts to averaging over all such maps, of which there are \(n^m\) many. Since the fraction of injections among these maps goes to \(1\) as \(n \to \infty\), we obtain the same limit by averaging over all injections. But every such injection can be extended to a permutation of \(\{1,\ldots,n\}\), there are \((n - m)!\) many ways to do so independently of what the injection is, and all of these are distinct as the map varies. Therefore, we can instead average over permutations, and this is exactly the claimed 111 .
Conversely, suppose that \((x_j)\) is such that the limits in 111 exist for all \(m\) and all \(T_1, \ldots, T_m\). Then this holds in particular for \(m = 1\), in which case the right-hand side coincides with that of 69 and the claim follows. In conclusion, \(\mathsf{es}_F^{(\mathbb{N})}\) and the formula from 111 have the same domain and, on this domain, they coincide.
With this formula for \(\mathsf{es}_F^{(\mathbb{N})}\) at hand, we can prove empirical adequacy for \(\mathsf{es}_F\). To this end, consider an arbitrary standard Borel space \(Y\) as in 67 . Then for a Markov kernel \(f : A \to F^{\mathbb{N}} \otimes Y\) that is exchangeable in its first factor, let us first show that \[\label{eq:exchangeable95es95dom} f \bigl(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right) \times Y \, | \, a \bigr) = 1 \qquad \forall a \in A.\tag{112}\] This amounts to showing that if \((x_n)_{n \in \mathbb{N}}\) and \(y\) are random variables taking values in the respective spaces, then the limit \[\lim_{n \to \infty} \frac{| \{ i \le n \mid x_i \in T \}|}{n} = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n T(x_i)\] exists almost surely with respect to the joint distribution \(f( {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}| a)\) of \(F^\mathbb{N}\otimes Y\). This follows from [lem:exchangeable95convergence].
We can now calculate that, for arbitrary subsets \(T_1, \ldots, T_m \subseteq F\) and any measurable \(U \subseteq Y\), \[\label{es95proof95finite} \begin{align} \mathopen{}\mathclose{\left( \bigl( \mathsf{es}_F^{(\mathbb{N})} \otimes \mathrm{id}_Y \bigr) \mathchoice{\,}{\,}{}{} f }\right)& \bigl( T_1 \times \cdots \times T_m \times F \times \dots \times U \,|\, a \bigr) \\ & = \int_{x \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right)} \mathsf{es}_F^{(\mathbb{N})} \bigl( T_1 \times \cdots \times T_m \times F \times \dots | x \bigr) \, f(\mathrm{d} x \times U \,|\, a) \\ & = \int_{x \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right)} \lim_{n \to \infty} \frac{1}{n!} \sum_{\sigma \in S_{n}} T_1(x_{\sigma(1)}) \cdots T_m(x_{\sigma(m)}) \, f(\mathrm{d} x \times U \,|\, a) \\ & = \lim_{n \to \infty} \frac{1}{n!} \sum_{\sigma \in S_{n}} \int_{x \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_F}\right)} T_1(x_{\sigma(1)}) \cdots T_m(x_{\sigma(m)}) \, f(\mathrm{d} x \times U \,|\, a) \\[1pt] & = f \bigl( T_1 \times \cdots \times T_m \times F \times \dots \times U \,|\, a \bigr), \end{align}\tag{113}\] where the first equation is plugging in definitions, the second one uses 111 , the commutation of the limit and the integral in the third is an instance of the dominated convergence theorem (the measure is finite and the integrand is bounded by \(1\)), and the last step holds by the exchangeability of \(f\) and by 112 . This concludes the proof of empirical adequacy for \(\mathsf{es}_F\). ◻
Writing \(\mathsf{es}_F\) as in averaging over permutations as in 111 is strongly reminiscent of group averaging in ergodic theory [44]. We expect this to be connected to the fact that the permutation group \(S_\infty = \bigcup_n S_n\) is amenable, and that similar constructions can be made for other amenable groups.
Proof of [lem:countable95es]. This works similarly as the construction from the finite case with some additional subtleties. Recall from 71 that we require the limits of 74 to exist uniformly for the sets \(T = \{1, \ldots, t\}\), but otherwise the proof of measurability of \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{N}}\right)\) and of \(\mathsf{es}_\mathbb{N}\) itself is the same as in the finite case. The fact that \(\mathsf{es}_\mathbb{N}({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}| (x_i))\) is a probability measure for every \((x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{N}}\right)\) holds because of 73 .
The rest of the proof is the same as in the finite case, but with all limits being suitably uniform; in particular, for fixed \(m\) the limit in 111 must exist uniformly for sets of the form \(T_i = \{1, \ldots, t_i\}\). The analogue of 112 holds because the relevant limits are all uniform in \(S\), as is immediate from the bound 103 in [lem:exchangeable95convergence]. ◻
Proof of [lem:real95es]. Let us first show that [def:es95R] indeed gives a unique Markov kernel as claimed. To this end, let \(F : \mathbb{Q}\to \mathbb{R}\) be the function given by \[F(t) \coloneq \lim_{n \to \infty} \frac{ \@ifstar{\abs}{\abs*}{\{ i \le n \mid x_i \le t\}}}{n}\] for any sequence in the domain of \(\mathsf{es}_\mathbb{R}\). Since the function \[t \mapsto \frac{|\{ i \le n \mid x_i \le t\}|}{n}\] is right continuous for every fixed \(n\), and right continuous functions are stable under uniform limits, it follows that \(F\) is right continuous as well. The limits in 76 likewise hold thanks to the uniform convergence, while monotonicity is already a consequence of the pointwise convergence. Therefore \(F\) is a CDF. The probability measure that corresponds to it satisfies 78 by finite additivity together with the commutation of limits and finite sums. Therefore, a measure \(\mathsf{es}_\mathbb{R}({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}|(x_i))\) with the properties specified in [def:es95R] indeed exists.
To see that \(\mathsf{es}_\mathbb{R}\) is a partial Markov kernel, we still need to verify that \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) is measurable and that on this domain, \(\mathsf{es}_\mathbb{R}(T | {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em})\) is measurable for every measurable \(T \subseteq \mathbb{R}\). The former follows by analogous arguments as before, as \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) consists of all sequences \((x_n)\) such that \[\begin{align} &\forall \ell \in \mathbb{N}, \; \exists N \in \mathbb{N} \; : \\ &\quad \quad \forall m, n \geq N, \; \forall t \in \mathbb{Q} \; : \\ &\quad \quad \quad \quad \mathopen{}\mathclose{\left| \frac{|\{ i \leq n \mid x_i \leq t\}|}{n} - \frac{|\{i \leq m \mid x_i \leq t\}|}{m} }\right| < \ell^{-1}. \end{align}\] which shows that \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) is a \(\mathbf{\Pi}^0_4\) set. The measurability of \(\mathsf{es}_\mathbb{R}(T | {\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em})\) also holds by the same token for the sets of the form \(T = (-\infty, t]\) with \(t \in \mathbb{Q}\). Since these generate the Borel \(\sigma\)-algebra on \(\mathbb{R}\), the general case follows by the \(\pi\)-\(\lambda\) theorem.
The remainder of the proof is analogous to the countable case, with all measurable sets being of the form \((-\infty, t)\) and all limits existing uniformly. The corresponding version of 112 holds thanks to [prop:exchangeable95ecdf]. ◻
Before proving [prop:tightened95es] in full, we first treat the restricted case of \(\mathbb{R}_+\). To this end, we consider the positive and negative parts of a real number \(x \in \mathbb{R}\), \[x^+ \mathrel{\vcenter{:}}= \max\{x, 0\} \qquad \text{and} \qquad x^- \mathrel{\vcenter{:}}= \max\{-x, 0\},\] so that we have \(x = x^+ - x^-\) and \(\@ifstar{\abs}{\abs*}{x} = x^+ + x^-\). We also write \[\begin{align} \pi : \mathbb{R}&\longrightarrow \mathbb{R}_+ \\ x &\longmapsto x^+ \end{align}\] for the positive part function and \(\iota : \mathbb{R}_+ \hookrightarrow \mathbb{R}\) for the inclusion map. Then \[\mathsf{es}_{\mathbb{R}_+} \mathrel{\vcenter{:}}= \pi \mathchoice{\,}{\,}{}{} \mathsf{es}_\mathbb{R} \mathchoice{\,}{\,}{}{} \iota^\mathbb{N}\] is an empirical sampling morphism for \(\mathbb{R}_+\) by [lem:transfer95es].
The empirical sampling morphisms \(\mathsf{es}_\mathbb{R}\) and \(\mathsf{es}_{\mathbb{R}_+}\) satisfy lax naturality with respect to \(\pi\), i.e. \[\label{eq:relu95lax95naturality} \mathsf{es}_{\mathbb{R}_+} \mathchoice{\,}{\,}{}{} \pi^\mathbb{N}\sqsupseteq\pi \mathchoice{\,}{\,}{}{} \mathsf{es}_{\mathbb{R}}.\tag{114}\]
Proof. First let us show that \(\mathrm{dom}\mathopen{}\mathclose{\left(\pi \mathchoice{\,}{\,}{}{} \mathsf{es}_{\mathbb{R}}}\right)\) is a subset of \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_{\mathbb{R}_+} \mathchoice{\,}{\,}{}{} \pi^\mathbb{N}}\right)\). To this end, consider an arbitrary sequence \((x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_{\mathbb{R}}}\right)\). The finite empirical CDFs of the sequence \((x_i^+)\) coincide with those of the original sequence \((x_i)\) on the positive axis (including \(0\)) while vanishing on the negative axis. Therefore the uniform convergence is preserved.
It is also clear that the limiting CDF is the one of the pushforward measure, which likewise arises by truncation of the limiting CDF of the original sequence. Therefore, \(\mathsf{es}_{\mathbb{R}_+} \mathchoice{\,}{\,}{}{} \pi^\mathbb{N}\) coincides with \(\pi \mathchoice{\,}{\,}{}{} \mathsf{es}_{\mathbb{R}}\) when restricted to the domain of the latter. This completes the proof of the lemma. ◻
Similar to [prop:tightened95es], we now consider a “tightened” version of \(\mathsf{es}_{\mathbb{R}_+}\) that we denote by \(\overline{\mathsf{es}}_{\mathbb{R}_+}\). This is defined like \(\mathsf{es}_{\mathbb{R}_+}\), but with the additional restriction that a sequence \((x_i)\) is in the domain of \(\overline{\mathsf{es}}_{\mathbb{R}_+}\) if and only if it is in the domain of \(\mathsf{es}_{\mathbb{R}_+}\) and additionally \[\label{eq:es95integral95Eabs952} \int_{\mathbb{R}_+} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y | (x_i)) = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i\tag{115}\] holds, where both sides may be infinite. This defines a partial Markov kernel \(\overline{\mathsf{es}}_{\mathbb{R}_+} : \mathbb{R}_+^\mathbb{N}\to \mathbb{R}_+\).
The partial Markov kernel \(\overline{\mathsf{es}}_{\mathbb{R}_+}\), defined as above, is an empirical sampling morphism for \(\mathbb{R}_+\) in \(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\),
Proof. The proof that \(\overline{\mathsf{es}}_{\mathbb{R}_+}\) is a partial Markov kernel is analogous to the previous cases. While permutation invariance is clear, empirical adequacy is where the main work lies.
We are essentially using the same empirical sampling as in [lem:real95es], the only change being a more restricted domain. Therefore, the only additional step to show is that the left-hand side of 67 is a total morphism for every total \(f\). This is what we focus on in the remainder of the proof. To simplify notation, we assume without loss of generality that \(f\) has no input, which makes it into a probability measure \(p : I \to \mathbb{R}_+^\mathbb{N}\otimes Y\).
Assuming that such \(p\) is exchangeable in the first factor, we need to show \[p \bigl( \mathrm{dom}\mathopen{}\mathclose{\left(\overline{\mathsf{es}}_{\mathbb{R}_+}}\right) \times Y \bigr) = 1.\] By what we have already shown in the previous proofs of empirical adequacy, this is equivalent to saying that 115 holds \(p\)-almost surely whenever the \((x_i)\) is a random sequence with exchangeable distribution.
For any given \(r \ge 0\), we decompose each \(x_i\) as \(x_i = x_i^{\le r} + x_i^{> r}\), where \[x_i^{\le r} \mathrel{\vcenter{:}}= x_i\, 1_{[0,r]}(x_i), \qquad x_i^{> r} \mathrel{\vcenter{:}}= x_i\,1_{(r,\infty)}(x_i),\] so that \(x_i\) is equal to exactly one of them. We conduct the proof by showing that the second of the two inequalities in \[\label{eq:supinf95ineqs} \limsup_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i \le \int_{\mathbb{R}_+} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y \mid (x_i)) \le \liminf_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i\tag{116}\] holds for every sequence in \(\mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_\mathbb{R}}\right)\) and subsequently showing that the first one holds \(p\)-almost surely. These two facts imply that 115 holds \(p\)-almost surely.
The second inequality in 116 can be shown by taking the \(r \to \infty\) limit of \[\begin{align} \label{eq:tightened95es95proof951} \int_{[0,r]} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y | (x_i)) &\leq \int_{[0,r]} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y | (x_i)) + \liminf_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^{> r} \\ &= \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^{\le r} + \liminf_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^{> r} \\ &\leq \liminf_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i, \end{align}\tag{117}\] where the first inequality is by \(r \ge 0\), the equality is an instance [prop:es95integral], and the last inequality is the superadditivity of the limit inferior.
In order to prove the first inequality in 116 , we can assume without loss of generality that the integral on its right-hand side is finite. Then, we have \[\begin{align} \limsup_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i &\leq \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^{\le r} + \limsup_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^{> r} \\ &= \int_{[0,r]} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y | (x_i)) + \limsup_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^{> r} \\ &\leq \int_{[0,r]} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y | (x_i)) + \sup_{n} \frac{1}{n} \sum_{i=1}^n x_i^{> r}, \end{align}\] where the first inequality is by the subadditivity of limit superior and the equality is again by [prop:es95integral]. Taking the \(r \to \infty\) limit gives \[\limsup_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i \leq \int_{\mathbb{R}_+} y \, \mathsf{es}_\mathbb{R}(\mathrm{d}y | (x_i)) + \lim_{r \to \infty} \sup_{n} \frac{1}{n} \sum_{i=1}^n x_i^{> r}.\] It now suffices to argue that the second term on the right-hand side vanishes \(p\)-almost surely. To this end, for a fixed \(\varepsilon> 0\), an application of [lem:maximal95ergodic] gives \[\undefined*{\sup_n \frac{1}{n} \sum_{i=1}^n x_i^{>r} > \varepsilon} \le \varepsilon^{-1} \E*{x_1^{>r}}.\] Since the functions \(x \mapsto x^{>r}\) converge to zero pointwise as \(r \to \infty\), the monotone convergence theorem implies that \(\E{x^{>r}}\) converges to \(0\). We thus conclude that \[\lim_{r \to \infty} \sup_n \frac{1}{n} \sum_{i=1}^n x_i^{>r} \le \varepsilon\] holds \(p\)-almost surely for any \(\varepsilon> 0\), as was to be shown. ◻
Proof of [prop:tightened95es]. We can generally proceed by the same arguments as in the proof of [lem:es95nonnegative]. However, we still need to show \[\label{eq:dom95esav} p \bigl( \mathrm{dom}\mathopen{}\mathclose{\left(\overline{\mathsf{es}}_{\mathbb{R}}}\right) \times Y \bigr) = 1\tag{118}\] for any exchangeable \(p : I \to \mathbb{R}^\mathbb{N}\otimes Y\), i.e.that the conditions in [def:es95av] that are additionally imposed, on top of those in [def:es95R], hold almost surely for a random sequence \((x_i)\) with an exchangeable distribution.
To this end, let \(L_+ \subseteq \mathbb{R}^\mathbb{N}\) be the set of those sequences, whose positive part is an element of the domain of \(\overline{\mathsf{es}}_{\mathbb{R}_+}\) and similarly for \(L^-\): \[\begin{align} L^+ &\coloneq \@ifstar{\Set}{\Set*}{ (x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_{\mathbb{R}}}\right) \int_\mathbb{R}y^+ \, \mathsf{es}_\mathbb{R}\bigl(\mathrm{d}y \,|\, (x_i) \bigr) = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^+ } \\ L^- &\coloneq \@ifstar{\Set}{\Set*}{ (x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_{\mathbb{R}}}\right) \int_\mathbb{R}y^- \, \mathsf{es}_\mathbb{R}\bigl(\mathrm{d}y \,|\, (x_i) \bigr) = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^- } . \end{align}\] Note that, for any \((x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\mathsf{es}_{\mathbb{R}}}\right)\), we also have \[\label{eq:int95positive95part} \int_{\mathbb{R}} y^+ \, \mathsf{es}_\mathbb{R}\bigl( \mathrm{d}y \,|\, (x_i) \bigr) = \int_{\mathbb{R}_+} y \,\, (\pi \mathchoice{\,}{\,}{}{} \mathsf{es}_{\mathbb{R}}) \bigl( \mathrm{d}y \,|\, (x_i) \bigr) = \int_{\mathbb{R}_+} y \, \mathsf{es}_{\mathbb{R}_+} \bigl( \mathrm{d}y \,|\, (x_i^+) \bigr),\tag{119}\] where the first equation is by change of variables and the second by the lax naturality from [lem:relu95lax95naturality]. The other integral in 118 can be treated analogously.
Since both \((x_i^+)\) and \((x_i^-)\) have an exchangeable distribution, we thus obtain \[p(L^+ \otimes Y) = 1 = p(L^- \otimes Y)\] by [lem:es95nonnegative], so that \((L^+ \cap L^-) \otimes Y\) also has full measure.
We complete the proof by showing \(L^+ \cap L^- \subseteq \mathrm{dom}\mathopen{}\mathclose{\left(\overline{\mathsf{es}}_{\mathbb{R}}}\right)\), from which 118 then follows. We distinguish several distinct cases for the values of \[\lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^+ \qquad \text{and} \qquad \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n x_i^- .\]
If both of the limits are finite, we obtain 83 by adding the two defining equations of \(L^+\) and \(L^-\), respectively, and we obtain 115 by subtracting them.
If at least one is infinite, then this limit is necessarily \(+\infty\) since both sequences are non-negative, and we get 83 by adding the two equations and getting \(+\infty\) too.
In both cases, \((x_i) \in L^+ \cap L^-\) implies \((x_i) \in \mathrm{dom}\mathopen{}\mathclose{\left(\overline{\mathsf{es}}_{\mathbb{R}}}\right)\), and thus the proof is complete. ◻
However, making this precise for unbounded \(f\) requires dealing with a number of subtleties, which we return to in 3.3.↩︎
Technically, we need a positive quasi-Markov category in which balanced idempotents split.↩︎
In this article, we use \(\mathbb{N}= \{1,2,3,\ldots\}\) as the conventionally chosen countably infinite set.↩︎
The formal empirical adequacy axiom in [def:es] is slightly stronger than this, but here we focus on the case \(Y = I\) for simplicity, which contains the essence of the idea.↩︎
This fresh perspective has also gained popularity in the computer science community, as it allows for a more systematic treatment of the logic underlying probability theory [14], [15] as well as applications to topics including active inference [16], random graphs [17], causal inference [18] and evidential decision theory [19], to name a few.↩︎
As an alternative to \(f({\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}|x)\) being undefined for \(x \notin D_f\), we could also set \(f(T|x) = 0\) for all measurable sets \(T \subseteq Y\). However, this should be used with caution, since we cannot use the Chapman–Kolmogorov 7 for those \(x \in D_f\) that lie outside \(D_{g \mathchoice{\,}{\,}{}{} f}\) as given by 9 . Namely if \(x \in D_f\) and we have \(0 < f(D_g|x) < 1\), then Chapman–Kolmogorov equation would give \(0 < (g \mathchoice{\,}{\,}{}{} f)(Z|x) < 1\) which contradicts quasi-totality. In other words, it is important that our composite fails either if the first part \(f\) fails or if the second part \(g\) fails with non-zero probability.↩︎
This shows that compatibility with post-composition holds also without positivity.↩︎
Our choice of \(m\) merely ensures that the domain contains all the components in the forward image. Any larger integer would work as well, as the corresponding morphism would simply discard all additional inputs.↩︎
Here, \(\mathsf{samp}^{(n)}\) denotes the \(n\)-fold copy of \(PX\) followed by \(\mathsf{samp}^{n}\), in analogy to the notation from 43 .↩︎
\(\mathsf{Partial}\mathopen{}\mathclose{\left({\mathsf{BorelStoch}}}\right)\) is one such category, as we elaborate on in 4 (specifically, [thm:representability]).↩︎
While the preservation of the limit by \({{\kern 0.06em}\mathord{\rule[-0.05em]{0.6em}{0.05em}}{\kern 0.06em}} \otimes \mathrm{id}_Y\) was not considered in [3], this can be shown by the same arguments. See also [13] for a similar result.↩︎
See [27] for the proof that observational representability implies -compatible representability.↩︎
This means that \((X^\sigma \otimes \mathrm{id}_Y) \mathchoice{\,}{\,}{}{} f = f\) holds for every finite permutation \(\sigma\).↩︎
For more details about the concept of tight sequences, see [35].↩︎
This means that there is a function \(f \colon \mathbb{N}\to [0,1]\) such that for every \(\varepsilon>0\) there is \(N\in\mathbb{N}\) with \[\mathopen{}\mathclose{\left| \frac{|\{ i \le n \mid x_i \le t \}|}{n} - f(t) }\right| < \varepsilon\qquad \forall n \ge N, t \in \mathbb{N}.\]↩︎
Recall that \(\mathbb{N}\), by convention, does not contain \(0\) (3).↩︎
Recall that \(f^{\sharp} : A \to PX\) denotes the counterpart of \(f : A \to X\) via Bijection 58 .↩︎
That result is stated for Markov categories, but the proof works in quasi-Markov categories just as well.↩︎
We write \(X^\mathbb{N}\) instead of \(X^{\mathbb{N}\setminus\{1\}}\) in the string diagrams to save space.↩︎
Although [3] was proven in the context of Markov categories, the proof is the same also for quasi-Markov categories.↩︎
Recall the symbol \(=_{p^\mathbb{N}\text{-a.s.}}\) refers to equality \(p^\mathbb{N}\)-almost surely ([def:ase]).↩︎
While the general formula is given e.g. at [40], it is worth noting that for our purposes we only need to know that this formula corresponds to the sum over partitions mentioned above and that \(\kappa_1(D) = 0\).↩︎
Technically the case \(i = j\) needs to be considered separately, but this does not affect the conclusion, since a change of \(\frac{1}{n}\) in the relative frequency is negligible for \(n \gg \varepsilon^{-1}\), and this is the relevant case as we consider asymptotics in \(n\) for fixed \(\varepsilon\).↩︎