2. Stochastic maps

Any conditional distribution $p(y|x)$ on finite sets $X$ and $Y$ can berepresented as a matrix as follows. Let $𝒱X=\{\phi :X\to ℝ\}$ denote the vector space of real valued functions on $X$ and similarlyfor $Y$. $𝒱X$ is equipped with Dirac basis$\{{\delta }_x:X\to ℝ|x\in X\}$, where

Given a conditional distribution $p(y|x)$ construct matrix ${𝔪}_p$ withentry $p(y|x)$ in column ${\delta }_x$ and row ${\delta }_y$. Matrix ${𝔪}_p$ isstochastic: it has nonnegative entries and its columns sum to 1.Alternatively, given a stochastic matrix $𝔪:𝒱X\to 𝒱Y$, we can recover the conditional distribution. The Dirac basis inducesEuclidean metric

$$⟨\bullet |\bullet ⟩:𝒱X\otimes 𝒱X\to ℝ:⟨\sum {\alpha }_x{\delta }_x|\sum {\beta }_x{\delta }_x⟩=\sum {\alpha }_x{\beta }_x$$(1)

which identifies vector spaces with their duals $𝒱X\approx {(𝒱X)}^{*}$. Let $p_{𝔪}(y|x):=⟨{\delta }_y|𝔪({\delta }_x)⟩$.

Definition 2.

The category of stochastic maps $\mathrm{𝚂𝚝𝚘𝚌𝚑}$ has function spaces$𝒱X$ for objects and stochastic matrices $𝔪:𝒱X\to 𝒱Y$ with respect to Dirac bases for arrows. Weidentify of ${(𝒱X)}^{*}$ with $𝒱X$ using the Dirac basiswithout further comment below.

Definition 3.

The dual of surjective stochastic map $𝔪:𝒱X\to 𝒱Y$ is the composition ${𝔪}^{\mathrm{♮}}:=𝒱Y\stackrel{{𝔪}^{*}\circ ren}{\to }𝒱X$, where $ren$ is the unique mapmaking diagram${𝔪}^{⟂}$ of $𝔪$ with columns renormalized to sum to 1. Thestochastic dual ${𝔪}^{\mathrm{♮}}$ is

commute. Precomposing ${𝔪}^{*}$ with $ren$ renormalizes itscolumns to sum to 1. The stochastic dual of a stochastic transform isstochastic; further, if $𝔪$ is stochastic then${({𝔪}^{\mathrm{♮}})}^{\mathrm{♮}}=𝔪$.

Category $\mathrm{𝚂𝚝𝚘𝚌𝚑}$ is described in terms of braid-like generators andrelations in [2]. A more general, but also more complicated,category of conditional distributions was introduced by Giry [3],see [5].

Example 1 (deterministic functions).

Let $\mathrm{𝙵𝚂𝚎𝚝}$ be the category of finite sets. Define faithfulfunctor $𝒱:\mathrm{𝙵𝚂𝚎𝚝}\to \mathrm{𝚂𝚝𝚘𝚌𝚑}$ taking set $X$ to$𝒱X$ and function $f:X\to Y$ to stochastic map$𝒱f:𝒱X\to 𝒱Y:{\delta }_x\mapsto {\delta }_{f(x)}$. It is easy to see that $𝒱(X\times Y)=𝒱X\otimes 𝒱Y$ and $𝒱(X\cup Y)=𝒱X\times 𝒱Y$.

We introduce special notation for commonly used functions:

• Set inclusion.For any inclusion $i:X\hookrightarrow Y$ of sets, let $\iota :=𝒱i:𝒱X\to 𝒱Y$ denote the corresponding stochasticmap. Two important examples are

  • Point inclusion.Given $x\in X$ define ${\iota }_x:ℝ\to 𝒱X:1\mapsto {\delta }_x$.

  • Diagonal map.Inclusion $\mathrm{\Delta }:X\hookrightarrow X\times X:x\mapsto (x,x)$induces ${\iota }_{\mathrm{\Delta }}:𝒱X\to 𝒱X\otimes 𝒱X:{\delta }_x\mapsto {\delta }_x\otimes {\delta }_x$.

• Terminal map.Let ${\omega }_X:𝒱X\to ℝ:{\delta }_x\mapsto 1$ denote theterminal map induced by $X\to \{\bullet \}$.

• Projection.Let ${\pi }_{XY,X}:𝒱X\otimes 𝒱Y\to 𝒱X:{\delta }_x\otimes {\delta }_y\mapsto {\delta }_x$ denote the projectioninduced by $p{r}_{X\times Y,X}:X\times Y\to X:(x,y)\mapsto x$.

Proposition 1 (dual is Bayes over uniform distribution).

The dual of a stochastic map applies Bayes rule to compute theposterior distribution $\mathrm{⟨}{\mathrm{m}}^{\mathrm{♮}}\mathrm{(}{\delta }_y\mathrm{)}\mathrm{|}{\delta }_x\mathrm{⟩}\mathrm{=}{p}_{\mathrm{m}}\mathrm{(}x\mathrm{|}y\mathrm{)}$ using the uniform probability distribution.

Proof:The uniform distribution is the dual ${\omega }_X^{\mathrm{♮}}:ℝ\to 𝒱X:1\mapsto \frac{1}{|X|}{\sum }_x{\delta }_x$of the terminal map ${\omega }_X:𝒱X\to ℝ$. It assignsequal probability $p_{{\omega }^{\mathrm{♮}}}(x)=\frac{1}{|X|}$ to all of $X$’selements, and can be characterized as the maximally uninformativedistribution [4]. Let $𝔪:𝒱X\to 𝒱Y$.The normalized transpose is

$${𝔪}^{\mathrm{♮}}({\delta }_y)=\sum _x\frac{p_{𝔪}(y|x)}{{\sum }_{x^{\prime }}{p}_{𝔪}(y|x^{\prime })}{\delta }_x=\sum _x\frac{p_{𝔪}(y|x)\cdot p_{{\omega }^{\mathrm{♮}}}(x)}{{\sum }_{x^{\prime }}{p}_{𝔪}(y|x^{\prime })p_{{\omega }^{\mathrm{♮}}}(x^{\prime })}{\delta }_x=\sum _x{p}_{𝔪}(x|y)\cdot {\delta }_x.\mathrm{■}$$

Remark 1.

Note that $p_{𝔪}(x|y):=⟨{𝔪}^{\mathrm{♮}}({\delta }_y)|{\delta }_x⟩\ne ⟨{\delta }_y|𝔪({\delta }_x)⟩=:p_{𝔪}(y|x)$.Dirac’s bra-ket notation must be used with care since stochasticmatrices are not necessarily symmetric [1].

Corollary 2 (preimages).

The dual ${\mathrm{(}\mathrm{V}\mathit{}f\mathrm{)}}^{\mathrm{♮}}\mathrm{:}\mathrm{V}\mathit{}Y\mathrm{\to }\mathrm{V}\mathit{}X$ ofstochastic map $\mathrm{V}\mathit{}f\mathrm{:}\mathrm{V}\mathit{}X\mathrm{\to }\mathrm{V}\mathit{}Y$ isconditional distribution

(2)

Proof:By the proof of Proposition 1

$${(𝒱f)}^{\mathrm{♮}}({\delta }_y)=\frac{1}{|f^{-1}(y)|}\sum _{\{x|f(x)=y\}}{\delta }_x.\mathrm{■}$$

The support of $p_{𝒱f}(X|y)$ is $f^{-1}(y)$. Elements in thesupport are assigned equal probability, thereby treating them as anundifferentiated list. Dual ${(𝒱f)}^{\mathrm{♮}}$ thus generalizes theinverse image $f^{-1}:Y\to {\underset{¯}{2}}^X$. Conveniently however,the dual ${(𝒱X)}^{\mathrm{♮}}$ simply flips the domain and range of$𝒱f$, whereas the inverse image maps to powerset ${\underset{¯}{2}}^X$,an entirely new object.

Corollary 3 (marginalization with respect to uniform distribution).

Precomposing $\mathrm{V}\mathit{}X\mathrm{\otimes }\mathrm{V}\mathit{}Y\stackrel{\mathrm{m}}{\mathrm{\to }}\mathrm{V}\mathit{}Z$with the dual ${\pi }_X^{\mathrm{♮}}$ to $\mathrm{V}\mathit{}X\mathrm{\otimes }\mathrm{V}\mathit{}Y\stackrel{{\pi }_X}{\mathrm{\to }}\mathrm{V}\mathit{}X$ marginalizes $p_{\mathrm{m}}\mathrm{(}z\mathrm{|}x\mathrm{,}y\mathrm{)}$over the uniform distribution on $Y$.

Proof:By Corollary 2 we have ${\pi }_X^{\mathrm{♮}}:𝒱X\to 𝒱X\otimes 𝒱Y:{\delta }_y\mapsto \frac{1}{|Y|}{\sum }_{y\in Y}{\delta }_x\otimes {\delta }_y$. It followsimmediately that

$$p_{𝔪\circ {\pi }_X^{\mathrm{♮}}}(z|x)=\frac{1}{|Y|}\sum _{y\in Y}{p}_{𝔪}(z|x,y).\mathrm{■}$$

Precomposing with ${\pi }_X^{\mathrm{♮}}$ treats inputs from $Y$ asextrinsic noise. Although duals can be defined so that theyimplement Bayes’ rule with respect to other probability distributions,this paper restricts attention to the simplest possible renormalizationof columns, Definition 2. The uniform distribution isconvenient since it uses minimal prior knowledge (it depends only on thenumber of elements in the set) to generalize pre-images to the stochasticcase, Proposition 2.