6

Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation, $$e(A|x) = \int_X e(A|y) \, e(dy|x) \qquad \forall x \in X, A \in \Sigma_X.$$ Does this imply that $e$ splits? That is, do there exist another standard Borel space $Y$ and Markov kernels $p : X \to Y$ and $i : Y \to X$ such that $i \circ p = e$ and $p \circ i = \mathrm{id}_Y$?

Two remarks:

  • Note that the splitting easily implies the idempotency, but the converse is not so clear.

  • We have a proof that splitting is possible based on the theory of Markov categories. This is Corollary 4.4.5 in this paper, which is a special case of a general categorical result (Theorem 4.4.3). So my main question is really:

is this new? If not, where was this done?

We haven't seen the problem mentioned anywhere else in the literature so far.

Tobias Fritz
  • 5,785
  • This seems clear at least when $X$ is finite. Do you need category-theoretical arguments to overcome technical conditions in Blackwell's Theorem 7? – Iosif Pinelis Aug 12 '22 at 15:50
  • @IosifPinelis, thanks for thinking about it. Yes, the discrete case is quite easy. The difficulty in general is that it's perhaps not so clear how to even find the "mediating" space $Y$ and how to prove the relevant properties. My personal subjective feeling is that the categorical formalism suggests constructions that would be less obvious in pure measure-theoretic language. But this it not so relevant for the question and was merely suppose to provide some context for why I wonder whether it's new: if it was straightforward in standard formalism, then surely it would be a standard result. – Tobias Fritz Aug 12 '22 at 16:09
  • (I'd be happy to share things over email in case that anyone is interested in the details of our proof.) – Tobias Fritz Aug 12 '22 at 16:10
  • Yes, I would be interested in seeing the proof. Perhaps, it will give me a window into some aspects of category theory. But I am not promising to be able to understand your proof. :-) – Iosif Pinelis Aug 12 '22 at 16:16
  • On the other hand, I can also imagine that one can strengthen Blackwell's arguments to a more standard measure-theoretic proof by turning the index set of his partition into a suitable measurable space. I just haven't seen it done anywhere. @IosifPinelis: sounds good, I'll send you an email later! – Tobias Fritz Aug 12 '22 at 16:24

1 Answers1

-2

I do not know if the result is new or not. But I believe the problem is easy if you think in terms of the Eilenberg-Moore category of the Giry monad. Since that category is isomorphic to a certain subcategory of superconvex spaces let me work in that category. (If you're not familiar with superconvex spaces, resort to EM, just notice that all the measurable maps happen to be countably affine functions also!)

So let $\mathcal{P}X$ be the set $\mathcal{G}X$ endowed with the natural superconvex space structure which is defined pointwise. Similarly, for $f:X \rightarrow Y$ a morphism in standard Borel let $\mathcal{P}f: \mathcal{P}X \rightarrow \mathcal{P}Y$ denote the countably affine map in superconvex spaces.

Let $k:X \rightarrow \mathcal{G}X$ be your kernel viewed in the Kleisi category, which, in the category of superconvex space, corresponds to the countably affine map $\mu_X \circ \mathcal{P}k:\mathcal{P}X \rightarrow \mathcal{P}X$. To say it is idempotent just says $\mu_X \circ \mathcal{P}k \circ \mu_X \circ \mathcal{P}k = \mu_X \circ \mathcal{P}k$. In the EM category (or Superconvex category) all colimits exist. So to find the splitting just take the coequalizer $q$ of the two parallel arrows, $\mathbf{id}: \mathcal{P}X \rightarrow \mathcal{P}X$ and $\mu_X \circ \mathcal{P}k: \mathcal{P}X \rightarrow \mathcal{P}X$. Now, by definition, the superconvex space structure on the quotient space is defined by $\sum_{i \in \mathbb{N}}p_i q[P_i] := q(\sum_{i \in \mathbb{N}} p_i P_i)$ where $\mathbf{p} \in \mathcal{G}(\mathbb{N})$ with components $p_i$.

The definition of the structure on the quotient space implies the insertion map $\iota: \mathcal{P}X/\sim \rightarrow \mathcal{P}X$ is a countably affine map, i.e., take a representative from each equivalence class and map $[P] \mapsto P$. That's your splitting which, incidentally, is a nice example of a $\mathcal{G}$-algebra arising in practice.

kirk sturtz
  • 250
  • Sorry, but that doesn't answer my question, which is about novelty and finding a reference. It also doesn't solve the mathematical problem I posed, since it replaces it by a much easier one. Here's a formulation of the mathematical problem in your formalism: show that $\mathcal{P}X/ \sim$ is a free Giry algebra associated to a standard Borel space. – Tobias Fritz Aug 13 '22 at 06:44
  • The quotient space $\mathcal{P}X / \sim$ is a NON-FREE Giry algebra. In your posting on Markov categories YOU claimed that NON-FREE algebras rarely arise in practice. Well it just arose! The whole point of using EM is precisely that it makes solving problems easier. The Kleisi category does not have quotients - which is precisely why using the Kleisi category (Markov cat) is not the appropriate choice. Your question clearly illustrates why you should consider EM. – kirk sturtz Aug 13 '22 at 08:28
  • Sorry to disagree, but we've proven that the splitting exists in the Kleisli category. Since splittings of idempotents are unique up to iso and the Kleisli cat embeds into the EM cat, this implies that the algebra is free. (And as mentioned in the comments with Iosif Pinelis, the proof is quite simple in the discrete case.) So if you claim that it is non-free, then I'd like to see a concrete example of that (satisfying the assumptions mentioned in the OP). – Tobias Fritz Aug 13 '22 at 08:45
  • Take $X=2$ so $\mathcal{G}(X) \cong [0,1]$. Take $k(0)=\frac{1}{3}$ and $k(1)= \frac{2}{3}$. Then your quotient space is the discrete space ${0,1,u}$ with the superconvex space structure characterized by $r 0 + (1-r) 1 = u$ for all $r \in (0,1)$, $ r 0 +(1-r) u = u$ for all $r \in (0,1)$ and $r1 + (1-r)u=u$ for all $r \in (0,1)$. Nothing free about that space. – kirk sturtz Aug 13 '22 at 09:03
  • Your $k$ is not idempotent, so it doesn't satisfy the assumptions of the OP. – Tobias Fritz Aug 13 '22 at 09:05
  • Also your quotient calculation is wrong, and the correct quotient is a singleton. We have $0 \sim \frac{1}{3}$, and this implies that the interval $[0,\frac{1}{3}]$ is a single equivalence class, and similarly for $[\frac{2}{3},1]$. But then also $\frac{1}{3} = \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot \frac{2}{3} \sim \frac{1}{2} \cdot \frac{1}{3} + \frac{1}{2} \cdot 1 = \frac{2}{3}$. Taken together, these relations imply that all points are identified. – Tobias Fritz Aug 13 '22 at 09:18
  • The proof I gave shows that the idempotent kernel splits. Your implied question is Is the quotient space (of the splitting) also a free space? Yes - the coequalizer of the parallel pair with one of the arrows the identity map on the free space $\mathcal{P}(X)$ implies the quotient must be a subobject of $\mathcal{P}(X)$ which will also necessarily be a free space cuz if any two points of that free space, say $P$ and $Q$ satisfy $k(P)=id(P)$ and $k(Q)=id(Q)$ then all points on the line connecting those two points, $rP + (1-r)Q$ will also satisfy $k(rP+(1-r)Q)=id(rP+(1-r)Q)$... – kirk sturtz Aug 13 '22 at 23:49
  • Yes, maybe this goes in the right direction of a proof in the finite case. But as mentioned in the comments to the question, the finite case is easy, and I don't think that you can get a proof in the non-finite case based on considering finite convex combinations only. (BTW the freeness wasn't my "implied" question, but is rather part of the reformulation of my original question in your framework, together with showing that the quotient is standard Borel.) – Tobias Fritz Aug 14 '22 at 08:04
  • I think it does prove the non-finite case because $r$ is your free parameter. The kernel map $k$ itself is countably affine so, at minimum, it certainly holds for countably infinite spaces. If I think of a more convincing argument I'll shout out. Yes, we do live in different worlds (categories) don't we. Sorry for my confusion. – kirk sturtz Aug 14 '22 at 08:37
  • The explication of the term free space is given (now) in Example 5.6 on the nLab page for superconvex space. I conjecture that the quotient space of any space $\mathcal{G}(X)$ for $X$ uncountable is going to be a free space (which may be trivial). That conjecture, required for your proof, is priority number one as it is required to further understand what I have attempted to explain in Example 5.6. – kirk sturtz Aug 16 '22 at 01:57
  • Since the free space construction $\mathcal{F}: \mathbf{Set} \leftrightarrows \mathbf{SCvx}: \mathcal{U}$ works in $\mathbf{SCvx}$ one obtains the result that The quotient of a free space is always a free space of the quotient. The proof is simple. Let R be a congruence relation on $\mathcal{F}(X)$. This induces an equivalence relation $S$ on the set $X$ by $(x,y) \in S$ iff $(1x,1y) \in R$. The condition of countably affine then induces an isomorphism $\mathcal{F}X /R= \mathcal{F}(X/S)$ by $\sum_{i \in \mathbb{N}}p_i [1 x_i]R \mapsto \sum{i \in \mathbb{N}} p_i [x_i]_S$. – kirk sturtz Aug 17 '22 at 05:32
  • But to see your splitting within $\mathbf{Std}$ use the kernel space construction. – kirk sturtz Aug 17 '22 at 05:38
  • Sorry about the delay. Are you suggesting that a quotient of a free superconvex space is always free? I must be misunderstanding something, since that is very obviously false: every superconvex space is a quotient of a free one, but not every superconvex space is free. – Tobias Fritz Aug 18 '22 at 20:26
  • Regardless, I still don't see much motivation for me to study your framework. If you can update your answer (at some point) with a complete and correct proof of the statement made in the OP, then I'll be happy to take another look. Recall that the problem is to prove that every idempotent endomorphism of a free standard Borel Giry algebra splits through a Giry algebra that is itself free and standard Borel. – Tobias Fritz Aug 18 '22 at 20:27
  • The quotient of a free superconvex space is, in general, usually NOT a free space. That is why I was so confused. The example in 5.6 on nLab is a nice example of that. But for your particular problem, where the quotient arises from an identity map and an idempotent Markov kernel, that does turn out to be the case. Again, that's why I was so dumbfounded. I didn't write out the full argument on nLab as I'm still trying to see how deep the analogy between the free space construction $Set \leftrightarrows SCvx$ extends to $Std \leftrightarrows SCvx$. I fully understand your last comment. – kirk sturtz Aug 19 '22 at 02:13
  • I understand that, but my second to last comment was asking what you mean by the claim that "The quotient of a free space is always a free space of the quotient", since this literally implies the absurd statement that a quotient of a free space is always free. Anyway, I will drop this conversation for now. – Tobias Fritz Aug 19 '22 at 05:57