2. Stochastic maps
Any conditional distribution on finite sets and can be represented as a matrix as follows. Let denote the vector space of real valued functions on and similarly for . is equipped with Dirac basis , where
Given a conditional distribution construct matrix with entry in column and row . Matrix is stochastic: it has nonnegative entries and its columns sum to 1. Alternatively, given a stochastic matrix , we can recover the conditional distribution. The Dirac basis induces Euclidean metric
which identifies vector spaces with their duals . Let .
The category of stochastic maps has function spaces for objects and stochastic matrices with respect to Dirac bases for arrows. We identify of with using the Dirac basis without further comment below.
commute. Precomposing with renormalizes 11If is not surjective, i.e. if one of the rows has all zero entries, then the renormalization is not well-defined. its columns to sum to 1. The stochastic dual of a stochastic transform is stochastic; further, if is stochastic then .
Example 1 (deterministic functions).
Let be the category of finite sets. Define faithful functor taking set to and function to stochastic map . It is easy to see that and .
We introduce special notation for commonly used functions:
Proposition 1 (dual is Bayes over uniform distribution).
The dual of a stochastic map applies Bayes rule to compute the posterior distribution using the uniform probability distribution.
Proof: The uniform distribution is the dual of the terminal map . It assigns equal probability to all of ’s elements, and can be characterized as the maximally uninformative distribution . Let . The normalized transpose is
Corollary 2 (preimages).
The dual of stochastic map is conditional distribution
The support of is . Elements in the support are assigned equal probability, thereby treating them as an undifferentiated list. Dual thus generalizes the inverse image . Conveniently however, the dual simply flips the domain and range of , whereas the inverse image maps to powerset , an entirely new object.
Corollary 3 (marginalization with respect to uniform distribution).
Precomposing with the dual to marginalizes over the uniform distribution on .
Proof: By Corollary 2 we have . It follows immediately that
Precomposing with treats inputs from 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.
- 1 P A M Dirac (1958): The Principles of Quantum Mechanics. Oxford University Press.
- 2 Tobias Fritz (2009): A presentation of the category of stochastic matrices. arXiv:0902.2554v1 .
- 3 M Giry (1981): A categorical approach to probability theory. In B Banaschewski, editor: Categorical Aspects of Topology and Analysis, Springer.
- 4 E T Jaynes (1957): Information theory and statistical mechanics. Phys. Rev. 106(4), pp. 620–630.
- 5 P Panangaden (1998): Probabilistic relations. In C Baier, M Huth, M Kwiatkowska & M Ryan, editors: PROBMIV’98, pp. 59–74.
|Title||2. Stochastic maps|
|Date of creation||2014-04-23 0:51:47|
|Last modified on||2014-04-23 0:51:47|
|Last modified by||rspuzio (6075)|