Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: Continuous-time Markov processes as functors

Nathaniel Virgo (Oct 05 2020 at 02:23):

In discrete time, one way to think about Markov chains is the following: let $M$ be the natural numbers as a monoid under addition. Then a functor from $M$ into a Markov category defines a (time homogeneous) Markov chain. In the finite case, $1$ gets mapped to some stochastic matrix $P$, and any other natural number $n$ gets mapped to $P^n$.

I had it in my mind that one could do the same thing for continuous-time Markov processes just by replacing the natural numbers with the reals, but I've realised there's a subtlety, and I'm wondering (i) what's the best way to resolve it, and (ii) if there's an existing treatment that I can read about that takes this kind of approach.

The most obvious way to do it is to use the monoid $\langle[0,\infty),{+}\rangle$. A continuous-time Markov process can be expressed as a functor from this monoid to a Markov category. For example, we could have a functor that maps a nonnegative real number $t$ to a stochastic matrix $e^{Ht}$, where $H$ is an infinitesimal stochastic matrix.

The problem is that this scheme also admits things that are not of this form. For example, given an idempotent non-identity stochastic matrix $P$, we can have a functor that maps $0$ to the identity matrix, and any $t>0$ to $P$. This corresponds in some way to a stochastic process with infinite transition rates, and it seems that in general functors of this form correspond to continuous-time Markov processes with possibly infinite rates.

I actually find that kind of cool, but sometimes it would be convenient to talk about continuous-time Markov chains as we normally understand them, without the possibility of infinite rates. I had it in my mind that we could achieve this by using the monoid $\langle \mathbb{R}, {+}\rangle$ instead of $\langle[0,\infty),{+}\rangle$, but I've realised that doesn't work. Given an infinitesimal stochastic matrix $H$ and $t>0$, the matrix $e^{-Ht}$ can (and generally will) have negative entries. This means "most" continuous-time Markov processes don't correspond to functors of this form.

So the question is, can the idea be salvaged? Is there a way to talk about continuous-time Markov processes as functors from a monoid into a Markov category, in such a way that we include all the Markov processes we'd normally want to talk about, but exclude the ones with infinite transition rates? I'm keen to read any existing treatment of ideas along these lines.

Nathaniel Virgo (Oct 05 2020 at 02:35):

I guess a related question: have these "continuous-time Markov processes with possibly infinite rates" been written about anywhere? It would be handy to know how to characterise them in terms of linear algebra.

Nathaniel Virgo (Oct 05 2020 at 03:22):

In this blog post, @Jade Master talks about smooth dynamical systems as enriched functors from $\langle \mathbb{R},{+}\rangle$ to another category, where the enrichment takes care of the smoothness. I'm wondering if something similar can be done here. I hope the enrichment would be in something simpler than diffeological spaces, because in some sense a continuous-time Markov process is a simpler thing than a general dynamical system.

John Baez (Oct 05 2020 at 04:11):

You probably want to work in the context of topological categories and continuous functors.

Nathaniel Virgo (Oct 05 2020 at 04:17):

Great, many thanks!

Where would I go to learn what those things are? Wikipedia and nlab tell me there are multiple nonequivalent things called topological categories, so I want to make sure I'm looking in to the right one.

John Baez (Oct 05 2020 at 04:22):

I mean categories enriched over Top, not categories internal to Top.

John Baez (Oct 05 2020 at 04:25):

A Markov semigroup is an example of a strongly continuous one-parameter semigroup on a Banach space $V$, and it's pretty obvious (once one has the definitions understood) that the latter is the same as a continuous functor from the topological monoid $([0,\infty),+)$ to $\mathrm{End}(V)$ where the latter is a topological monoid using the strong operator topology. (A topological monoid is the same as a one-object topological category.)

John Baez (Oct 05 2020 at 04:28):

Strongly continuous one-parameter semigroups: https://en.wikipedia.org/wiki/C0-semigroup

John Baez (Oct 05 2020 at 04:33):

Strong operator topology: https://en.wikipedia.org/wiki/Strong_operator_topology

John Baez (Oct 05 2020 at 04:35):

I've done stuff on Markov processes from a categorical viewpoint in my work on the phylogenetic operad:

http://www.tac.mta.ca/tac/volumes/32/40/32-40abs.html

However, it's probably more efficient to ask me questions than read this.

John Baez (Oct 05 2020 at 04:41):

By the way, a one-object category enriched in Top is the same as a one-object category internal to Top since there's just one topology on the one-element set. They're both just topological monoids. So it doesn't really matter what concept of "topological category" you use as long as you're only dealing with one-object categories.

John Baez (Oct 05 2020 at 04:42):

The point is, this gives a way to force everything to be continuous.

John Baez (Oct 05 2020 at 04:43):

That'll eliminate the pathological example you mentioned. And people working on continuous-time Markov processes always demand them to be continuous.

Nathaniel Virgo (Oct 05 2020 at 04:45):

Great, thanks, I'll look in to this stuff and get back to you if I have questions.

(Thanks for the link to the phylogenetics paper also. I probably should read it at some point, it's relevant to my interests.)

John Baez (Oct 05 2020 at 04:51):

The cool part of that paper is that "phylogenetic trees" as widely studied are operations in a topological operad that's the coproduct of the topological monoid $[0,\infty)$ and the operad for commutative semigroups.

John Baez (Oct 05 2020 at 04:52):

It took about a day to realize this and over a year to prove it.

John Baez (Oct 05 2020 at 04:53):

The annoying part was getting a really concrete general description of the coproduct of topological operads.

Jules Hedges (Oct 05 2020 at 10:00):

This might be totally wrong/unhelpful, but one idea I've had in mind for a long time for similar things is to try to work in the poset of real intervals, in the hope that it makes the passage from discrete to continuous look like a categorical limit

Daniel Geisler (Oct 05 2020 at 22:51):

When you say phylogenetic tree, do you mean https://oeis.org/A000311 ? This version of phylogenetic trees is the heart of my derivation of continuous dynamical systems. Unfortunately the derivation is not categorical .

John Baez (Oct 05 2020 at 22:59):

No, I mean the concept of phylogenetic tree where the edges have lengths - in biology they want to know how "long" (in years) is the edge between each branching. It's explained in the intro to my paper.

Nathaniel Virgo (Oct 07 2020 at 00:46):

Here's a related, but possibly more difficult/interesting question:

We can think of a continuous-time Markov chain (CTMC) as a continuous functor from $\big([0,\infty),+\big)$ to a Markov category. (For now I'm just assuming the 'continuous' part works - I guess it's not actually needed for this next question.) But we might also want to think of it as a set of states and possible transitions, that is, a graph whose edges have rate constants associated with them, which are numbers in $(0,\infty)$.

Given such a transition graph, one can build a CTMC by building an infinitesimal stochastic matrix in a straightforward way. (If there are multiple edges you have to add their rate constants together, and if there are self-loops you ignore them.) Then from the infinitesimal stochastic matrix you can build a functor from $\big([0,\infty),+\big)$ to a Markov category, as discussed above.

But is there a way to express that relationship in a more category-theoretic way, that is, in terms of functors between suitable categories of weighted graphs and CTMCs, without needing to talk about what goes on "inside" the objects?

Jade Master (Oct 07 2020 at 02:02):

I don't have it worked out but I'm guessing that this might be a free monoid construction.

Jade Master (Oct 07 2020 at 02:03):

Sorry for the vague comment but I've got to go

Nathaniel Virgo (Oct 19 2020 at 02:07):

I think I've figured out the answer to my second question now. It turned out to be less of a technical question and more of a philosophical "how to do applied category theory" sort of a question. But since that kind of question is currently relevant in another thread, I might as well mention it.

My question, basically, was "how do I think of these things as objects with internal structure (weighted transition graphs in this case) and also as functors at the same time?". I think the solution is just to define the right notion of morphism on weighted transition graphs. If I define the right morphism then the category of weighted graphs will become equivalent to the category of continuous functors, and the equivalence will give me functors in both directions, between the category of transition graphs and the category of continuous functors from $\big([0,\infty),+\big)$ to FinStoch. Even if it doesn't end up being an equivalence of categories, having a functor from a category transition graphs to the functor category is still useful. Natural transformations between these functors seem to correspond to lumpability of Markov processes, and that tells me how I should define the morphisms of weighted transition graphs - the rest is just filling in the details.

Matteo Capucci (he/him) (Oct 19 2020 at 10:24):

+1 for 'lumpability' :laughing: