11
$\begingroup$

$\def\unit{{\rm unit}}\def\join{{\rm join}}$It's well known that (discrete) probability distributions form a monad. Specifically, if we let $PX$ be the set of discrete probability distributions on elements of $X$, and notate them as a set of pairs $(x,p)$ such that $\sum p=1$, then we have natural transformations

$$\begin{align} \unit : X & \to PX \\ \unit : x & \mapsto \{ (x,1) \} \\ \\ \join: P(PX) & \to PX \\ \join: D & \mapsto \{(y,pq)| (x,p) \in D, (y,q)\in x \} \end{align}$$

that satisfy the monad laws.

Can probability distributions be made into a comonad as well? For that, we would need to provide natural transformations

$$\begin{align} {\rm counit} : PX & \to X \\ {\rm cojoin} : PX & \to P(PX) \end{align}$$

that satisfy the comonad laws. It seems that the role of counit can be played by mathematical expectation (as long as $X$ is an $\mathbb{R}$-module), but in that case what is the correct definition of cojoin?


Edit:

Zhen Lin pointed out in the comments that if you want to have counit being expectation, then you need an $\mathbb{R}$-module structure on $PX$ as well as on $X$. The module operations on $PX$ are inherited from those on $X$ in the following way:

Addition

$$D_1 + D_2 = \{ (x+y,pq) | (x,p)\in D_1, (y,q)\in D_2\}$$

Multiplication by a scalar

$$qD = \{ (qx,p) | (x,p)\in D \}$$

  • 0
    Your description of the unit of $P$ monad seems to be incorrect. Do you mean to have $1 / |{X}|$ instead of $1$? In that case, I suppose you must also assume that $X$ is finite.2012-06-28
  • 1
    No - here $X$ is a set (the sample space), and ${\rm unit}(x)$ is the trivial distribution over $x\in X$, i.e. the distribution which always selects $x$.2012-06-28
  • 0
    Ah, yes. That makes sense. I don't think can make expectation into the comonad unit, because $P X$ is not a vector space even when $X$ is.2012-06-28
  • 0
    It's possible to define a vector space structure on $PX$. I'll edit the question to include that.2012-06-28
  • 0
    Your formula for $D_1 + D_2$ will misbehave when there are $x_1, x_2, y_1, y_2$ such that $x_1 + y_1 = x_2 + y_2$.2012-06-28
  • 0
    Yes. There's an implicit assumption being made that like terms are collected and their probabilities summed. An alternative is to consider the containing data structure to be a multiset rather than a set, I suppose. You're touching on the problem of [restricted monads](http://okmij.org/ftp/Haskell/types.html#restricted-datatypes) which has been the bane of implementors of functional programming languages for the last 15 or so years :)2012-06-28
  • 0
    Either way, it doesn't define a vector space structure. $D - D \ne 0$ in general.2012-06-28
  • 0
    Good point. Perhaps I don't actually need the vector space structure at all - to compute expectations you just need scalar multiplication and addition. It seems as though an $\mathbb{R}$-module is probably sufficient. More edits coming...2012-06-28
  • 0
    An $\mathbb{R}$-module is the same thing as a vector space over $\mathbb{R}$. I don't see any way of making scalar multiplication and addition behave nicely – even if we pass from rings to [rigs](http://en.wikipedia.org/wiki/Semiring).2012-06-28
  • 0
    But crucially, it doesn't have a requirement for additive inverses, so that fact that $D-D\neq 0$ is not important, because we haven't even bothered to define $D-D$.2012-06-28
  • 0
    Oops, I don't mean $\mathbb{R}$-module. I'm not exactly sure what structure I'm looking for. Something like an additive abelian group combined with an $\mathbb{R}$-set, I think.2012-06-28
  • 0
    I've already explained why your proposed addition cannot be the addition operation of an abelian group. There _is_ an algebraic structure for which your functor is a comonad – namely the structure of a $P$-algebra. But this is completely tautological.2012-06-28
  • 0
    This is an interesting question. Could you tell us your motivation? Is it just plain curiosity or do you have a patricular application in mind where you need some (comonadic) notion of composition on probabilities? I have not found an answer yet. One thought I had was, perhaps you could define cojoin to be a conditional probability with itself? e.g. `cojoin [(10, 0.25), (5, 0.75)] = [([(10, 0.0625), (5, 0.1875)], 0.25), ([(10, 0.1875), (5, 0.5625)], 0.75)]`, but this does not satisfy the laws (only right identity)2013-07-26
  • 0
    Thinking "contextually" (as one might do to give a computational interpretation for comonads), cojoin is then like saying, "what is the probability of me following this path given that my 'context' is that I have already taken a particular path".2013-07-26
  • 0
    @dorchard I don't remember what my motivation was when I asked this - and I don't think I ever resolved the question one way or the other, either. I'll try to think about it over the weekend!2013-07-26
  • 0
    @ChrisTaylor With the module definition you give in your question there is a comonad-*like* structure which has the associativity and right-unit laws, but not left unit, where $\delta\, D \mapsto \{ \{ (x, q) \, | \, (y, q) \in D \} | \, (x, p) \in D \}$, e.g., $\delta \{(1, 0.25), (2, 0.75)\} \mapsto \{\{(1, 0.25), (1, 0.75)\}, \{(2, 0.25), (2, 0.75)\}\}$. There are different definitions of the module and $\delta$ which give a comonad-like structure with a left-unit, however I have not yet found one that has both units.2013-08-02
  • 0
    It's worth noting that `counit` could also be *sampling* rather than expectation, if you use a sampling function-based probability monad à la [Park et al 2008](https://www.cs.cmu.edu/~fp/papers/toplas08.pdf).2015-11-22
  • 0
    I don't think `counit` is valid. `counit` would have to be a natural transformation. Take a uniform distribution over $\{-1,1\}$. If you take the expected value you get $0$, and then square that and you get $0$. Square it first and you get a guaranteed value of $1$, square that and you get $1$. Therefore, `counit` isn't a natural transformation.2016-03-03

0 Answers 0