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: event: Categorical Probability and Statistics 2020 workshop

Topic: A monad of random variables?

Alex Simpson (Jun 09 2020 at 07:21):

Paolo Perrone said:

Very good! I start: do random variables form a monad, in any category and any context?

Hi Paolo. This is related to your question at the end of my talk, which I feel like I didn't do a very good job of answering, so I'm glad you've brought this up again here.

If one is happy to fix a sample space $\Omega$ and define an $X$-valued random variable as a map from $\Omega$ to $X$, then one indeed has a random-variable monad, in any category in which exponentials $X^\Omega$ exist, as the functor $X \mapsto X^\Omega$ carries a monad structure.

So, for example, in the category of qbs spaces, one could take $[0,1]$ with the uniform distribution as a canonical sample space and declare $X^{[0,1]}$ to be a monad of random variables. This doesn't seem very useful though. The monad of probability measures in qbs is much more interesting.

The setting of my talk departs from this in two ways. Firstly, the sample space (which is left implicit) is allowed to "grow". This is compatible with having a monad on a presheaf category. (I have a concrete example, but its complicated. I can elaborate elsewhere if there is interest.)

The second departure in my account of random variables is that they are identified up to almost sure equality. I believe this kills the monad structure. The problem can already be seen in the context of a fixed sample space. If one tries to make a monad out of $X^\Omega/{=_{as}}$ then there seems no sensible way to define the multiplication map. Perhaps I am missing something.

Personally, I like the identification of almost surely equal random variables, and I don't mind foregoing the monad to have it. But it could also be interesting and potentially fruitful to start with a monad of random variables and not identify up to almost-sure equality.

Paolo Perrone (Jun 09 2020 at 13:30):

Alex Simpson said:

Paolo Perrone said:

Very good! I start: do random variables form a monad, in any category and any context?

Hi Paolo. This is related to your question at the end of my talk, which I feel like I didn't do a very good job of answering, so I'm glad you've brought this up again here.

If one is happy to fix a sample space $\Omega$ and define an $X$-valued random variable as a map from $\Omega$ to $X$, then one indeed has a random-variable monad, in any category in which exponentials $X^\Omega$ exist, as the functor $X \mapsto X^\Omega$ carries a monad structure.

So, for example, in the category of qbs spaces, one could take $[0,1]$ with the uniform distribution as a canonical sample space and declare $X^{[0,1]}$ to be a monad of random variables. This doesn't seem very useful though. The monad of probability measures in qbs is much more interesting.

The setting of my talk departs from this in two ways. Firstly, the sample space (which is left implicit) is allowed to "grow". This is compatible with having a monad on a presheaf category. (I have a concrete example, but its complicated. I can elaborate elsewhere if there is interest.)

The second departure in my account of random variables is that they are identified up to almost sure equality. I believe this kills the monad structure. The problem can already be seen in the context of a fixed sample space. If one tries to make a monad out of $X^\Omega/{=_{as}}$ then there seems no sensible way to define the multiplication map. Perhaps I am missing something.

Personally, I like the identification of almost surely equal random variables, and I don't mind foregoing the monad to have it. But it could also be interesting and potentially fruitful to start with a monad of random variables and not identify up to almost-sure equality.

@Alex Simpson Thanks for the details!
Do you refer to the multiplication map $X^{\Omega \times \Omega} \to X^\Omega$ induced by the diagonal $\Omega\to\Omega\times\Omega$ in a cartesian closed category? I think that this is not what we want: this would only "pick out that part of the measure that lies on the diagonal and map it to $X$", which is not what I'm looking for, I believe.
In particular, I'd like the map $RV(X)\to PX$ given by taking the image measure to induce a morphism of monads.

Alex Simpson (Jun 09 2020 at 14:11):

Paolo Perrone said:

Alex Simpson Thanks for the details!
Do you refer to the multiplication map $X^{\Omega \times \Omega} \to X^\Omega$ induced by the diagonal $\Omega\to\Omega\times\Omega$ in a cartesian closed category? I think that this is not what we want: this would only "pick out that part of the measure that lies on the diagonal and map it to $X$", which is not what I'm looking for, I believe.
In particular, I'd like the map $RV(X)\to PX$ given by taking the image measure to induce a morphism of monads.

Yes I did mean the multiplication map induced by the diagonal. I think there are situations in which this is what one does want for a monad of random variables, even though it does not lead to a morphism of monads $RV(X)\to PX$ . I am thinking in particular of a certain scenario involving programming with random variables, the discussion of which would take us too far out on a limb for me to attempt here. But there is also an intuitive mathematical point of view that gives a rationale for using the diagonal. As I think you explained very nicely in your talk, the very idea of having a bunch of random variables over a single sample space is that the sharing of the sample space induces correlations between the random variables. Using the diagonal for the multiplication implements a similar mechanism for having correlations between the outer random variable $X \in RV(RV(A))$ and its inner random variables, namely those random variables in $RV(A)$ to which $X$ randomly evaluates.

Tobias Fritz (Jun 09 2020 at 14:23):

@Alex Simpson, @Paolo Perrone: since part of Alex's philosophy is to implement the idea that the sample space isn't fixed, perhaps one could naively hope for $RV$ to be an idempotent monad, where the multiplication isomorphism $RV(RV(A)) \cong RV(A)$ would simply reinterpret a "doubly random" variable in $(X^\Omega)^{\Omega'}$ as an ordinary random variable in $X^{\Omega \times \Omega'}$. Could this work? I may well be missing something obvious, and I'm also not sure about the compatibility with quotienting by almost sure equality.

(Edit: In our finite samples paper, Paolo and I did something like the previous paragraph for finite $\Omega$, and considering a version of $RV$ as a graded monad where the grading is by $\Omega$. This grading is what allowed the multiplication maps to be just the currying isomorphisms.)

Note: if there's more discussion on a monad of random variables, I can move the existing posts on it to a separate topic.

Paolo Perrone (Jun 09 2020 at 14:34):

Tobias Fritz said:

Alex Simpson, Paolo Perrone: since part of Alex's philosophy is to implement the idea that the sample space isn't fixed, perhaps one could naively hope for $RV$ to be an idempotent monad, where the multiplication isomorphism $RV(RV(A)) \cong RV(A)$ would simply reinterpret a "doubly random" variable in $(X^\Omega)^{\Omega'}$ as an ordinary random variable in $X^{\Omega \times \Omega'}$. Could this work? I may well be missing something obvious, and I'm also not sure about the compatibility with quotienting by almost sure equality.

(Edit: In our finite samples paper, Paolo and I did something like the previous paragraph for finite $\Omega$, and considering a version of $RV$ as a graded monad where the grading is by $\Omega$. This grading is what allowed the multiplication maps to be just the currying isomorphisms.)

Note: if there's more discussion on a monad of random variables, I can move the existing posts on it to a separate topic.

Yep, this is more in the spirit of that I have in mind. (But I'm not entirely sure that the monad would be idempotent that way. I mean, the two object are isomorphic, but I'm not sure that the multiplication map is an iso.)

Paolo Perrone (Jun 09 2020 at 14:36):

If enough people are willing to chime in, we could create a separate thread.

Tobias Fritz (Jun 09 2020 at 14:37):

Oh, right! I haven't argued that hiding $\Omega$ will preserve the invertibility of the multiplication. So I'll have to take back the idempotency.

I'll move this to a separate topic now, for it not to clutter the "open problems" one.

Paolo Perrone (Jun 09 2020 at 15:12):

Here's a concrete prototype of what I have in mind, for the case of finitely supported random variables.
Let's work in the category of sets. Let $1$ be a set of 1 elements, $2$ a set of two elements, and so on for $N$ (one set for each cardinality).
Let now $X$ be any set. A finitely supported random variable on $X$ is a finite set $N$ as above, together with a probability measure on $N$ and a function $N\to X$. Denote by $FRV(X)$ the set of all finitely supported random variables on $X$.
Now an element of $FRV(FRV(X))$ consists of a finite set $N$ with a measure $p$ on it, and a function $f:N\to RV(X)$, which assigns to each element $i$ of $N$ a finite set $N_i$, a measure $p_i$ on it, and a function $f_i:N_i\to X$. Denote this element of $FRV(FRV(X))$ by $q$, for brevity
Define now $\mu(q)\in FRV(X)$ to be the finitely supported random variable on $X$ given as follows.

• The finite set is given by $M:=\coprod_{i\in N}N_i$.
• The function $M\to X$ is given by gluing the $f_i$, by the universal property of the disjoint union.
• The measure on $M$ is given by assigning to the element $(i,j)$ of $M$, with $i\in N$ and $j\in N_i$, the number $p(i)\cdot p_i(j)$.
  This gives a mapping $\mu:FRV(FRV(X))\to FRV(X)$ which should give the multiplication of a monad.

What I'd like: the same, but not finitely supported.

Paolo Perrone (Jun 09 2020 at 15:26):

Now, the main technicality here is: in which category do we want this to happen?
Suppose we take Meas, and instead of the sets $N$ we take all standard Borel spaces, one representative for each isomorphism class. The question then translates to: which sigma-algebra do we put on $RV(X)$?

Tobias Fritz (Jun 09 2020 at 15:27):

Hmm, then it looks like we're almost back at the codomain (op)fibration: your $FRV$ assigns to every (say finite) set its fibre in the codomain fibration. So presumably your $FRV$ needs to be considered as a category, or at least as a groupoid.; it clearly doesn't want to be a mere set, right? Which suggests that $FRV(FRV(X))$, assuming that it makes any sense, is likely to have even higher structure than that. We had some discussion in the thread for Bas's talk on the potential role of higher structure, but it seemed vague and perhaps ill-motivated. But if there's a way to define a version of $RV$ as a homotopy type rather than a set, and if that makes it into a monad, then would also help HoTT to take over the world.

Paolo Perrone (Jun 09 2020 at 15:28):

Tobias Fritz said:

Hmm, then it looks like we're almost back at the codomain (op)fibration: your $FRV$ assigns to every (say finite) set its fibre in the codomain fibration. So presumably your $FRV$ needs to be considered as a category, or at least as a groupoid. Which suggests that $FRV(FRV(X))$, assuming that it makes any sense, is likely to have even higher structure than that. We had some discussion in the thread for Bas's talk on the potential role of higher structure, but it seemed vague and perhaps ill-motivated. But if there's a way to define a version of $RV$ as a homotopy type rather than a set, and if that makes it into a monad, then would also help HoTT to take over the world.

Well, yes, and that would be beautiful. But I think even without the higher structure this can work.

Paolo Perrone (Jun 09 2020 at 15:28):

(All of this is motivated by my work on diagrams, Kan extensions and presheaves, which do have a higher structure - and form an opfibration.)

Paolo Perrone (Jun 09 2020 at 15:30):

Paolo Perrone said:

Now, the main technicality here is: in which category do we want this to happen?
Suppose we take Meas, and instead of the sets $N$ we take all standard Borel spaces, one representative for each isomorphism class. The question then translates to: which sigma-algebra do we put on $RV(X)$?

I have concrete ideas on how to do this, but I need more LaTeX than we have on Zulip - we could set up a meeting, or a document where whoever wants to participate can give their contribution.

Paolo Perrone (Jun 09 2020 at 16:01):

Paolo Perrone said:

Tobias Fritz said:

Hmm, then it looks like we're almost back at the codomain (op)fibration: your $FRV$ assigns to every (say finite) set its fibre in the codomain fibration. So presumably your $FRV$ needs to be considered as a category, or at least as a groupoid. Which suggests that $FRV(FRV(X))$, assuming that it makes any sense, is likely to have even higher structure than that. We had some discussion in the thread for Bas's talk on the potential role of higher structure, but it seemed vague and perhaps ill-motivated. But if there's a way to define a version of $RV$ as a homotopy type rather than a set, and if that makes it into a monad, then would also help HoTT to take over the world.

Well, yes, and that would be beautiful. But I think even without the higher structure this can work.

To elaborate on this point: in the Kan extension case, diagrams over a (1-)category form a 2-category. However, to get the monad we only use the underlying 1-category, and that's enough for the formalism to work. Still, exploring the higher structure can be interesting for "structural" purposes.

Tobias Fritz (Jun 09 2020 at 16:32):

I don't know about the case of Kan extensions and diagrams, but presumably you want your $FRV(X)$ to be independent of how many different finite sets $N$ there are in each isomorphism class, yes? Now if you define $FRV(X)$ to be the set (or class) of pairs $(N,f)$ where $N$ is a finite set and $f : N \to X$, then this does not have that invariance property. So presumably you either want to quotient by the equivalence relation in which $f_1 : N_1 \to X$ and $f_2 : N_2 \to X$ are identified whenever there is an isomorphism $N_1 \cong N_2$ that makes the triangle commute, or throw in all those isomorphisms as extra arrows making $FRV(X)$ into a groupoid. Right?

Paolo Perrone (Jun 09 2020 at 17:24):

Tobias Fritz said:

I don't know about the case of Kan extensions and diagrams, but presumably you want your $FRV(X)$ to be independent of how many different finite sets $N$ there are in each isomorphism class, yes? Now if you define $FRV(X)$ to be the set (or class) of pairs $(N,f)$ where $N$ is a finite set and $f : N \to X$, then this does not have that invariance property. So presumably you either want to quotient by the equivalence relation in which $f_1 : N_1 \to X$ and $f_2 : N_2 \to X$ are identified whenever there is an isomorphism $N_1 \cong N_2$ that makes the triangle commute, or throw in all those isomorphisms as extra arrows making $FRV(X)$ into a groupoid. Right?

Yes - and that's why above I was taking one set for each equivalence class. But I agree that that's a bit evil.

Alex Simpson (Jun 09 2020 at 17:28):

Paolo Perrone said:

Here's a concrete prototype of what I have in mind, for the case of finitely supported random variables.
[...]

What I'd like: the same, but not finitely supported.

Thank you Paolo for that explanation of what you are looking for. From my perspective, your finite construction lacks the important property of allowing one to talk about the joint law of two different $X,Y \in RV(A)$. In my talk, this was implemented by requiring $RV$ to preserve finite products. For me this property is non negotiable!

Paolo Perrone (Jun 09 2020 at 17:29):

Alex Simpson said:

Paolo Perrone said:

Here's a concrete prototype of what I have in mind, for the case of finitely supported random variables.
[...]

What I'd like: the same, but not finitely supported.

Thank you Paolo for that explanation of what you are looking for. From my perspective, your finite construction lacks the important property of allowing one to talk about the joint law of two different $X,Y \in RV(A)$. In my talk, this was implemented by requiring $RV$ to preserve finite products. For me this property is non negotiable!

I completely agree. I would like that monad to be strong monoidal, indeed.

Paolo Perrone (Jun 09 2020 at 17:41):

Tobias Fritz said:

I don't know about the case of Kan extensions and diagrams...

The main reason why I'm for now sweeping the higher structure under the rug is that if I didn't, we would have to equip the category $RV(X)$ with a sigma-algebra, or a quasi-Borel structure, or something similar. And I have no idea how to do it sensibly. (Any idea in this regard would be very welcome).

Tobias Fritz (Jun 09 2020 at 17:47):

In Alex's system, $RV(X)$ is just a set without any additional structure. In this spirit, we can perhaps wildly speculate that $RV(X)$ may just be a mere groupoid or higher homotopy type if things are set up correctly.

Alex Simpson (Jun 09 2020 at 18:00):

Tobias Fritz said:

In Alex's system, $RV(X)$ is just a set without any additional structure. In this spirit, we can perhaps wildly speculate that $RV(X)$ may just be a mere groupoid or higher homotopy type if things are set up correctly.

That would be setting things up "correctly"??! :slight_smile:

Tobias Fritz (Jun 09 2020 at 20:11):

I'm not in a position to set the moral standards here, but just to clarify: that was from the somewhat tongue-in-cheek perspective of "HoTT taking over the world". Of course your setting is correct by being very faithful to how probability theory is traditionally set up, and that has withstood the test of time very well. So feel free to consider such wild (and wacky) speculation as pure entertainment :yum: it most likely doesn't make any sense, but in the unlikely case that it does may be very interesting.

Tobias Fritz (Jun 09 2020 at 21:58):

So sorry @Alex Simpson if my statement was misleadimg. I certainly did not mean to claim that your framework is deficient in any sense; I like it a lot and have nothing significant to add to it :smile:

Alex Simpson (Jun 10 2020 at 06:49):

Tobias Fritz said:

So sorry Alex Simpson if my statement was misleadimg. I certainly did not mean to claim that your framework is deficient in any sense; I like it a lot and have nothing significant to add to it :smile:

Don't apologise. I was teasing. Seriously, there might indeed be something interesting in having a weak infinity-groupoid or HoTT version of probability theory. But also seriously, I don't buy into the idea that such a setting is a haven for the whole of mathematics. One of the subtexts in my talk is the "proper" treatment of equality in probability theory. Actual equality is always something probabilistically meaningful: almost sure equality, indistinguishability, being mutual modifications, ... Also equality in law enjoys a meta-theoretic substitutivity property, as at the end of the talk. This treatment of equality seems mathematically interesting, but it seems to have nothing to do with any higher groupoid structure.

Paolo Perrone (Jun 11 2020 at 22:44):

For those interested in why this comes from the analogy with diagrams and presheaves, here's the talk where I explain it.