2.1 Dynamical systems and categories

In ergodic theory and related fields, one is mostly interested in the following two types of dynamical system:

1. (1) a set or space X with some structure (topology, measure, etc.), and a map or kernel $t:X\to X$ preserving that structure;

2. (2) a set or space X with some structure, and a group acting on X in a structure-preserving way.

Both dynamics are encompassed by the notion of a monoid: every group is a monoid, and every map $t:X\to X$ generates a monoid via iterations, $\{\mathrm {id},t,t^2,\dots \}$ .

In terms of category theory, a monoid is equivalently a category with a single object. Given a monoid M, denote by ${\mathsf {B}}M$ the category with a single object, denoted by $\bullet $ , and with the set of arrows $\bullet \to \bullet $ given by M, with its identity and composition.

Let now ${\mathsf {C}}$ be a category (for example, the category ${\mathsf {Meas}}$ of measurable spaces and measurable maps). A dynamical system can be modeled as a functor ${\mathsf {B}}M\to {\mathsf {C}}$ . Let us see this explicitly. Such a functor maps:

• • the unique object $\bullet $ of ${\mathsf {B}}M$ to an object X of ${\mathsf {C}}$ (for example, a measurable space). This is the object (or ‘space’) where the dynamics takes place;

• • each arrow of ${\mathsf {B}}M$ , i.e. each element m of the monoid M, to an ‘induced’ arrow $X\to X$ (for example, a measurable map). This is the dynamics.

For brevity, we denote the dynamical system just by X whenever this does not cause ambiguity, and we denote the map $X\to X$ induced by $m\in M$ again by m, writing $m:X\to X$ .

If $M=\mathbb {N}$ , the monoid is generated by the number $1$ , and so the dynamics is generated by the arrow induced by $1$ (for example, a measurable map), which then is iterated. We usually denote the resulting map by $t:X\to X$ .

Here are other examples of categories ${\mathsf {C}}$ .

• • If ${\mathsf {C}}$ is the category of compact Hausdorff spaces and continuous maps, a functor ${\mathsf {B}}M\to {\mathsf {C}}$ is a (compact) topological dynamical system.

• • If ${\mathsf {C}}$ is the category of measure spaces and measure-preserving maps, a functor ${\mathsf {B}}M\to ~{\mathsf {C}}$ is a measure-preserving dynamical system.

• • If $M=\mathbb {N}$ and ${\mathsf {C}}$ is the category of measurable spaces and Markov kernels, a functor ${\mathsf {B}}M\to {\mathsf {C}}$ is a (discrete-time) Markov chain.

One of the most useful contributions of the categorical formalism to dynamical systems is a systematic treatment of invariant states and observables. Consider a dynamical system on the object X indexed by the monoid M. A cone over X is an object C together with an arrow $c:C\to X$ such that for every $m\in M$ , the following diagram commutes.

(1)

In general, cones over a given dynamical system have the interpretation of ‘invariant states of some kind.’ Indeed, in the category of sets and functions, if C is a one-point set, the arrow $c:C\to X$ is the inclusion of some point $x\in X$ , and the diagram in equation (1) just says that x is a fixed point, that is, $m(x)=x$ . More generally, if C is not a one-point set, the arrow $c:C\to X$ selects a C-indexed family of fixed points in X. (Note that what matters here is that each individual point $c(i)$ is a fixed point, rather than any property of the range $\{ c(i) : i \in C \} \subseteq X$ of c as a subset.)

Since the diagram in equation (1) can be written as $m\circ c = c$ , sometimes one says that m is a left-invariant morphism (since m acts on the left of c). Note that the commutativity of the diagram in equation (1) needs only to be checked on generators of M. For example, for $M=\mathbb {N}$ , it suffices to check the condition for $1\in \mathbb {N}$ , the map that we usually denote by $t:X\to X$ .

A cone $C\to X$ over X is universal, or a limit, if for every (other) cone $D\to X$ , there is a unique arrow $D\to C$ such that for every $m\in M$ , the following diagram commutes.

The limit cone C, if it exists, is unique up to isomorphism, and can be interpreted as the ‘largest subspace of X of invariant states.’ In the category of sets, it is precisely the set of all invariant points (which can be empty), and in other categories, it has a similar interpretation. We denote the limit, if it exists, by $X^{\mathrm {inv}}$ .

Dually, a cocone under the dynamical system X, or a right-invariant morphism, is an object R together with an arrow $r:X\to R$ such that for all $m\in M$ , $f\circ m= f$ , i.e. the following diagram commutes.

This has the interpretation of an invariant function or invariant observable. In the category of sets, this is precisely a function with the property that $r(mx)=r(x)$ , i.e. it is constant on each orbit.

A cocone is universal, or a colimit, if for every (other) cocone $X\to S$ , there is a unique arrow $R\to S$ such that for every $m\in M$ , the following diagram commutes.

Again, this object, if it exists, is unique up to isomorphism, and it can be interpreted as the ‘finest invariant observable.’ In the category of sets, it is precisely the set of orbits, and the commutation of the last diagram says precisely that every invariant observable factors through the orbits. In other categories, the interpretation is similar (for example, for compact Hausdorff spaces, one obtains the quotient by the smallest closed equivalence relation which contains the orbits). We denote the colimit X, if it exists and up to isomorphism, by $X_{\mathrm {inv}}$ .

Further categorical formalism for dynamical systems, similar in spirit to this section, can be found in [Reference Behrisch, Kerkhoff, Pöschel, Schneider and Siegmund2], for the case of Cartesian closed categories.

2.2 Basic concepts of Markov categories

Markov categories are a category-theoretic framework for probability and related fields. They allow us to express several conceptual aspects of probability theory (such as stochastic dependence and independence, almost-sure equality, and conditional distributions) in a graphical language, where the formalism takes care automatically of the measure-theoretic aspects. See [Reference Fritz5] for more details.

The basic idea of a Markov category, which we will define shortly, is that of a category whose morphisms are ‘probabilistic maps’ or ‘transitions.’ One of the most basic examples is the category ${\mathsf {FinStoch}}$ , where:

• • objects are finite sets, which we denote by X, Y, etc.;

• • morphisms are stochastic matrices. A stochastic matrix from X to Y is a function

  
  such that for all $x\in X$ , we have $\sum _{y\in Y} k(y|x)=1$ . A possible interpretation is a transition probability from state x to state y;

• • the composition of stochastic matrices is equivalently the Chapman–Kolmogorov formula. For $k:X\to Y$ and $h:Y\to Z$ ,

  $$ \begin{align*} h\circ k(z|x) = \sum_{y\in Y} h(z|y) \, k(y|x). \end{align*} $$

The most important example is the category ${\mathsf {Stoch}}$ , where:

• • objects are measurable spaces, which we denote as either $(X,\Sigma _X)$ or more briefly as X;

• • morphisms are Markov kernels. A Markov kernel from X to Y is a function

  
  such that:

  • – for each $x\in X$ , the assignment $B\mapsto k(B|x)$ is a probability measure on Y;

  • – for each $B\in \Sigma _Y$ , the assignment $x\mapsto k(B|x)$ is a measurable function on X.

  A possible interpretation of the quantity $k(B|x)$ is the ‘probability that the next state is in B if the current state is x;’

• • the composition of Markov kernels is given by the integral version of the Chapman–Kolmogorov formula. For $k:X\to Y$ and $h:Y\to Z$ , and for each measurable $C\in \Sigma _Z$ ,

  $$ \begin{align*} h\circ k(C|x) = \int_{Y} h(C|y) \, k(dy|x). \end{align*} $$

Every measurable function $f:X\to Y$ defines a ‘deterministic’ Markov kernel $K_f$ as follows.

(2)

for each $x\in X$ and $B\in \Sigma _Y$ . This construction defines then a functor $K:{\mathsf {Meas}}\to {\mathsf {Stoch}}$ from measurable functions to Markov kernels.

Markov categories can be considered an abstraction of the category ${\mathsf {Stoch}}$ , where the main categorical properties are formulated as axioms, and used to prove theorems of probability without having to use measure theory directly.

One of the main structures of the categories ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ , which figures prominently in the definition of Markov categories, is the concept of a monoidal or tensor product. The basic idea is that, sometimes, one wants to consider two systems and talk about joint or composite states. Sometimes, the systems transition independently, and sometimes they interact. The categorical notion of a tensor product (generalizing, for example, the usual tensor of vector spaces) models this idea. Indeed, given objects X and Y, we want to form a ‘composite’ object, denoted by $X\otimes Y$ . In ${\mathsf {Stoch}}$ , we take the Cartesian product of measurable spaces, with the product $\sigma $ -algebra. Moreover, given morphisms $k:X\to Y$ and $h:Z\to W$ , we want a morphism $k\otimes h:X\otimes Z\to Y\otimes W$ , with the interpretation that in this case, the dynamics is given by k and h independently on the two subsystems. This means that the tensor product is a functor of two variables, $\otimes :{\mathsf {C}}\otimes {\mathsf {C}}\to {\mathsf {C}}$ . In ${\mathsf {Stoch}}$ , this is given by the (independent) product of Markov kernels,

$$ \begin{align*} k\otimes h(B,D|x,z) = k(B|x) \, h(D|z) \end{align*} $$

for all $x\in X$ , $z\in Z$ , $B\in \Sigma _Y$ , and $D\in \Sigma _W$ . It is helpful to use string diagrams to represent these products. We draw a morphism $k:X\to Y$ as the following diagram, which should be read from bottom to top.

We can write the tensor product $k\otimes h$ by simply juxtaposing the two morphisms, as follows.

This notation reflects the fact that the two subsystems do not interact. A general morphism between $X\otimes Z$ and $Y\otimes W$ will exhibit interaction and will not be in the form above—we represent it as follows.

Moreover, we need a unit object I, which accounts for a ‘trivial’ state. In ${\mathsf {Stoch}}$ , this is the one-point measurable space. Markov kernels of the form $p:I\to X$ are equivalently just probability measures in X. In general, we call morphisms in this form states, and denote them as follows.

We have associativity and unitality isomorphisms which resemble the axioms for a monoid,

$$ \begin{align*} (X\otimes Y)\otimes Z \cong X\otimes(Y\otimes Z) ,\quad X\otimes I \cong X \cong I\otimes X , \end{align*} $$

and so, a category with this notion of product is called a monoidal category. A monoidal category is symmetric if each product $X\otimes Y$ is isomorphic to $Y\otimes X$ in a very strong sense, so that for all practical purposes, the order of the factors does not matter. For the rigorous definition of a monoidal category, see for example [Reference Lane17, §VII.1]. The categorical product with its usual universal property satisfies the axioms of a monoidal product, in that case, one talks about a Cartesian monoidal category. The categories ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ are symmetric monoidal, but not Cartesian. In general, whenever randomness is involved, we do not want a Cartesian category (see below for more on this).

Here is the rigorous definition of a Markov category.

In ${\mathsf {Stoch}}$ , the copy and discard maps are the kernels obtained by the following measurable functions. The copy map corresponds from the diagonal map $X\to X\times X$ which literally ‘copies the state,’ $x\mapsto (x,x)$ . The discard map corresponds to the unique map to the one-point space $X\to I$ .

2.3 Graphical definitions of probabilistic concepts

The formalism of Markov categories allows us to express several concepts of probability theory in categorical and graphical terms. The first notion we can look at is stochastic independence. First of all, notice that given a joint state $p:I\to X\otimes Y$ , we can form the marginal $p_X$ on X by simply discarding Y.

In ${\mathsf {Stoch}}$ , this corresponds to saying that the marginal on X is the pushforward of the measure p along the projection map $X\times Y\to X$ .

Definition 2.2. A joint state $p:I\to X\otimes Y$ is said to exhibit independence of X and Y if the following holds.

(3)

More generally, a morphism $p:A\to X\otimes Y$ is said to exhibit conditional independence of X and Y given A if the following holds.

In ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ , these correspond to the usual notions. For example, equation (3) in ${\mathsf {FinStoch}}$ corresponds to saying that

$$ \begin{align*} p(x,y) = p_X(x)\,p_Y(y) \end{align*} $$

for all x and y, and in ${\mathsf {Stoch}}$ corresponds to saying that

$$ \begin{align*} p(A\times B) = p_X(A)\,p_Y(B) \end{align*} $$

for all measurable sets $A\in \Sigma _X$ and $B\in \Sigma _Y$ .

Another natural concept in Markov categories is the notion of a deterministic morphism.

Definition 2.3. A morphism $f:X\to Y$ in a Markov category ${\mathsf {C}}$ is called deterministic if the following identity holds.

(4)

We denote by ${{\mathsf {C}}}_{\det }$ the subcategory of ${\mathsf {C}}$ of deterministic morphisms.

Intuitively, if f carries non-trivial randomness, then the identity above cannot hold: on the left, we have perfect correlation given A and on the right, we have conditional independence given A.

For a state $p:I\to X$ , the condition in equation (4) reads as follows.

(5)

In ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ , these are exactly those measures (and kernels in the general case) which can only have values zero and one. Indeed, equation (5) says that for each pair of measurable sets $A,B\in \Sigma _X$ , we have

$$ \begin{align*} p(A\cap B) = p(A)\,p(B). \end{align*} $$

In particular, for $A=B$ , we get $p(A)=p(A)^2$ , i.e. $p(A)=0$ or $p(A)=1$ . Every Dirac delta probability measure is of this form. On standard Borel spaces, only Dirac deltas are in this form, and so every deterministic morphism between standard Borel spaces comes from an ordinary measurable function, via the construction in equation (2). If one considers coarser $\sigma $ -algebras, however, there are measures which are deterministic (according to Definition 2.3), but which are not Dirac deltas. These are extremely important, for example, most ergodic measures are of this form, if one considers the $\sigma $ -algebra of invariant sets (see Definition 3.8). In other words, we have functors

and the first functor is not quite the identity. When we speak generally of deterministic Markov kernels, we will mean kernels with value zero and one, which are more general than the ones obtained by a measurable function via the functor K of equation (2). The advantage of working with this category will become clear in §3, and also in Appendix A. For more theory on those deterministic morphisms which are not Dirac deltas, see [Reference Moss and Perrone18].

Therefore, one can view Cartesian categories as precisely those Markov categories with only trivial randomness.

Another concept of probability theory which can be expressed in terms of Markov categories is the concept of almost-sure equality, first introduced in [Reference Cho and Jacobs4, Definition 5.1] and expanded in [Reference Fritz5, Definition 13.1].

Definition 2.5. In a Markov category, let $p:A\to X$ and let $f,g:X\to Y$ . We say that f and g are p-almost surely (a.s.) equal if

In particular, for states, this reads as follows.

In ${\mathsf {Stoch}}$ , this condition is equivalent to the usual almost-sure equality for the measure p.

If f is a morphism and R is an equationally defined property that f may or may not satisfy, we say that f satisfies the R property p-a.s. if and only if the relevant morphisms are equal p-a.s. For example, we say that f is p-a.s. deterministic if and only if equation (4) holds p-a.s., i.e. the following condition holds.

See also [Reference Fritz5, Definition 13.11].

We now turn to conditioning. There are a few variations of the idea of conditionals and disintegrations. We will use the following one. For additional context, see [Reference Fritz5, §11].

Definition 2.6. In a Markov category ${\mathsf {C}}$ , let $p:I\to X$ be a state and let $f:X\to Y$ be a morphism. A disintegration of p via f, or a Bayesian inversion of f with respect to (w.r.t.) p, is a morphism $f^+_p: Y\to X$ such that the following holds.

In ${\mathsf {Stoch}}$ , this definition reads as follows, if we denote the state $f\circ p:I\to Y$ by q. Given a probability measure p on X and a Markov kernel (for example, a measurable function) $f:X\to Y$ , the Markov kernel $f^+_p: Y\to X$ is such that for all measurable subsets $A\in \Sigma _X$ and $B\in \Sigma _Y$ ,

$$ \begin{align*} \int_A f(B|x) \,p(dx) = \int_B f^+_p(A|y) \, q(dy). \end{align*} $$

In ${\mathsf {FinStoch}}$ , the condition has the even simpler form

$$ \begin{align*} p(x) \, f(y|x) = q(y) \, f^+_p(x|y). \end{align*} $$

This can be therefore seen as a categorical definition of Bayesian inversion, and if f is deterministic, as a disintegration of p in the sense of disintegration theorems (see for example [Reference Bogachev3, §10.6]).

It follows immediately from the definition that any two disintegrations of p via f as above are equal q-a.s., generalizing what happens in ordinary measure theory.

Proposition 2.7. Let $f:X\to Y$ be deterministic. Let $p:I\to X$ and suppose that the disintegration $f^+_p:Y\to X$ exists. Then, the composite

is $(f\circ p)$ -a.s. equal to the identity.

This was mentioned in [Reference Fritz5], directly after Proposition 11.17 therein. We include a proof here, for completeness.

Proof. We have that

where the first equality is by definition of $f^+_p$ and the second equality is by determinism of f.

In ${\mathsf {Stoch}}$ , every standard Borel space has disintegrations, this statement is sometimes known as (Rokhlin’s) disintegration theorem. See for example [Reference Tao20, Theorem 4 and Remark 5], [Reference Viana and Oliveira21, Theorem 5.1.11 and related sections], as well as [Reference Bogachev3, §10.6].

2.4 Dynamical systems in Markov categories

A dynamical system in a Markov category can be interpreted as a ‘stochastic’ dynamical system in general. For example, a dynamical system in ${\mathsf {Stoch}}$ with monoid $\mathbb {N}$ is a discrete-time Markov process. In this work, we are mostly interested in dynamical systems in the subcategory of deterministic morphisms of a Markov category. These are interpretable as traditional deterministic dynamical systems. The advantage of working in the larger Markov category (rather than in ${\mathsf {Meas}}$ ) is the convenience of having states (measures) and conditionals (kernels) fit in the same language. Moreover, as we have seen, there are deterministic morphisms in ${\mathsf {Stoch}}$ which are not just measurable functions, and these are going to be crucial to talk about ergodicity.

Let X be a dynamical system with monoid M in a Markov category ${\mathsf {C}}$ . Following the intuition of §2.1, we have the following.

• • A left-invariant state (as known as (a.k.a.) cone) from the monoidal unit $p:I\to X$ is a state satisfying $m\circ p=p$ for all $m\in M$ . This can be interpreted as an ‘invariant random state,’ or ‘invariant measure.’ In ${\mathsf {Stoch}}$ , these are invariant measures. For deterministic dynamical systems generated by measurable functions in the form $m:X\to X$ , this is a measure p satisfying

  $$ \begin{align*} p(m^{-1}(A)) = p(A) \end{align*} $$
  for every measurable set $A\in \Sigma _X$ . More generally, for dynamical systems generated by kernels, in the form $m:X\times \Sigma _X\to [0,1]$ , the invariance of p means that for every measurable $A\in \Sigma _X$ ,
  $$ \begin{align*} \int_X m(A|x) \,p(dx) = p(A). \end{align*} $$

• • More generally, a left-invariant morphism (a.k.a. cone) from a generic object $c:C\to ~X$ is a morphism satisfying $m\circ c=c$ for all $m\in M$ . This can be interpreted either as a ‘transition to an invariant state,’ or as a family of invariant states parameterized (measurably) by C. In ${\mathsf {Stoch}}$ , the interpretation is similar to invariant measures, except that they depend measurably on a parameter.

• • A right-invariant morphism (a.k.a. cocone) $r:X\to R$ is a morphism satisfying $r\circ m=r$ for all $m\in M$ . This can be interpreted as an ‘invariant function or invariant observable,’ especially when r is deterministic. In ${\mathsf {Stoch}}$ , these indeed correspond to invariant functions, or invariant kernels. For dynamical systems where M acts by measurable functions $m:X\to X$ , this means a measurable map $r:X\to R$ satisfying

  $$ \begin{align*} r(m(x)) = r(x) \end{align*} $$
  for every $x\in X$ and $m \in M$ . More generally, for dynamical systems where M acts by kernels $m:X\times \Sigma _X\to [0,1]$ , the right-invariance of a kernel r means that for every $x\in X$ , $m\in M$ , and $B\in \Sigma _R$ ,
  (6) $$ \begin{align} \int_X r(B|x') \, m(dx'|x) = r(B|x). \end{align} $$

From now on, when we talk about an invariant state, we always mean a left-invariant state (in ${\mathsf {Stoch}}$ , an invariant measure). When we talk about an invariant observable, we talk about a right-invariant morphism (in ${\mathsf {Stoch}}$ , an invariant measurable map or kernel). We are mostly interested in deterministic invariant observables.

3.1 Mixtures of states

Let us define a categorical version of convex decompositions, which can be constructed in any Markov category.

For motivation, let X be a finite set and let p be a (discrete) probability measure on X. Let now $k_1,\dots ,k_n$ be other probability measures on X. We say that p is a convex combination of the $k_i$ with coefficients $q_i$ if

$$ \begin{align*} p = \sum_{i=1}^n k_i \, q_i , \end{align*} $$

or more explicitly, for each $x\in X$ ,

(7) $$ \begin{align} p(x) = \sum_{i=1}^n k_i(x) \, q_i. \end{align} $$

For the $q_i$ to be the coefficients of a convex combination, we need $0\le q_i\le 1$ for all i, and $\sum _i q_i=1$ . In other words, we need the map $i\mapsto q_i$ to be a (discrete) probability measure on the set $\{1,\dots ,n\}$ . That way, $i\mapsto k_i$ can be considered a discrete kernel (or transition matrix) from $\{1,\dots ,n\}$ to X. Equation (7) can then be expressed as the (matrix) composition of q with k. Note that the values of $k_i$ when $q_i=0$ do not play any role.

More generally, if a generic finite set Y is indexing the convex combination, and writing $k(x|y)$ instead of $k_y(x)$ , we see that a convex decomposition of p,

$$ \begin{align*} p(x) = \sum_{y\in Y} k(x|y) \, q(y) , \end{align*} $$

is just the decomposition of $p:I\to X$ in the category ${\mathsf {FinStoch}}$ into a composite of stochastic matrices,

Let us now turn to the continuous case. Let X be a measurable space, and let p be a probability measure on X, which we can view as a morphism $p:I\to X$ of ${\mathsf {Stoch}}$ . In this category, decomposing $p:I\to X$ corresponds to writing it as a (measurably indexed) mixture of measures. Indeed, $k\circ q = p$ for a pair of morphisms $q:I\to Y, k:Y\to X$ if and only if for each measurable set $A\subseteq X$ , we have

$$ \begin{align*} p(A) = \int_Y k(A|y) \, q(dy). \end{align*} $$

If we consider k as a Y-indexed family of measures on X, and denote it by $y\mapsto k_y$ , then we are equivalently saying that

$$ \begin{align*} p = \int_Y k_y \, q(dy). \end{align*} $$

That is, p is a mixture of measures ( $k_y$ ) with mixing measure q. Note that the mixture only depends on the values of $k_y$ for q-almost all y.

Here is the general definition.

Not all distinctions between decompositions are interesting. For example, in the discussion above, changes to the values of $k_y$ on any set of q-measure zero are not interesting. In terms of Markov categories, we have the following. If $(q,k)$ is a decomposition of p and $k' : Y \to X$ is any other morphism with $k =_{q\text {-a.s.}} k'$ , it follows that $p = k \circ q = k' \circ q$ , whence $(q,k')$ is also a decomposition of p. Thus it would be somewhat natural to identify decompositions $(q,k), (q,k')$ whenever $k =_{q\text {-a.s.}} k'$ , but equivalence of decompositions plays no role in this paper beyond the special case of equivalence with the trivial decomposition (Definition 3.2).

In the discrete case, p always has a trivial decomposition: we can write p as

$$ \begin{align*} p = \sum_{y\in Y} p \, q(y) \end{align*} $$

for any normalized measure q. More generally, we can always write

$$ \begin{align*} p = \int_Y \tilde{p}_y \, q(dy) , \end{align*} $$

where $y\mapsto \tilde {p}_y$ is q-a.s. equal to p.

We can define this in general.

Definition 3.2. Let $(q:I\to Y, k:Y\to X)$ be a decomposition of $p:I\to X$ . We say that $(q,k)$ is a trivial decomposition of p if and only if k is q-a.s. equal to

We call the state p indecomposable if all its decompositions are trivial.

Clearly, each Dirac delta probability measure is indecomposable. This is part of Choquet theory, where one shows that the set of probability measures over a given space is a simplex (or an infinite-dimensional analog thereof), and its extreme points are exactly the Dirac delta, or more generally, the zero-one measures. (See for example [Reference Winkler22] for more on Choquet decompositions.) For general Markov categories, there is a similar relationship between indecomposable and deterministic states.

Proof. Let $p:I\to X$ be an indecomposable state. We can decompose p as $p=\mathrm {id}\circ p$ and, by hypothesis, this decomposition is trivial. Therefore, the identity $\mathrm {id}$ is p-a.s. equal to

That is,

Hence, p is deterministic.

The converse statement fails for general Markov categories, but it holds for a large class of them, including ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ . Recall from [Reference Fritz5, §11] that a Markov category is called positive if whenever a composite $f\circ p$ is deterministic, then the following equation holds.

(8)

This holds for ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ , and it is related to the fact that probabilities are non-negative (hence the name), see the original reference for more details.

Proof. If we instantiate the positivity condition in equation (8) with the case of a state, we get that for $p:I\to X$ and $f:X\to Y$ such that $f\circ p$ is deterministic, then

(9)

So let the composition $f\circ p$ be a deterministic state. The equation above says that f is p-a.s. equal to $f\circ p$ . Therefore, $f\circ p$ is indecomposable.

In conclusion:

• • in ${\mathsf {Stoch}}$ and ${\mathsf {FinStoch}}$ , convex combinations of measures can be described categorically as compositions of arrows (up to almost sure equality);

• • the deterministic states are precisely those that cannot be written as a non-trivial convex combination.

This is the notion of decomposition which we will use in our ergodic decomposition theorem (§3.4).

3.2 Markov quotients

For the purposes of this work, we need colimits of dynamical systems in a Markov category, which, as we have seen in §2.1, can be often interpreted as ‘quotient spaces’ or ‘spaces of orbits’ (more on this in Appendix A). In Markov categories, we need to require a little bit more of the usual universal property: it needs to play well with deterministic morphisms.

Alternatively and more explicitly, it is a map $r : X \to X_{\mathrm {inv}}$ , where:

• • for every invariant observable $s:X\to S$ , there exists a unique map $\tilde s:X_{\mathrm {inv}}\to S$ such that $s=\tilde s\circ r$ , i.e. making the following diagram commute for each $m\in M$ ;

  (10)

  

• • and moreover, the map $\tilde s$ is deterministic if and only if the map s is.

By taking $S = X_{\mathrm {inv}}$ and $s = r$ , so that $\tilde s = \mathrm {id}$ , we see that the second point implies that r is deterministic.

It is worth remarking on the connection between our Markov quotients and the Kolmogorov products introduced in [Reference Fritz and Rischel8]. The latter essentially suggests a notion of cofiltered limit appropriate to Markov categories, characterized by requiring the limiting property to hold in both the ${\mathsf {C}}$ and ${\mathsf {C}}_{\det }$ and to be preserved by all functors $(-) \otimes A$ for $A \in {\mathsf {C}}$ . By contrast, we do not require Markov quotients to be preserved by the tensor product here.

We have seen that the colimit of a dynamical system has the interpretation of a ‘space of orbits.’ In ${\mathsf {Stoch}}$ , at least when the dynamics is deterministic, the Markov colimit exists and is given by the invariant $\sigma $ -algebra. We will define this more precisely and then check the universal property (Proposition 3.7). In Appendix A, we will see in what sense it is similar to a space of orbits.

Definition 3.6. Let X be a dynamical system in ${\mathsf {Stoch}}$ with monoid M. A measurable set $A\in \Sigma _X$ is called invariant if for every $m\in M$ , we have

(11) $$ \begin{align} m(A|x) = 1_A(x) = \begin{cases} 1, & x\in A, \\ 0, & x\notin A. \end{cases} \end{align} $$

If the dynamical system is deterministic and generated by measurable functions $m:X\to X$ , the invariance condition in equation (11) can be written more simply as $m^{-1}(A)=A$ . As it is well known, both for the deterministic and for the generic case, invariant sets form a $\sigma $ -algebra, often called the invariant $\sigma $ -algebra.

Proof. Construct the kernel $r:X\to X_{\mathrm {inv}}$ as follows:

$$ \begin{align*} r(A|x) = 1_A(x) = \begin{cases} 1, & x\in A, \\ 0, & x\notin A \end{cases} \end{align*} $$

for every $x\in S$ and every measurable (invariant) set $A\in \Sigma _{X_{\mathrm {inv}}}$ . Note that it is exactly the kernel induced by the function $X\to X_{\mathrm {inv}}$ induced by the set-theoretic identity. As every measurable set of $X_{\mathrm {inv}}$ is measurable in X, this function is measurable, and so it induces a well-defined Markov kernel. Let us now prove that r is left-invariant. For every $m\in M$ , every $x\in X$ , and every measurable (invariant) set $A\in \Sigma _{X_{\mathrm {inv}}}$ ,

$$ \begin{align*} \int_X r(A|x') \,m(dx'|x) = \int_X 1_A(x') \,m(dx'|x) = m(A|x) = 1_A(x) = r(A|x), \end{align*} $$

where we used invariance of A.

Let us now prove the universal property in equation (10). Let $s:X\to S$ be a right-invariant Markov kernel. Define the kernel $\tilde s:X_{\mathrm {inv}}\to S$ simply by

for all $x\in X_{\mathrm {inv}}$ (equivalently, $x\in X$ ) and all measurable $B\subseteq S$ . To see that $\tilde s$ is measurable in x, consider a Borel-generating interval $(r,1]\subseteq [0,1]$ for some $0\le r < 1$ . We have to prove that the set

is measurable in $X_{\mathrm {inv}}$ , that is, as a subset of X, is measurable and invariant. We know that it is measurable as a subset of X, since s is a Markov kernel. Let us prove invariance. Using the fact that s is right-invariant (equation (6)), and that $\tilde s^*(B,r)$ is measurable as a subset of X,

$$ \begin{align*} s(B|x) &= \int_X s(B|x') \, m(dx'|x) \\ &= \int_{\tilde s^*(B,r)} s(B|x') \, m(dx'|x) + \int_{X\setminus \tilde s^*(B,r)} s(B|x') \, m(dx'|x). \end{align*} $$

Now let us use that m is deterministic, so that either we have $m(\tilde s^*(B,r)|x)=1$ or $m(X\setminus \tilde s^*(B,r)|x)=1$ . In the first case, we have that $s(B|x')> r$ on a set of measure $1$ ; therefore, $s(B|x)> r$ , i.e. $x\in \tilde s^*(B,r)$ . In the latter case, $s(B|x') \le r$ on a set of measure $1$ ; therefore, $s(B|x) \le r$ , i.e. $x\notin \tilde s^*(B,r)$ . Since m is deterministic, these are the only possibilities, and so we have that

$$ \begin{align*} m(\tilde s^*(B,r)|x) = \begin{cases} 1, & x \in \tilde s^*(B,r), \\ 0, & x\notin \tilde s^*(B,r). \end{cases} \end{align*} $$

This means precisely that $\tilde s^*(B,r)$ is invariant, and so $\tilde s$ is measurable. Therefore, $\tilde s$ is a well-defined Markov kernel $X_{\mathrm {inv}}\to S$ .

For uniqueness, note that $\tilde s$ is the only possible choice of kernel $X_{\mathrm {inv}}\to S$ making equation (10) commute: let $k:X_{\mathrm {inv}}\to S$ be another such kernel. Then, for all $x\in X$ and every measurable $B\subseteq X$ ,

$$ \begin{align*} k(B|x) = \int_{X_{\mathrm{inv}}} k(B|x') \,\delta(dx'|x) = \int_{X_{\mathrm{inv}}} k(B|x') \, r(dx'|x) = s(B|x). \end{align*} $$

Moreover, by construction, $\tilde s$ is deterministic if and only if s is.

3.3 Ergodic states

Intuitively, an ergodic measure is an invariant state of the system such that every conserved quantity almost surely takes on a single definite value. In particular, invariant deterministic observations $c : X \to R$ cannot be used to ‘decompose’ the state p into disjoint invariant subsystems of X, since $c \circ p$ being deterministic intuitively means that the state p is concentrated in a single fiber of c.

Our notion of ergodicity coincides with the traditional one in terms of invariant sets, by means of the following statement, which follows from the universal property of Markov colimits.

Proposition 3.10. Let X be a dynamical system with monoid M in a Markov category ${\mathsf {C}}$ , and suppose that the Markov colimit $X_{\mathrm {inv}}$ of X exists. An invariant state $p:I\to X$ is ergodic if and only if the composition with the universal cocone

is deterministic.

Proof. First, suppose that the composite $r\circ p$ is deterministic. Let $c:X\to R$ be an invariant deterministic observable. By definition of Markov colimit, c factors (uniquely) as a composite $\tilde {c}\circ r$ , where $\tilde {c}:X_{\mathrm {inv}}\to R$ is deterministic. Therefore,

$$ \begin{align*} c\circ p = \tilde{c}\circ r \circ p = \tilde{c}\circ (r\circ p) \end{align*} $$

is a composite of deterministic maps, and hence is deterministic. This is true for every invariant deterministic c, and so p is ergodic.

The converse follows by taking c in the definition of ergodicity to be $r:X\to X_{\mathrm {inv}}$ , which is deterministic and invariant.

Compare, for example, with the traditional characterizations [Reference Tao20, Theorem 3] and [Reference Viana and Oliveira21, Proposition 4.1.3].

To state Theorem 3.15, it remains to consider families of states which are almost surely ergodic. In Definition 3.8, we required $p : I \to X$ to be an invariant state, but the definition still makes sense for an invariant morphism $k : Y \to X$ (that is, with domain other than I). The development above generalizes immediately and, in particular, in ${\mathsf {Stoch}}$ , $k : Y \to X$ being ergodic simply says that each measure $p_y$ on X for $y \in Y$ is ergodic. However, we cannot simply derive the meaning of ‘almost surely ergodic’ in the manner described after Definition 2.5, since ergodicity is not a purely equational notion. Nevertheless, it is natural to adopt the following definition.

The following is a straightforward adaptation of Proposition 3.10.

Proposition 3.13. Let X be a dynamical system with monoid M in a Markov category ${\mathsf {C}}$ , and suppose that the Markov colimit $X_{\mathrm {inv}}$ of X exists. Let Y be an object of ${\mathsf {C}}$ with a state $q : I \to Y$ and a q-a.s. invariant morphism $k : Y \to X$ . Then k is q-a.s. ergodic if and only if the composition with the universal cocone

is q-a.s. deterministic.

Definition 3.12 is justified by what it means for ${\mathsf {Stoch}}$ .

3.4 Main statement

Let us now instantiate the theorem in ${\mathsf {Stoch}}$ , recalling that Markov colimits of deterministic dynamical systems always exist (Proposition 3.7).

Compare this with the traditional statements [Reference Viana and Oliveira21, Theorem 5.1.3], [Reference Tao20, Proposition 4]. Note also that the statement holds regardless of the cardinality or extra structure of the monoid M.

Now that all the necessary categorical setting is in place, the proof is very concise. Before looking at it, let us explain the intuition behind it a little. Since the Markov colimit exists (for example, the invariant $\sigma $ -algebra), we have a ‘weak quotient’ map $r:X\to X_{\mathrm {inv}}$ which intuitively forgets the distinction between points that lie on the same orbit. We then construct a disintegration $r^+_p:X_{\mathrm {inv}}\to X$ . Intuitively, this kernel maps each orbit back to a measure on X which is:

• • supported on the given orbit (i.e. $r^+$ is a stochastic section of r almost surely);

• • uniform within the given orbit (i.e. $r^+$ is almost surely ergodic).

This disintegration then expresses p as a mixture of ergodic measures.

Let us now look at the proof.

Proof of Theorem 3.15

Let $p:I\to X$ be an invariant state. Consider the map ${r:X\to X_{\mathrm {inv}}}$ , and form the disintegration $r^+_p:X_{\mathrm {inv}}\to X$ .

By marginalizing the equation above over $X_{\mathrm {inv}}$ , we see that $p=r^+_p \circ r\circ p$ , i.e. we are decomposing p into the composition of $r\circ p:I\to X_{\mathrm {inv}}$ followed by $r^+_p$ . Now denote $r\circ p$ by q.

Let us show that $r^+_p$ is q-a.s. ergodic. To see that $r^+_p$ is q-a.s. left-invariant, note that for all $m\in M$ ,

using, in order, the definition of $r^+_p$ as a disintegration, right-invariance of r, determinism of m, left-invariance of p, and again the definition of $r^+_p$ as a disintegration.

By Proposition 3.13, all that remains to be shown to prove q-almost sure ergodicity is that $r\circ r^+_p$ is q-a.s. deterministic. To see this, note that since r is deterministic, we can apply Proposition 2.7 with r in place of f. The proposition tells us that $r\circ r^+_p$ is q-a.s. equal to the identity, which is deterministic.

As one can see, at this level, all the measure-theoretic and analytic details are taken care of by the formalism, and one can focus on the conceptual reasoning.