This question is mostly for the purpose of learning how to reason in category theory.

Consider the category of finite stochastic maps. I imagine this is something fairly standard, but I've given a definition below in case it's not. I'll call this category FinStochMap.

Products, coproducts, and the initial and final objects in FinStochMap are the same as in FinSet. In FinStochMap, a morphism from the terminal object to an object $A$ can be seen as a probability distribution over $A$. To be concrete, consider a morphism in FinStochMap, $f:\{*\}\to A$. This gives us a set of numbers $p(a|*)$ for every $a\in A$, such that $\sum_{a\in A} p(a|*)=1$, so we can interpret $p(a|*)$ as the probability of $a$.

In probability theory, an important kind of probability distribution is the uniform distribution. Among other things, this is the only distribution on a finite set that is invariant to permutations of its elements.

My question is, is there a category-theoretic way to pick out the uniform probability distributions in FinStochMap? Are they the morphisms from the terminal object that obey a certain universal property, and if so, what is it?

Definition of FinStochMap. By FinStochMap I mean the category where the objects are finite sets, and the morphisms are conditional probability distributions (or Markov kernels if you prefer), i.e. a morphism $f:A\to B$ is a function $p_f:A\times B \to [0,1]$, with elements written $p_f(b|a)$, such that $\sum_{b\in B} p(b|a)=1$ for all $a\in A$. The composition rule is that for $f:A\to B$ and $g:B\to C$, the composition $f;g:A\to C$ is given by $$ p_{f;g}(c|a) = \sum_{b\in B} p_f(b|a)p_g(c|b). $$ An identity morphism $I_A:A\to A$ is given by $p_{I_A}(a|a') = 1$ if $a=a'$, and 0 otherwise.

Related question by me: expectations in FinStochMap.

  • $\begingroup$ The morphisms of your category are not probability distributions but transition kernels, and the objects are not distributions either but probability spaces. So asking which ones are uniform probability distributions is not strictly meaningful. Can you be more specific about what it means for a transition kernel to be uniform? $\endgroup$ – Jack M Feb 12 at 14:36
  • $\begingroup$ @JackM a conditional probability distribution and a Markov kernel are the same thing. I defined what I meant by a probability distribution: it's a morphism from the terminal object in FinStochMap to an object in FinStochMap. $\endgroup$ – Nathaniel Feb 12 at 14:38
  • $\begingroup$ You're right, I read too quickly. $\endgroup$ – Jack M Feb 12 at 14:40
  • $\begingroup$ @JackM just in case, I expanded a bit in the question on why such a morphism can be seen as a probability distribution. $\endgroup$ – Nathaniel Feb 12 at 14:42
  • 2
    $\begingroup$ I don't know if this is what you want, but the automorphisms on an object in $\mathbf{FinStochMap}$ are precisely the permutations of the set. So the uniform distributions can be defined categorically simply by saying they're automorphism invariant. That's kind of boring though. Let me also advertise my (semi-related) paper Purity through Factorisation. $\endgroup$ – Oscar Cunningham Feb 12 at 16:21

This is a self-answer based on Oscar Cunningham's comment.

The automorphisms in FinStochMap are exactly the permutations of a set. That is, if $f:A\to A$ is an isomorphism then each $p_f(a'|a)$ must either be 0 or 1, with exactly one 1 on each row and each column, if we view it as a matrix. Then we can just define the uniform distributions as those distributions that are automorphism invariant.

That is, a morphism $u_A:\{*\}\to A$ is a uniform distribution if, for every automorphism $f:A\to A$ we have $u_A f = u_A$.

Equivalently, we could say that $u_A:\{*\}\to A$ is a uniform distribution if for every pair of isomorphisms $f, g:A\to B$ we have $u_A f = u_A g$.

In his comment Oscar Cunningham worried that this would be 'boring' (i.e. unsatisfying), but I think it's fine - it's a perfectly good category-theoretic definition, because it only relies on the 'external' features of the morphisms, not their internal structure, and it allows us to see that (for example) FinSet does not have the analogous feature. (In FinSet the morphisms from the terminal object correspond to set membership, and only the terminal object has an automorphism-invariant member.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.