Lemma [efr-VH33]

Let F: \mathsf {Borel} \to \mathcal {C} be .. Then there is a unique Markov extension \bar {F} over \mathsf {Borel} \to \mathsf {Borel}_{\bar {\Delta }}.

Proof

First, note that the Kleisli category \mathsf {Borel}_{\bar {\Delta }} is freely generated by adding morphisms s_A: \bar {\Delta } A \to A for each A, subject to the equations that these are natural in A, unital for the monad structure, and satisfy s_A\mu _A = s_As_{\bar {\Delta }}A (where \mu is the multiplication of the monad).

Let \Delta _omega (\omega ) \to \omega be the map in \mathcal {C} constructed above. We first prove that the resulting F(A)^\omega \times \bar {\Delta }(\omega ) \to F(A) factors over F(\bar {\Delta } A). This factorization will be our chosen \bar {F}(s_A).

Note that the map F(A)^\omega \times \bar {\Delta }(\omega ) \to F(\bar {\Delta } A) is F applied to a map A^\omega \times \bar {\Delta } \omega \to \bar {\Delta } A. This map splits. As above, to show the sampling map factors over this, it suffices to describe the normal form implied by the splitting and show that normalizing first does not alter the sampling map. It is easier here to simply describe the normal form:

  1. If any a \in A occurs multiple times with nonzero \epsilon _i, combine all of them (replacing those \epsilon _i with zero and adding them to the coefficient of the first occurence of that a)
  2. Fix some arbitrary a^* \in A and set a_i = a^* whenever \epsilon _i = 0.

    3. Permute both the coefficients and the a_i, ordering first by decreasing \epsilon _i, then by some arbitrary total order on A (note that the set of distinct a_i with the same coefficient must be finite, so this can be done for any total order).

It's clear that the normal forms are in bijection with \bar {\Delta } A. Just as above, we can prove that sampling and normalization followed by sampling agree by identifying fifty percept of the probability mass of the normalized thing, then fifty percent of the rest, etc.

As we have shown above, the map F(X)^\omega \times \bar {\Delta }(\omega ) \to F(X) always factors uniquely over F(\bar {\Delta } X). We take this factorization to be \bar {F}(s_X).

It's clear that this is unital. We now pass to the multiplicativity. Note that the map F(X)^\omega \times \bar {\Delta }(\omega ) \to F(X) is natural for any map F(X) \to F(Y) \in \mathcal {C}. Consider this diagram:

The object is to show that the bottom square commutes. It suffices to consider the two composites from the top object. First consider the right side. By naturality, the outer cell commutes. The map from the top is given by sampling from all the \bar {\Delta }, using the coordinate of the second one to index into the sequence \bar {\Delta }(\omega )^\omega , then taking x_{ij} where i,j are the resulting two natural numbers.

Now consider the left side. The map labeled \mu ' is given by forming the joint distribution on \omega \times \omega obtained by ... The top left cell is simply F applied to a map in \mathsf {Borel}, which is easily seen to commute.

Thus it suffices to show that the two maps F(\bar {\Delta }(\omega )^\omega \times \bar {\Delta }(\omega )) \to F(\omega \times \omega ) given either by using this mutiplication in \mathsf {Borel}, then sampling, or by sampling from everything and combining, agree. But this is essentially the claim that the sampling map is a (infinitary) midpoint homomorphism.

Either here or elsewhere, need to insert this

Backlinks

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.