In probability theory, a stochastic map between sets $X$ and $Y$ is a way of assigning numbers to elements $(x,y)$ of $X\times Y$ to model a probabilistic transition from $X$ to $Y$. 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 $X$ and $Y$ be sets. A stochastic map or stochastic matrix from $X$ to $Y$ is a function $f:X\times Y\to[0,1]$, whose entries we denote by $f(y|x)$, such that
The quantity $f(y|x)$ can be thought of as a transition probability or conditional probability of moving to $y$ if the current state or current knowledge is $x$.
The product of stochastic matrices is again a stochastic matrix (and so they form a category, see below). Given stochastic matrices $f$ from $X$ to $Y$ and $g$ from $Y$ to $Z$, the entries of the product are
Its probabilistic interpretation is that the random transition from $x$ to $y$ and from $y$ to $z$ are independent, as in a Markov process (hence their product is taken), and all intermediate states $y$ are mutually exclusive, so that the probabilities are summed over all $y$. 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.
Let $(X,p)$ and $(Y,q)$ be discrete probability spaces, i.e. sets equipped with a functions $p:X\to[0,1]$ and $q:Y\to[0,1]$ which sum to one. A stochastic map $f$ from $X$ to $Y$ is called measure-preserving if for every $y\in Y$,
(Compare this with the analogous notion for stochastic kernels.)
The identity function on a set $X$ defines a stochastic map as follows,
for every $x,x'\in X$. This gives the identity morphisms in the categories of stochastic maps below.
More generally, let $f:X\to Y$ be a function. We can define the stochastic map $\delta_f:X\to Y$ as follows,
for every $x\in X$ and $y\in Y$. Intuitively, this kernel represents the deterministic transition, from $x$ to $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.)
A stochastic map can be equivalently written as a function where $D$ 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.)
The category of finite sets and stochastic matrices between them is often called FinStoch, and is an example of a Markov category.
The category of finite probability spaces and measure-preserving stochastic matrices between them form a category as well.
See also:
Wikipedia, Stochastic matrix
James Fullwood, Arthur Parzygnat, Section 4 of: The information loss of a stochastic map, Entropy 2021 23(8) 1021 [arXiv:2107.01975, doi:10.3390/e23081021]
Last revised on April 19, 2024 at 00:52:41. See the history of this page for a list of all contributions to it.