Understanding the Giry monad

Question

I would like to understand the Giry monad, which is used to reason about probability in category theory.

The issue is that I'm hitting a stumbling block understanding monads in general, in the category theoretical sense. This is partly because most of the information I can find about monads is in the context of functional programming. (I understand that in some sense those monads are the same kind of thing as the Giry monad, but I don't understand the relationship.)

Some details about monads in the mathematical sense are given for example here, which I more or less understand, but there is still a rather large gap in between digesting the definition of a monad and being able to read Giry's paper. Aside from the technical nature of the paper, I think the issue is that the definition of a monad doesn't, by itself, help me to understand what to do with the concept. If I try to imagine how I might use the concept to reason about probability, I fail.

Consequently, I'm wondering if a brief outline can be given, of

1. how monads are used in practice in the context of mathematics rather than programming, and

2. what the Giry monad is specifically, and why it's useful/interesting in relation to probability theory.

I'm looking for an explanation in terms of fairly basic notions from category theory. (i.e. functors, natural transformations, products and coproducts, monoidal categories, that sort of thing.)

If a complete and concise explanation can be given in elementary terms that would be great, but if that's not possible it would be helpful at least to have an overview of what it is and why it's useful, along with some pointers toward other resources.

Answer 1

To understand monads, first you have to understand functors.

If $\mathbf{C}$ and $\mathbf{D}$ are categories, then a functor $T : \mathbf{C} \rightarrow \mathbf{D}$ assigns to each object $X$ of $\mathbf{C}$ an object $TX$ of $\mathbf{D}$ and to each arrow $f : X \rightarrow Y$ of $\mathbf{C}$ an arrow $Tf : TX \rightarrow TY$ in $\mathbf{D}$. There's a couple of further conditions we need before $T$ can be regarded as a functor, but that's the gist.

If that seems very abstract, it's because it is! The good news is that category theory is absurdly abstract, yet somehow still provides the needed concepts to analyse a wide variety of mathematical phenomena from a single coherent standpoint. The bad news is that, due to this high level of generality, you won't always have intuition for a concept straightaway. There's two basic tricks category theorists often use to get quick intuition for a new concept.

The first trick is to "decategorify", moving from category theory to order theory. Instead of categories, we think about partially ordered sets. Functors are replaced by monotone mappings, and natural transformations becomes proofs that one monotone mapping is pointwise less-than-or-equal-to another monotone mapping. You NEED to understand this idea if you're going to understand category theory; you simply won't survive without it (please comment if the idea is not clear).

The second trick is to, look at the category of sets, which in some sense is the most basic and fundamental category. After this, you can try to deploy the concept in any of the other most basic categories; $\mathbf{Grp}$, $\mathbf{Ring}$, $R\mathbf{Mod}$, etc. and see what happens there.

With that in mind, let's try to get intuition for functors $\mathbf{Set} \rightarrow \mathbf{Set}$. A good intuition is that these are different notions of "container". For example, there's a functor $\mathrm{List} : \mathbf{Set} \rightarrow \mathbf{Set}$ that assigns to each set $X$ the set of all (finite) lists of items of $X$. We denote this object $\mathrm{List} X$ of course. Furthermore, we can't understand a functor properly without thinking about what it does to arrows. So, given a function $X \rightarrow Y$, can you think of an "obvious" function $\mathrm{List} X \rightarrow \mathrm{List} Y$? For example, suppose we're talking about the function $\mathrm{square} : \mathbb{N} \rightarrow \mathbb{N}$ that maps each natural number to its square. Suppose we have a list of natural numbers, like $[3,8,4]$. What should it mean to apply squaring to this list? Well, the obvious thing to do is to apply it to each item separately. Like so: $$(\mathrm{List} \,\mathrm{square})([3,8,4]) = [9,64,16].$$ Indeed, this basically defines the $\mathrm{List}$ functor. In particular: $$(\mathrm{List} f)([x_1,\ldots,x_n]) = [f(x_1),\ldots,f(x_n)].$$

Pretty much every functor $T:\mathbf{Set} \rightarrow \mathbf{Set}$ is similar to this. We assign to every set $X$ the set of all containers $TX$ of some particular type (lists, subsets, multisets, Catalan trees, etc.) And given a function $f : X \rightarrow Y$, the idea is that that $Tf : TX \rightarrow TY$ is the function that applies $f$ to every item in the container you give as input.

So, that's our intuition for endofunctors on $\mathbf{Set}$. They're basically "notions of container". But some notions of container are special in the following way: if we have a container whose items are themselves containers (of the same type), then we can flatten this down to a single container. For example, suppose I have a list of lists, like so: $$[[3,4],[15,12,16],[2]]$$

Well, I can flatten this down to a single list, obtaining $$[3,4,15,12,16,2].$$ Since this process of flattening takes as input a list of lists and returns as output a (mere) list, it's type signature is $$\mathrm{List}(\mathrm{List}(X)) \rightarrow \mathrm{List}(X).$$ That's basically what a monad is; it's a functor with a way of flattening containers of containers down to (mere) containers. The way of flattening things down is usually denoted $\mu$. So a monad on a category $\mathbf{C}$ is basically an endofunctor on $\mathbf{C}$ together with a family of mapts $\mu_X : TTX \rightarrow TX$ that are compatible in a certain way. The actual definition is a little bit more complicated; for example, we also have a monoidal unit $\eta$. The idea is that $\eta$ produces singleton containers. For example, in the case of $\mathrm{List}$, we have $\eta_X(x) = [x]$. Some axioms need to hold of course.

Anyway, what does this all have to do with probability theory? As you've correctly identified, the answer is the Giry monad. The easiest way to get intuition for the Giry monad is to think about what it does to finite sets. So, that's what we'll do. But before going on, we need to talk about formal linear combinations.

We've talked about the $\mathrm{List}$ monad. There's also a multiset monad, which does the same thing, except that our containers don't remember the order that their elements were inserted in. For example, $[5,4,5]$ and $[5,5,4]$ represent different lists, but they represent the same multiset. A a better notation for this multiset is therefore $2[5] + [4]$, to indicate that there's $2$ copies of $5$ but only $1$ copy of $4$. This teaches us something important; a multiset of elements of $X$ is the same thing as a formal $\mathbb{N}$-linear combination of elements of $X$.

[To be continued when I have more laptop power]