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
(1) |
which identifies vector spaces with their duals . Let .
Definition 2.
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.
Definition 3.
The dual of surjective stochastic map is the composition , where is the unique map
making diagram
of with columns renormalized to sum to 1. The
stochastic dual is
![](information-theoretic-distributed-measurement-2.1.png)
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 .
Category 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 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:
-
•
Set inclusion. For any inclusion of sets, let denote the corresponding stochastic map. Two important examples are
-
–
Point inclusion. Given define .
-
–
Diagonal map. Inclusion induces .
-
–
-
•
Terminal map. Let denote the terminal map induced by .
-
•
Projection
. Let denote the projection induced by .
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
[4]. Let .
The normalized transpose
is
Remark 1.
Corollary 2 (preimages).
The dual of stochastic map is conditional distribution
(2) |
Proof:
By the proof of Proposition 1
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.
References
- 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 |
---|---|
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 |