2. Stochastic maps

Any conditional distribution $p(y|x)$ on finite sets $X$ and $Y$ can be represented as a matrix as follows. Let $𝒱X=\{\phi :X\to ℝ\}$ denote the vector space of real valued functions on $X$ and similarly for $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$ with entry $p(y|x)$ in column ${\delta }_x$ and row ${\delta }_y$. Matrix ${𝔪}_p$ is stochastic: 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 induces Euclidean 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. We identify of ${(𝒱X)}^{*}$ with $𝒱X$ using the Dirac basis without 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 map making diagram ${𝔪}^{⟂}$ of $𝔪$ with columns renormalized to sum to 1. The stochastic dual ${𝔪}^{\mathrm{♮}}$ is

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

Category $\mathrm{𝚂𝚝𝚘𝚌𝚑}$ is described in terms of braid-like generators and relations 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 faithful functor $𝒱:\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 stochastic map. 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 the terminal 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 projection induced 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 the posterior 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 assigns equal probability $p_{{\omega }^{\mathrm{♮}}}(x)=\frac{1}{|X|}$ to all of $X$’s elements, and can be characterized as the maximally uninformative distribution [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 stochastic matrices 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$ of stochastic map $\mathrm{V}\mathit{}f\mathrm{:}\mathrm{V}\mathit{}X\mathrm{\to }\mathrm{V}\mathit{}Y$ is conditional 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 the support are assigned equal probability, thereby treating them as an undifferentiated list. Dual ${(𝒱f)}^{\mathrm{♮}}$ thus generalizes the inverse 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 follows immediately 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$ as extrinsic noise. Although duals can be defined so that they implement Bayes’ rule with respect to other probability distributions, this paper restricts attention to the simplest possible renormalization of columns, Definition 2. The uniform distribution is convenient since it uses minimal prior knowledge (it depends only on the number of elements in the set) to generalize pre-images to the stochastic case, Proposition 2.

Title	2. Stochastic maps
Canonical name	2StochasticMaps
Date of creation	2014-04-23 0:51:47
Last modified on	2014-04-23 0:51:47
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	11
Author	rspuzio (6075)
Entry type	Feature
Classification	msc 60J20