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: learning: questions

Topic: Is the category Stoch closed?

Peva Blanchard (Jun 30 2024 at 22:45):

The category $Stoch$ is a Markov category. In particular, it is symmetric monoidal.

But is it closed?

I think it is not, but I'm not sure. My clue is

$$Stoch(B, C) \cong Stoch(1, [B,C])$$

I.e., we would have a natural bijection between the stochastic maps from $B$ to $C$ and the probability distributions on the (yet to be defined) object $[B,C]$. The latter, I guess, should be related to some space of functions from $B$ to $C$. But I don't see how to naturally map a stochastic map to a probability distribution on a function space (of course this is not an argument).

Eric M Downes (Jul 01 2024 at 01:32):

But I don't see how to naturally map a stochastic map to a probability distribution on a function space (of course this is not an argument).

I can only offer some help from the applied probability end of things, which I do know. By [[stochastic map]] I think you mean a conditional probability of a transition $p(x_n|x_{n-1})$, and not, a function with an explicit noise term $\omega$, like $x(t+1)=x(t) + \omega$. (If it is the latter, check out Ito Calculus for how to work with these.)

Are you familiar with the Chapman-Kolmogorov equation? This is an integral over a product of intermediate states $x_k\in X$ using Bayes Law. The markov chain assumption allows us to go from a probability over every possible path/history (e.g. a probability distribution in function space $X^X$) to a probability over the underlying space $X$, by explicitly saying that your history is encoded in your position $x\in X$.
$p(x|x_0)=\int_X \prod_{k=1}^n [p(x_k|x_{k-1})dx_k]$
Indeed I see things very much like the Chapman-Kolmogorov equation on the nLab page for Markov Category. It looks like instead of $p:X^2\to[0,1]$, they use the sigma-algebra $\Sigma\subset 2^X$ directly and you have $p:X\Sigma\to[0,1]$, which makes a certain amount of intuitive sense -- given where you are, what chance $p(B|x)$ do you have of ending up in some measurable set of $B\in\Sigma$ next turn. Whether some version of CK satisfies naturality conditions, I do not know.

Which is to say, given a Markov-Chain-Assumption-like rule, that maps $\mathbb{R}^{End(X)}\to\mathbb{R}^{\Sigma(X)X}$ does that help you?

Hope that helps; I too need to read up before Paolo's talk!

Matteo Capucci (he/him) (Jul 01 2024 at 07:43):

Stoch is not closed, and the obstruction goes the way you suspected: there are more distributions on $B \to C$ than maps $B \to \Delta C$. As an example, take $B=2$. Then $\Delta(2 \to C)= \Delta(C \times C)$ whereas $2 \to \Delta C = \Delta C \times \Delta C$. Then the former is bigger than the latter: there are distributions on $C \times C$ which are not the product of distributions on $C$.

Paolo Perrone (Jul 01 2024 at 07:56):

Matteo is correct, and that's the minimal counterexample.
Here is further intuition on that.
There are two ways to interpret the expression "random function":

• A function with a random outcome;
• A randomly chosen function.

In Haskell, if P is a probability monad, one would write the first type as X -> PY (i.e. a Kleisli morphism), and the second one as P(X -> Y) (i.e. the monad applied to the internal hom).
Now there is a difference between the two:

• In the first case, applying the same function to the same input twice may give a different result, because of the randomness (see my talk!)
• In the second case, once the function is randomly chosen, applying it to the same input gives the same output. Moreover, it is possible that there is correlation between its values on different inputs (as Matteo pointed out), which would be completely absent in the previous case.

In general, one can only hope that the subcategory of deterministic morphisms is Cartesian closed. Now, for the case of Stoch, this is also not true. But there are related categories, such as quasi-Borel spaces as well as particular topological spaces where this is true.

Paolo Perrone (Jul 01 2024 at 07:59):

Notice also that, in order to talk about the type P(X -> Y), where X -> Y are deterministic morphisms, it is sufficient that the subcategory of deterministic morphisms is cartesian closed, so this is not a great limitation.
In practice, types such as P(X -> Y) appear, for example, when we try to fit functions to data (nonparametrically).

Peva Blanchard (Jul 01 2024 at 10:49):

Great, thank you all for the answers!