Lemma [efr-X0VA]

With \mathcal {C}, \mathsf {Borel} \to \mathcal {C} as above, let A be (the image of) a standard Borel space, and consider the map \lambda : (BT(A)^\omega )^\omega \to A given by sampling two natural numbers according to c^\omega : I \to 2^\omega \setminus 0 \to \omega and indexing with them, then using the canonical sampling map. There exists a map BT(A)^{\omega \times \omega } \to BT(A)^\omega which preserves the sampling map. Moreover this map also preserves the map into \Delta (A).

Proof

Let F: BT(A)^{\omega \times \omega } \times (2^\omega \setminus 0)^2 \times (2^\omega )^\omega \to A be a parametrization of the sampling map. Specifically, the first two bitstreams select the indexes (i,j) into the matrix of finitary distributions, after which the ith of the remaining bitstreams is used to choose a branch.

Let us adopt the convention that the first index chooses the column and the second index chooses the row when describing the manipulations below.

Given a sequence (d_{ij}) \in BT(A)^{\omega \times \omega }, construct r_1(d)_{ij} as follows:

  1. r_1(d)_{1j} = g(d_{11}, g(d_{12}, d_{21}))
  2. r_1(d)_{2j} = g(d_{1(j+2)},d_{2(j+1)})
  3. r_1(d)_{ij} = d_ij for i \geq 3

First note that clearly r_1(d) has the same image in \Delta (A) as d—the first column of r_1(d) has the same sum as the three most probably indices of d, and the second column of r_1(d) has the same sum as the remainder of the first two columns of d. Also note that there exists a permutation \rho _1 : (2^\omega \setminus 0 )^2 \times (2^\omega )^omega \to (2^\omega \setminus 0)^2 \times (2^\omega )^omega so that F(r_1(d),\rho _1(b)) = F(d,b).

\rho _1(b_1,b_2,(b_3^i)) can be chosen as follows: it does not modify b_3^i for i>2 (since these bits are only used for choices in the first column). Omitting therefore these strings from the notation below, we define \rho _1(1.c,1.r,s^1,s^2) = (1.c,r,1.s^1,s^2) \rho _1(1.c,01.r,s^1,s^2) = (1.c, r,01.s^1,s^2) \rho _1(01.c,1.r,s^1,s^2) = (1.c,r,10.s^2, s^1) \rho _1(1.c, 00.r, s^1,s^2) = (01.c, r, s^2, 1.s^1) \rho _1(01.c, 0.r, s^1,s^2) = (01.c, r, s^1, 0.s^2) \rho _1(00.c,r,s^1,s^2) = (00.c,r,s^1,s^2)

It is straightforward to verify that \rho _1 is well-defined, that F(r_1(d),\rho _1(b)) = F(d,b) as required. Moreover we see that every finite projection of the output of \rho _1 factors over some finite prefix of the input, and that the resulting maps 2^N \to 2^M carry the uniform distribution to the uniform distribution. This implies that \rho _1 c^\omega = c^\omega .

r_1 "flattens" the first column of d. Now we can apply r_1 again to the remaining columns to flatten the second column, and similarly apply \rho _1 ignoring the first bit of c and s^1 to obtain a corresponding permutation. Let r_N, \rho _N be the map an permutation that flatten the first N columns. Note that by construction each output bit of r_N is eventually stable for high N, and the same is true for \rho _N. Let r_\infty , \rho _\infty be the limiting maps.

Then when the first 1 in the part of \rho _\infty (b) which selects the i appears before index N, F(r_\infty (d),\rho _\infty (b)) depends only on the first N rows, hence is equal to F(r_N(d),\rho _\infty (b)), which is then equal to F(d,b). Since \rho _\infty is the limit of permutations, it preserves the uniform measure, and so the composite F(d,c^\omega ) = F(r_\infty (d), \rho _\infty (c^\omega )) = F(r_\infty (d), c^\omega ).

This proves that r_\infty preserves the sampling map. But clearly r_\infty factors over the inclusion of BT(A)^\omega \hookrightarrow BT(A)^{\omega \times \omega } as the "flat" sequences of sequences, and equally clearly this inclusion preserves the sampling map. This concludes the proof.

Context

The universal property of \mathsf {BorelStoch} [efr-D09F]

We are now ready to prove Theorem [efr-TVLB]. The basic point is that any Markov kernel between standard Borel spaces can be written as the composite of a measurable function f: A \times 2^\omega \to B with the uniform measure on c^\omega : I \to 2^\omega . By Chen's theorem, the image of f is uniquely determined, and by Proposition [efr-V3JG], so is the image of c^\omega . Hence there is at most one such functor---what we need to prove is that the above is well-defined (that is, choosing different factorizations gives the same kernel in the image) and actually forms a Markov functor.

The strategy for the proof is as follows:

  1. Observe that for any \mathcal {C}, there is an essentially unique functor \mathsf {Borel} \to \mathcal {C} (which lands in \mathcal {C}_\mathrm {det}), by Chen's theorem.
  2. Prove that there is a (Markov) extension to the category of discrete kernels, \mathsf {Borel}_{\bar {\Delta }}.
  3. Finally prove that there is a further Markov extension to \mathsf {BorelStoch}

We have essentially already given the proof of the first step in the introduction, but let us state it here for completeness.

Proposition [efr-AFCK]

Let \mathcal {C} be a Markov category which is countably extensive, Boolean, coinflip, and admits countable Kolmogorov products. Then there is an essentially unique (strong) Markov functor i: \mathsf {Borel} \to \mathcal {C} which preserves pullbacks along monomorphisms and countable Kolmogorov products.

Proof

Since \mathsf {Borel} is Cartesian, any such Markov functor must factor over \mathcal {C}_\mathrm {det}. \mathcal {C}_\mathrm {det} has countable limits (it has countable products by Lemma [efr-OH6B] and pullbacks along monomorphisms, which along with finite products suffices to build equalizers) and is countably extensive and Boolean by assumption. The assumptions on i are equivalent to the factorization \mathsf {Borel} \to \mathcal {C}_\mathrm {det} preserving countable limits and countable coproducts. Hence this uniqueness is exactly Reference [chen-universal-stdborel-2019] theorem 1.1

To make our results slightly more broadly applicable, since there aren't many Boolean categories, we will instead take a suitable Markov functor \mathsf {Borel} \to \mathcal {C} as the input, and prove that given such, there is a unique extension of the above kind. In the below, we will generally abuse notation and identify a standard Borel space with its image under this functor.

Let's now see the details of part 2. We begin with the following lemma, which is what allows us to use infinitary sampling without the iterability assumption.

Lemma [efr-K4NK]

Let \mathcal {C} be an extensive coinflip Markov category with countable Kolmogorov products, and let \mathsf {Borel} \to \mathcal {C} be a strong Markov functor which preserves pullbacks along coproduct inclusions and countable Kolmogorov products. Let V_1 \subseteq 2^\omega be the subobject consisting of those sequences containing infinitely many ones. Then the map c^\omega : I \to 2^\omega factors over V_1. In particular, it factors over the inclusion 1 . 2^\omega \sqcup 01.2^\omega \sqcup \cdots \hookrightarrow 2^\omega of the subobject of sequences with at least one 1.

Proof

Let r_1: 2^\omega \to 2 be the indicator of the subset consisting of those streams which have only finitely many 1s. Observe that for any finite N, r_1 factors over the second coordinate of the decomposition 2^\omega \to 2^N \times 2^\omega .

As a result, if we form the joint I \to 2^\omega \otimes 2 given by sampling the uniform distribution and computing r_1, the second coordinate is independent of any finite prefix of the first. Hence, by the abstract Kolmogorov zero-one law (Reference [rischel-fritz-infinite-products], theorem 5.3), the composite r_1 c^\omega : I \to I+I is deterministic.

Hence it classifies some subterminal object q. By symmetry, r_0 c^\omega is the indicator of q as well, where r_0 is the indicator of sequences with only finite many 0s. But these two subterminal objects must be disjoint, hence they must both be empty. (This step uses the fact that pullbacks along monomorphisms in \mathcal {C}_\mathrm {det} are still pullbacks in \mathcal {C})

So r_0c^\omega , r_1c^\omega are both equal to 0 : I \to 2. It follows that c^\omega factors over the subobject 2^\omega \setminus \{0\}^\omega \hookrightarrow 2^\omega (since any sequence with finitely many zeroes certainly has at least one 1).

Thus we can define a countable-arity operator M_A: A^\omega \to A in any of these categories by drawing a sample from c^\omega \in 2^\omega and projecting onto the coordinate of the first 1 (which necessarily exists).

For any standard Borel space A, let BT(A) denote the (again standard Borel) space of balanced, finite binary trees with leaves labeled by A. This can be identified with the coproduct \sum _{n \in \mathbb {N}} A^{2^n}. Let g : BT(A) \times BT(A) \to BT(A) glue two trees together, duplicating the shallower one so that they have the same depth. In \mathcal {C}, there is a unique kernel BT(A) \to A which carries this operation to the midpoint operation in \mathcal {C}. Note that this can be factored as a map BT(A) \times 2^\omega \to A which uses the first n bits to choose a branch, composed with the uniform distribution.

Given anything like (BT(A)^{\omega \times \omega })^{\omega }, we can build a well-defined map into A by composing these sampling homomorphisms. This is what we mean below by a sentence like "the sampling homomorphism BT(A)^{\omega ^N} \to A. Note that this is well-defined in any extensive, coinflip \mathcal {C} with countable Kolmogorov products equipped with \mathsf {Borel} \to \mathcal {C}.

Note that we have not proven that M_A is uniquely determined by the coinductive definition M_A(a_1, \dots ) = m(a_1, M(a_2, \dots )), merely constructed a canonical such operation. We have not been able to prove uniqueness in general (which would imply that any countably distributive, Boolean, countably complete coinflip Markov category is iterable), but neither do we know of a counterexample.

Lemma [efr-X0VA]

With \mathcal {C}, \mathsf {Borel} \to \mathcal {C} as above, let A be (the image of) a standard Borel space, and consider the map \lambda : (BT(A)^\omega )^\omega \to A given by sampling two natural numbers according to c^\omega : I \to 2^\omega \setminus 0 \to \omega and indexing with them, then using the canonical sampling map. There exists a map BT(A)^{\omega \times \omega } \to BT(A)^\omega which preserves the sampling map. Moreover this map also preserves the map into \Delta (A).

Proof

Let F: BT(A)^{\omega \times \omega } \times (2^\omega \setminus 0)^2 \times (2^\omega )^\omega \to A be a parametrization of the sampling map. Specifically, the first two bitstreams select the indexes (i,j) into the matrix of finitary distributions, after which the ith of the remaining bitstreams is used to choose a branch.

Let us adopt the convention that the first index chooses the column and the second index chooses the row when describing the manipulations below.

Given a sequence (d_{ij}) \in BT(A)^{\omega \times \omega }, construct r_1(d)_{ij} as follows:

  1. r_1(d)_{1j} = g(d_{11}, g(d_{12}, d_{21}))
  2. r_1(d)_{2j} = g(d_{1(j+2)},d_{2(j+1)})
  3. r_1(d)_{ij} = d_ij for i \geq 3

First note that clearly r_1(d) has the same image in \Delta (A) as d—the first column of r_1(d) has the same sum as the three most probably indices of d, and the second column of r_1(d) has the same sum as the remainder of the first two columns of d. Also note that there exists a permutation \rho _1 : (2^\omega \setminus 0 )^2 \times (2^\omega )^omega \to (2^\omega \setminus 0)^2 \times (2^\omega )^omega so that F(r_1(d),\rho _1(b)) = F(d,b).

\rho _1(b_1,b_2,(b_3^i)) can be chosen as follows: it does not modify b_3^i for i>2 (since these bits are only used for choices in the first column). Omitting therefore these strings from the notation below, we define \rho _1(1.c,1.r,s^1,s^2) = (1.c,r,1.s^1,s^2) \rho _1(1.c,01.r,s^1,s^2) = (1.c, r,01.s^1,s^2) \rho _1(01.c,1.r,s^1,s^2) = (1.c,r,10.s^2, s^1) \rho _1(1.c, 00.r, s^1,s^2) = (01.c, r, s^2, 1.s^1) \rho _1(01.c, 0.r, s^1,s^2) = (01.c, r, s^1, 0.s^2) \rho _1(00.c,r,s^1,s^2) = (00.c,r,s^1,s^2)

It is straightforward to verify that \rho _1 is well-defined, that F(r_1(d),\rho _1(b)) = F(d,b) as required. Moreover we see that every finite projection of the output of \rho _1 factors over some finite prefix of the input, and that the resulting maps 2^N \to 2^M carry the uniform distribution to the uniform distribution. This implies that \rho _1 c^\omega = c^\omega .

r_1 "flattens" the first column of d. Now we can apply r_1 again to the remaining columns to flatten the second column, and similarly apply \rho _1 ignoring the first bit of c and s^1 to obtain a corresponding permutation. Let r_N, \rho _N be the map an permutation that flatten the first N columns. Note that by construction each output bit of r_N is eventually stable for high N, and the same is true for \rho _N. Let r_\infty , \rho _\infty be the limiting maps.

Then when the first 1 in the part of \rho _\infty (b) which selects the i appears before index N, F(r_\infty (d),\rho _\infty (b)) depends only on the first N rows, hence is equal to F(r_N(d),\rho _\infty (b)), which is then equal to F(d,b). Since \rho _\infty is the limit of permutations, it preserves the uniform measure, and so the composite F(d,c^\omega ) = F(r_\infty (d), \rho _\infty (c^\omega )) = F(r_\infty (d), c^\omega ).

This proves that r_\infty preserves the sampling map. But clearly r_\infty factors over the inclusion of BT(A)^\omega \hookrightarrow BT(A)^{\omega \times \omega } as the "flat" sequences of sequences, and equally clearly this inclusion preserves the sampling map. This concludes the proof.

Lemma [efr-HYFI]

Let \mathcal {C} be an extensive Markov category with countable Kolmogorov products. Let \mathsf {Borel} \to \mathcal {C} be a Markov functor which preserves countable coproducts, countable Kolmogorov products and pullbacks along coproduct inclusions. Then:

  1. For every n, the iterated sampling operator BT(A)^{\omega ^n} \to A factors over the map BT(A)^{\omega ^n} \to \bar {\Delta }(A).
  2. The composite map \coprod _n BT(A)^{\omega ^n} \to \Delta (A) is a split epimorphism, and thus the factorization is unique, giving a well-defined sampling map s_A: \Delta (A) \to A for every standard Borel space A.
  3. This sampling map is a \omega -midpoint homomorphism, in the sense that s_A(\sum _i 1/2^i \mu _i) = M_A(s_A \mu _1, s_A \mu _2, \dots ).
  4. These maps assemble into a functor \mathsf {Borel}_{\bar {\Delta }} \to \mathcal {C} which extends the unique \mathsf {Borel} \to \mathcal {C}.

Proof

By Lemma [efr-X0VA], we see that we can immediately flatten any nested sequence in BT(A)^{\omega ^n} into a sequence of dyadic binary trees in BT(A)^\omega , without altering either the sampling map or the represented distribution in \bar {\Delta (A)}. Hence it suffices to prove that the sampling map BT(A)^\omega \to A factors over \bar {\Delta (A)}.

It is clear that the sum map BT(A)^\omega \to \bar {\Delta }(A) is surjective. We will begin by choosing a particular splitting of this map, assigning to each countably supported measure a "normal form" in BT(A)^\omega

Fix an arbitrary total ordering on A. If A is countable there is no difficulty doing this, if A = 2^\omega , we may use the lexical ordering.

Given a finitary distribution \mu , we compute its normal form as follows:

  1. Let N_0 be the smallest natural so that there exists a dyadic distribution \nu _0 = \sum _i \frac {k_i}{2^N} a_i so that \frac {1}{2}\nu _0 < \mu - that is, for every element of A, the probability under \frac {1}{2}\nu _0 is strictly less than the probability under \mu .
  2. Let \nu _0 be a dyadic distribution as above, choosing the lowest possible a_i according to the chosen ordering. Represent \nu _0 as a balanced binary tree of minimal depth, with the leaves increasing left to right.
  3. Repeat these steps with \mu - \frac {1}{2}\nu _0 to construct \nu _1, \nu _2, \dots .

It is clear that this defines a measurable map \Delta (A) \to BT(A)^\omega , and that this is a section of the map \sum _i 1/2^i \nu _i in the other direction.

  1. Let S: BT(A)^\omega \times (2^{\omega } \setminus 0) \times (2^\omega )^\omega \to A be the sampling map, which uses the first bitstream to choose the index i from the sequence, then the ith one of the remaining streams to sample from the given binary tree.
  2. Note that by construction, if \nu _1 is the first element in the normal form of \mu , and \lambda _i is another sequence of binary trees so that \sum _i 1/2^i \lambda _i is equal to \mu , then there exists some finite prefix so that 1/2 \nu _0 < \sum _{i=0}^N 1/2^i \lambda _i. Then there exists some rearrangement of this prefix \lambda _i' so that \lambda _1' = \nu _1 (and \lambda '_i = \lambda _i when i>N). Let \mathrm {nm}_k: BT(A)^\omega \to BT(A)^\omega be the map which puts the first k elements into the normal form like this. Note that for each k there exists some permutation \sigma _k : BT(A)^\omega \times (2^{\omega } \setminus 0) \times (2^\omega )^\omega \to (2^{\omega } \setminus 0) \times (2^\omega )^\omega which, for each possible sequence, witnesses this rearrangement (in the same way as Lemma [efr-X0VA]).
  3. By construction the nth coordinate of \mathrm {nm}_k(a) is equal for all k > n, and so there is a well-defined limiting map \mathrm {nm}_\infty : BT(A)^\omega \to BT(A)^\omega , which (by construction) carries a sequence to its normal form.
  4. For \sigma _k, similarly note that the first n bits (deciding the index into the sequence) are fixed for k > n, and the same is true for the n first streams used to sample from the given binary trees.
  5. Let \mathrm {nm}_\infty and \sigma _\infty be the limiting maps.

Now observe that F(a,b) = F(\mathrm {nm}_\infty (a),\sigma _\infty (a,b)), and that \sigma _\infty (a,b) for each a preseves the uniform measure. Hence just as before, this proves that the sampling map commutes with taking the normal form, as we wanted.

Observe that (for any monad), the Kleisli category is presented by adding morphisms s_A: TA \to A for each A, subject to the equations s_A\eta _A = 1_A and s_A s_{TA} = s_A \mu _A. We have just constructed the s_A, so we now have to prove that they satisfy these equations. Unitality is clear. The multiplicativity condition follows by observing that any finitary distribution on \Delta (A) can be decomposed as an iterated sum coming from \Delta (A)^{\omega ^N}, at which point this reduces to the mentioned \omega -midpoint homomorphism property.

We are now ready for the final step, to construct the extension of the functor \mathsf {Borel}_{\bar {\Delta }} \to \mathcal {C} over \mathsf {Borel}_{\bar {\Delta }} \hookrightarrow \mathsf {BorelStoch}

Lemma [efr-JK8U]

Let \phi : A \to (2^\omega )^k be a kernel in \mathsf {BorelStoch}, and let \vee ^k : (2^\omega )^k \to 2^k be the map which is 1 in each coordinate if the corresponding sequence contains at least one 1 (and zero else). Let \mathsf {Borel} \to \mathcal {C} be as above, and let F: \mathsf {Borel}_{\bar {\Delta }} \to \mathcal {C} be the unique extensions of Lemma [efr-HYFI]. Write \bar {F}(\phi ) for the unique map F(A) \to F((2^\omega )^k) given as the limit of F applied to the finite truncations. Then F(\vee ^k)\bar {F}(\phi ) = F(\vee ^k \phi )

Proof

We proceed by induction on k, the case k=0 being trivial.

First, consider a kernel \alpha : A \to (2^\omega )^k which, on the first N bits in the first coordinate, is concentrated on a given string a = a_1,\dots a_N which contains at least one 1. This kernel factors over the inclusion of this component: (2^\omega )^k = \{a\} \otimes 2^{\{N+1, \dots \}} \otimes (2^\omega )^{k-1} \sqcup (2^N \setminus \{a\}) \otimes 2^{\{N+1, \dots \}} \otimes (2^\omega )^{k-1}

This factorization is preserved by F (which preserves coproducts). Note that \vee ^k, when restricted to this summand, factors over the projection (2^\omega )^k \to (2^\omega )^{k-1}. So we can write F(\vee ^k)\bar {F}(\alpha ) = F((1,\vee ^{k-1}) \pi )\bar {F}(\alpha ). It is clear that F(\pi )\bar {F}(\alpha ) = \bar {F}(\pi \alpha ), and so by induction this means F(\vee ^k)\bar {F}(\alpha ) = F(\vee ^k \alpha ).

By an analogous argument (without passing through the finite truncation), if \alpha is concentrated on the string 0 \in 2^\omega in the first coordinate, again F(\vee ^k)\bar {F}(\alpha ) = F(\vee ^k \alpha )

Now consider the generic kernel \phi of the lemma. Let A = A_0 \sqcup A_1, where A_0 consists of those a for which the probability that the first coordinate is zero is \geq 1/2, and A_1 is the complement, consisting of those for which at least one 1 has probability >1/2. Note that by \sigma -continuity, there exists for each a \in A_1 some N_a so that there is a probability \geq 1/2 of an 1 in the first N_a coordinates. Note that the least such N_a is a measurable function of a, and so A_1 decomposes into a sum A_1 = A_1^1 \sqcup A_1^2 \dots , where on A_1^N there is a \geq 1/2 probability of an 1 in the first N coordinates.

Now let \mu _1 be the kernel defined as follows:

  1. On A_0, it is deterministically 0 in the first coordinate, and given by the conditional distribution given this in the last k coordinates.
  2. For a \in A_1^N, choose some distribution \nu on 2^N so that \nu / 2 is less than the marginals of \phi , and so that \nu is concentrated away from 0 (this is possible by construction of A_1^N). Then for each b \in 2^N, let \xi _b be the measure which is concentrated on that bitstring on the first N bits, and given by the conditional distribution according to \phi everywhere else. Let \mu _1(a) = \sum _{b\in 2^N} \nu (b) \xi _b

Observe that by construction, \mu _{1/2} \leq \phi . Now we can continue the recursion, defining \mu _2, \mu _3, \dots , and we must necessarily have \sum _i 1/2^i \mu _i = \phi . This sum must be preserved by \bar {F} (where the meaning of this sum in \mathcal {C} is given by the canonical sampling morphism X^\omega \to X, or equivalently by the dual I \to \omega ). Therefore we have F(\vee ^k)\bar {F}(\phi ) = F(\vee ^k)(\sum _i 1/2^i \bar {F}(\mu _i)) = \sum _i 1/2^i F(\vee ^k) \bar {F}(\mu _i) = \sum _i 1/2^i F(\vee ^k \mu _i) = F(\vee ^k \phi ), finishing the proof.

Lemma [efr-D3QE]

Let \mathsf {Borel} \to \mathcal {C} be as above. Then it admits a unique extension to \mathsf {BorelStoch} \to \mathcal {C}.

Proof

Using Lemma [efr-VH33], there is a unique extension F: \mathsf {Borel}_{\bar {\Delta }} \to \mathcal {C}. There is a faithful (identity on objects) functor \mathsf {Borel}_{\bar {\Delta }} \to \mathsf {BorelStoch} - the only case where this is not full is \operatorname {\mathrm {Hom}}(A,2^\omega ).

It is apparent that we must extend this functor by defining \bar {F}(\phi : A \to 2^\omega ) = \lim _n F(\pi _{2^n}\phi ), using the universal property of F(2^\omega ) = F(2)^\omega . It is apparent that this preserves independent pairings—the only question is whether this extension is actually functorial. By the limit property it suffices to prove that it is functorial for any composable pair A \xrightarrow {\phi } 2^\omega \xrightarrow {\psi } K with K finite.

Let a function f: 2^\omega \to K be good if \bar {F}(\phi ) ; F(f) = F(\phi ; f) for all kernels \phi : A \to 2^\omega (for all A). Let an algebra of sets \mathbb {A} \subseteq \mathcal {B}(2^\omega ) (i.e a collection of subsets stable under finite unions and complements) be called good if every \mathbb {A}-measurable map 2^\omega \to K to a finite set is good. Now we claim:

  1. The class \mathbb {A}_0 of sets of the form V \times 2^\omega for V \subseteq 2^N, N finite, is a good algebra.
  2. If \mathbb {A} is a good algebra, let \mathbb {A}^+ be the smallest algebra containing all countable unions of sets in \mathbb {A}. Then \mathbb {A}^+ is again a good algebra.
  3. Any directed union of good algebras \mathbb {A}_0 \subseteq \mathbb {A}_1 \dots \subseteq A_\alpha \subseteq is again a good algebra.

First note that, by Zorn's lemma, this straightforwardly implies the full Borel \sigma -algebra is a good algebra, which in turn concludes the proof.

Point 3 holds, since both being an algebra and being good are finitary properties (any map to a finite set which is measurable for the union must be measurable at some finite stage). Point 1 is a straightforward consequence of the fact that the projections 2^\omega \to 2^N are good by construction. So we are left with point 2.

Let \mathbb {A} be a good algebra. Let us identify sets by their indicators 2^\omega \to 2. Then we can write any set in \mathbb {A}^+ as g(\vee (f_1^i(-)), \vee f_2^i(-), \dots , \vee f_k^i(-)), where g: 2^k \to 2 is some function, \vee : 2^\omega \to 2 is the indicator of the sequences with at least one 1, and f_j^i, 0 \leq j \leq k, 0 \leq i < \infty are a bunch of \mathbb {A}-measurable functions.

By assumption the pairing of all the f's, 2^\omega \to (2^\omega )^k is good, and so it suffices to show that the mapping (\vee )^k : (2^\omega )^k \to 2^k is good. By induction we may suppose this holds for (\vee )^{k-1}, since it is trivial for k=0.

Now let \phi : A \to (2^\omega )^k be some kernel. Write A = A_0 + A_1, where A_0 is the subset where the probability of only zeroes in the first stream is at least 1/2, and A_1 is the complement, where the probability of at least one 1 in the first stream is >1/2. Observe that by \sigma -continuity, for each a there must be some N so that the probability of at least one 1 in the first N elements of the first stream is at least 1/2. Decompose A_1 into A_1^1 + A_1^2 + \cdots , where for a \in A_1^N there is at least a 1/2 probability of the first 1 being before N. Let \psi _1 : A \to (2^\omega )^k be a kernel which on A_0 is given by (0, \otimes \mu _{2\dots k}) where \mu _{2,\dots k} is the kernel giving the conditional distribution of the remaining streams if the first stream is 0. On A_1^N, it is given by a linear combination \sum _{s \in 2^N \setminus 0} \delta _{s} \otimes \mu _s, where \mu _s is the conditional distribution of the rest of the stream and the remaining streams - we choose this linear combination so that 1/2 of it is \leq the actual probability of each of those prefixes.

Thus we obtain a decomposition of \phi as \sum _i \frac {1}{2^i} \phi _i where for each \phi _i, the distribution on the first coordinate is either concentrated on 0 \in 2^\omega , or concentrated away from 0 on some finite prefix. Each of these satisfy F(\vee ^k)\bar {F}(\phi _i) = F(\vee ^k \phi _i). Hence, since F(\vee ^k) must preserve the infinite linear combination, \vee ^k must be good as desired.

Now let f: 2^\omega \to B be a kernel, and let \phi : A \to 2^\omega again be a kernel. We can factor f as a measurable map \bar {f} : 2^\omega \times 2^\omega \to B, composed with the uniform c^\omega : I \to 2^\omega . By the above we have F(f) = F(\bar {f})\circ (F(c^\omega ) \otimes 2^\omega ). By monoidality, it follows that \bar {F}(f)\bar {F}(\phi ) = F(f\phi ) as desired.

Now Theorem [efr-TVLB] follows trivially from Proposition [efr-AFCK]

Instead of studying Markov categories, one could study probability monads. The relevant question would then have been to give a universal property for the Giry monad. Our theorem implies this immediately:

Corollary

Let T be a bicommutative, affine monad on \mathsf {Borel} so that T(2) contains a coinflip, T preserves the limits \lim _{F \subset J \mathrm { F finite}} \prod _{i \in F} X_i and pullbacks along coproduct inclusions, and the induced midpoint algebras on TX are all iterable. Then there is a unique monoidal monad homomorphism G \to T, where G is the Giry monad.

Proof

Subject to these assumptions, \mathsf {Borel}_T is a Markov category which satisfies the hypotheses of Theorem [efr-TVLB]. Hence there is a strong monoidal, identity-on-objects functor \mathsf {BorelStoch} = \mathsf {Borel}_G \to \mathsf {Borel}_T. Such functors correspond bijectively to morphisms of monads G \to T (see eg Reference [barr-wells-triples-2005], Theorem 3.6.3), finishing the proof.

This settles an unpublished

Backlinks

Lemma [efr-HYFI]

Let \mathcal {C} be an extensive Markov category with countable Kolmogorov products. Let \mathsf {Borel} \to \mathcal {C} be a Markov functor which preserves countable coproducts, countable Kolmogorov products and pullbacks along coproduct inclusions. Then:

  1. For every n, the iterated sampling operator BT(A)^{\omega ^n} \to A factors over the map BT(A)^{\omega ^n} \to \bar {\Delta }(A).
  2. The composite map \coprod _n BT(A)^{\omega ^n} \to \Delta (A) is a split epimorphism, and thus the factorization is unique, giving a well-defined sampling map s_A: \Delta (A) \to A for every standard Borel space A.
  3. This sampling map is a \omega -midpoint homomorphism, in the sense that s_A(\sum _i 1/2^i \mu _i) = M_A(s_A \mu _1, s_A \mu _2, \dots ).
  4. These maps assemble into a functor \mathsf {Borel}_{\bar {\Delta }} \to \mathcal {C} which extends the unique \mathsf {Borel} \to \mathcal {C}.

Proof

By Lemma [efr-X0VA], we see that we can immediately flatten any nested sequence in BT(A)^{\omega ^n} into a sequence of dyadic binary trees in BT(A)^\omega , without altering either the sampling map or the represented distribution in \bar {\Delta (A)}. Hence it suffices to prove that the sampling map BT(A)^\omega \to A factors over \bar {\Delta (A)}.

It is clear that the sum map BT(A)^\omega \to \bar {\Delta }(A) is surjective. We will begin by choosing a particular splitting of this map, assigning to each countably supported measure a "normal form" in BT(A)^\omega

Fix an arbitrary total ordering on A. If A is countable there is no difficulty doing this, if A = 2^\omega , we may use the lexical ordering.

Given a finitary distribution \mu , we compute its normal form as follows:

  1. Let N_0 be the smallest natural so that there exists a dyadic distribution \nu _0 = \sum _i \frac {k_i}{2^N} a_i so that \frac {1}{2}\nu _0 < \mu - that is, for every element of A, the probability under \frac {1}{2}\nu _0 is strictly less than the probability under \mu .
  2. Let \nu _0 be a dyadic distribution as above, choosing the lowest possible a_i according to the chosen ordering. Represent \nu _0 as a balanced binary tree of minimal depth, with the leaves increasing left to right.
  3. Repeat these steps with \mu - \frac {1}{2}\nu _0 to construct \nu _1, \nu _2, \dots .

It is clear that this defines a measurable map \Delta (A) \to BT(A)^\omega , and that this is a section of the map \sum _i 1/2^i \nu _i in the other direction.

  1. Let S: BT(A)^\omega \times (2^{\omega } \setminus 0) \times (2^\omega )^\omega \to A be the sampling map, which uses the first bitstream to choose the index i from the sequence, then the ith one of the remaining streams to sample from the given binary tree.
  2. Note that by construction, if \nu _1 is the first element in the normal form of \mu , and \lambda _i is another sequence of binary trees so that \sum _i 1/2^i \lambda _i is equal to \mu , then there exists some finite prefix so that 1/2 \nu _0 < \sum _{i=0}^N 1/2^i \lambda _i. Then there exists some rearrangement of this prefix \lambda _i' so that \lambda _1' = \nu _1 (and \lambda '_i = \lambda _i when i>N). Let \mathrm {nm}_k: BT(A)^\omega \to BT(A)^\omega be the map which puts the first k elements into the normal form like this. Note that for each k there exists some permutation \sigma _k : BT(A)^\omega \times (2^{\omega } \setminus 0) \times (2^\omega )^\omega \to (2^{\omega } \setminus 0) \times (2^\omega )^\omega which, for each possible sequence, witnesses this rearrangement (in the same way as Lemma [efr-X0VA]).
  3. By construction the nth coordinate of \mathrm {nm}_k(a) is equal for all k > n, and so there is a well-defined limiting map \mathrm {nm}_\infty : BT(A)^\omega \to BT(A)^\omega , which (by construction) carries a sequence to its normal form.
  4. For \sigma _k, similarly note that the first n bits (deciding the index into the sequence) are fixed for k > n, and the same is true for the n first streams used to sample from the given binary trees.
  5. Let \mathrm {nm}_\infty and \sigma _\infty be the limiting maps.

Now observe that F(a,b) = F(\mathrm {nm}_\infty (a),\sigma _\infty (a,b)), and that \sigma _\infty (a,b) for each a preseves the uniform measure. Hence just as before, this proves that the sampling map commutes with taking the normal form, as we wanted.

Observe that (for any monad), the Kleisli category is presented by adding morphisms s_A: TA \to A for each A, subject to the equations s_A\eta _A = 1_A and s_A s_{TA} = s_A \mu _A. We have just constructed the s_A, so we now have to prove that they satisfy these equations. Unitality is clear. The multiplicativity condition follows by observing that any finitary distribution on \Delta (A) can be decomposed as an iterated sum coming from \Delta (A)^{\omega ^N}, at which point this reduces to the mentioned \omega -midpoint homomorphism property.