6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This seems clear at least when $X$ is finite. Do you need category-theoretical arguments to overcome technical conditions in Blackwell's Theorem 7? $\endgroup$ Aug 12, 2022 at 15:50
  • $\begingroup$ @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. $\endgroup$ Aug 12, 2022 at 16:09
  • $\begingroup$ (I'd be happy to share things over email in case that anyone is interested in the details of our proof.) $\endgroup$ Aug 12, 2022 at 16:10
  • $\begingroup$ 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. :-) $\endgroup$ Aug 12, 2022 at 16:16
  • $\begingroup$ 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! $\endgroup$ Aug 12, 2022 at 16:24

1 Answer 1

-2
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ 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. $\endgroup$ Aug 13, 2022 at 6:44
  • $\begingroup$ 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. $\endgroup$ Aug 13, 2022 at 8:28
  • $\begingroup$ 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). $\endgroup$ Aug 13, 2022 at 8:45
  • $\begingroup$ 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. $\endgroup$ Aug 13, 2022 at 9:03
  • $\begingroup$ Your $k$ is not idempotent, so it doesn't satisfy the assumptions of the OP. $\endgroup$ Aug 13, 2022 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.