nLab stochastic map




In probability theory, a stochastic map between sets XX and YY is a way of assigning numbers to elements (x,y)(x,y) of X×YX\times Y to model a probabilistic transition from XX to YY. The entries of a stochastic map form a matrix often called a stochastic matrix or transition matrix, which has nonnegative entries whose columns (or rows, depending on the convention) sum to one.

A generalization to arbitrary measurable spaces is called a stochastic kernel (or Markov kernel). (Sometimes the term stochastic map is used to denote a stochastic kernel.)

If a stochastic map also preserves the uniform distribution, then it is called a doubly stochastic map. This means that the stochastic matrix has not just columns but also rows which sum to unity, then called a doubly stochastic matrix.


Let XX and YY be sets. A stochastic map or stochastic matrix from XX to YY is a function f:X×Y[0,1]f:X\times Y\to[0,1], whose entries we denote by f(y|x)f(y|x), such that

  • For all xXx\in X and yYy\in Y, the number f(y|x)f(y|x) is non-negative;
  • For all xXx\in X, the numbers f(y|x)f(y|x) are nonzero for only finitely many yYy\in Y;
  • For all xXx\in X, Yf(y|x)=1\sum_Y f(y|x) = 1.

The quantity f(y|x)f(y|x) can be thought of as a transition probability or conditional probability of moving to yy if the current state or current knowledge is xx.


The product of stochastic matrices is again a stochastic matrix (and so they form a category, see below). Given stochastic matrices ff from XX to YY and gg from YY to ZZ, the entries of the product are

(gf)(z|x)= Yg(z|y)f(y|x). (g\circ f) (z|x) = \sum_Y g(z|y)\,f(y|x) .

Its probabilistic interpretation is that the random transition from xx to yy and from yy to zz are independent, as in a Markov process (hence their product is taken), and all intermediate states yy are mutually exclusive, so that the probabilities are summed over all yy. This formula is sometimes called the Chapman-Kolmogorov formula. (See also the generalization to Markov kernels.)

As identity matrices are stochastic, stochastic matrices form a category, see below.

Measure-preserving stochastic maps

Let (X,p)(X,p) and (Y,q)(Y,q) be discrete probability spaces, i.e. sets equipped with a functions p:X[0,1]p:X\to[0,1] and q:Y[0,1]q:Y\to[0,1] which sum to one. A stochastic map ff from XX to YY is called measure-preserving if for every yYy\in Y,

xf 1(y)p(x)=q(y). \sum_{x\in f^{-1}(y)} p(x) = q(y) .

(Compare this with the analogous notion for stochastic kernels.)

Stochastic maps from deterministic functions

The identity function on a set XX defines a stochastic map as follows,

δ(x|x)=δ x,x{1 x=x; 0 xx \delta(x'|x) = \delta_{x,x'} \begin{cases} 1 & x'=x ; \\ 0 & x'\neq x \end{cases}

for every x,xXx,x'\in X. This gives the identity morphisms in the categories of stochastic maps below.

More generally, let f:XYf:X\to Y be a function. We can define the stochastic map δ f:XY\delta_f:X\to Y as follows,

δ f(y|x)=δ f(x),y={1 f(x)=y; 0 f(x)y \delta_f(y|x) = \delta_{f(x),y} = \begin{cases} 1 & f(x) = y ; \\ 0 & f(x) \ne y \end{cases}

for every xXx\in X and yYy\in Y. Intuitively, this kernel represents the deterministic transition, from xx to f(x)f(x) with probability one. This construction induces a functor from the category Set to the categories of stochstic maps below. (Compare with the analogous construction for stochastic kernels.)

As Kleisli morphisms

A stochastic map can be equivalently written as a function where DD denotes the distribution monad. Therefore, stochastic maps can be seen as the Kleisli morphisms of the distribution monad on Set.

(Compare with the analogous statement for stochastic kernels.)

Categories of stochastic maps


See also:

category: probability

Last revised on April 19, 2024 at 00:52:41. See the history of this page for a list of all contributions to it.