Vanessa Kosoy explained to me that there are approximately 5 million ways of composing two infradistributions/infra-Markov kernels, each of which is useful in certain circumstances. She has an eldritch graphical language for expressing these, and it is my task to figure out if there is categorical structure underlying the madness.
First, let’s call the Kleisli category of the infradistribution monad \mathsf{InfraStoch}.
I have a hypothesis that one of the compositions, which she calls \bowtie might induce a copy-discard structure on \mathsf{InfraStoch}. A copy-discard structure is a symmetric monoidal structure along with a comonoid on each object. It’s kind of like a Markov category, but the monoidal unit is not required to be terminal. Indeed, 1 is not terminal in the Kleisli category of the infradistribution monad, because there are two infradistributions on it, the singleton and the empty set.
The type of \bowtie is
\bowtie \colon \square X \times \square Y \to \square (X \times Y)
so it looks like a laxator for \square. It’s defined by
where \eta ; (1_X \otimes !) is the composition of the Markov kernels \eta \colon 1 \to X \otimes Y and (1_X \otimes !) \colon X \otimes Y \to X (! \colon Y \to 1 is the unique such map). In other words, it is the marginalization of \eta over its second argument.
This is interesting because if you have two singleton infradistributions, their composition is not a singleton, it is the set of all infradistributions that have the right marginals. So composition is not independent composition, which means that the inclusion \mathsf{Stoch} \hookrightarrow \mathsf{InfraStoch} is not a strong monoidal functor. (Later on, we may discover that there is a 2-category structure on \mathsf{InfraStoch} and this is somehow lax with respect to 2-morphisms, but we aren’t there yet).
Now, a lax symmetric monoidal structure for \square with respect to \times automatically induces a copy-discard structure. Why is this true?
First of all, the lax symmetric monoidal structure induces a symmetric monoidal structure on \mathsf{InfraStoch}, where the parallel composition of two infrakernels f \colon A \to \square X, g \colon B \to \square Y is given by
So we just need to give a unitor, and show unitality, associativity, and symmetry. The unitor is easy: we just take the map 1 \to \square 1 which goes to the singleton infradistribution on 1.
Unitality then follows because if \delta_\ast is the singleton distribution on 1, then U \bowtie \{\delta_\ast\} is the set of distributions on U \times 1 which marginalize to a distribution in U, which is what we want.
Associativity follows because if we have infradistributions U \in \square X, V \in \square Y, W \in \square Z, then U \bowtie V \bowtie W is the collection of distributions on X \times Y \times Z which marginalize to something in U, to something in V, and to something in W, whichever way we parenthesize it.
And finally, symmetry is obvious because we could exchange X and Y in our definition of \bowtie and nothing changes.
Then, we get a copy-discard structure because there is a strict monoidal functor from \mathsf{Meas} into \mathsf{InfraStoch}, and thus the comonoid structure on each object of \mathsf{Meas} pushes forward.
We can now ask all sorts of questions about this category that we like to ask about copy-discard categories. For instance, does it have conditionals? Does it have a divergence structure? Can we talk about the other ways of composing infradistributions using this category? But those questions will have to wait for a future post.