Markov kernel

In probability theory, a Markov kernel (also known as a stochastic kernel or probability kernel) is a map that plays the role, in the general theory of Markov processes, that the transition matrix does in the theory of Markov processes with a finite state space.^[1]

Formal definition

Let ${\displaystyle (X,{\mathcal {A}}),(Y,{\mathcal {B}})}$  be measurable spaces. A Markov kernel ${\displaystyle \kappa :X\to Y}$  with source ${\displaystyle (X,{\mathcal {A}})}$  and target ${\displaystyle (Y,{\mathcal {B}})}$  is a map ${\displaystyle \kappa :{\mathcal {B}}\times X\to [0,1]}$  with the following properties:

1. For every (fixed) ${\displaystyle B\in {\mathcal {B}}}$ , the map ${\displaystyle x\mapsto \kappa (B,x)}$  is ${\displaystyle {\mathcal {A}}}$ -measurable
2. For every (fixed) ${\displaystyle x\in X}$ , the map ${\displaystyle B\mapsto \kappa (B,x)}$  is a probability measure on ${\displaystyle (Y,{\mathcal {B}})}$ 

In other words it associates to each point ${\displaystyle x\in X}$  a probability measure ${\displaystyle \kappa (dy|x):B\mapsto \kappa (B,x)}$  on ${\displaystyle (Y,{\mathcal {B}})}$  such that, for every measurable set ${\displaystyle B\in {\mathcal {B}}}$ , the map ${\displaystyle x\mapsto \kappa (B,x)}$  is measurable with respect to the ${\displaystyle \sigma }$ -algebra ${\displaystyle {\mathcal {A}}.}$ ^[2].

Examples

Simple random walk on the integers

Take ${\displaystyle X=Y=\mathbb {Z} ,{\mathcal {A}}={\mathcal {B}}={\mathcal {P}}(\mathbb {Z} )}$  (the power set of ${\displaystyle \mathbb {Z} }$ ). Then a Markov kernel is fully determined by the probability it assigns to singleton sets for each ${\displaystyle n\in X=\mathbb {Z} }$ .

${\displaystyle \kappa (B|n)=\sum _{m\in B}\kappa (\{m\}|n),\qquad \forall n\in \mathbb {Z} ,\,\forall B\in {\mathcal {B}}}$ .

Now the random walk ${\displaystyle \kappa }$  that goes to the right with probability ${\displaystyle p}$  and to the left with probability ${\displaystyle 1-p}$  is defined by

${\displaystyle \kappa (\{m\}|n)=p\delta _{m,n+1}+(1-p)\delta _{m,n-1},\quad \forall n,m\in \mathbb {Z} }$ 

where ${\displaystyle \delta }$  is the Kronecker delta. The transition probabilities ${\displaystyle P(m|n)=\kappa ({m}|n)}$  for the random walk are equivalent to the Markov kernel.

General Markov processes with countable state space

More generally take ${\displaystyle X}$  and ${\displaystyle Y}$  both countable and ${\displaystyle {\mathcal {A}}={\mathcal {P}}(X),\ {\mathcal {B}}={\mathcal {P}}(Y)}$ . Again a Markov kernel is defined by the probability it assigns to singleton sets for each ${\displaystyle i\in X}$ 

${\displaystyle \kappa (B|i)=\sum _{j\in B}\kappa (\{j\}|i),\qquad \forall i\in X,\,\forall B\in {\mathcal {B}}}$ ,

We define a Markov process by defining a transition probability ${\displaystyle P(j|i)=K_{ji}}$  where the numbers ${\displaystyle K_{ji}}$  define a (countable) stochastic matrix ${\displaystyle (K_{ji})}$  i.e.

${\displaystyle {\begin{aligned}K_{ji}&\geq 0,\qquad &\forall (j,i)\in Y\times X,\\\sum _{j\in Y}K_{ji}&=1,\qquad &\forall i\in X.\\\end{aligned}}}$ 

We then define

${\displaystyle \kappa (\{j\}|i)=K_{ji}=P(j|i),\qquad \forall i\in X,\quad \forall B\in {\mathcal {B}}}$ .

Again the transition probability, the stochastic matrix and the Markov kernel are equivalent reformulations.a

Markov kernel defined by a kernel function and a measure

If ${\displaystyle \nu }$  is a measure on ${\displaystyle (Y,{\mathcal {B}})}$  and ${\displaystyle k:Y\times X\to [0,\infty ]}$  is a measurable function with respect to the product ${\displaystyle \sigma }$ -algebra ${\displaystyle {\mathcal {A}}\otimes {\mathcal {B}}}$  such that

${\displaystyle \int _{Y}k(y,x)\nu (\mathrm {d} y)=1,\qquad \forall x\in X}$ 

then ${\displaystyle \kappa (dy|x)=k(y,x)\nu (dy)}$  i.e. the mapping

${\displaystyle {\begin{cases}\kappa :{\mathcal {B}}\times X\to [0,1]\\\kappa (B|x)=\int _{B}k(x,y)\nu (\mathrm {d} y)\end{cases}}}$ 

defines a Markov kernel.^[3]. This example generalises the countable Markov process example where ${\displaystyle \nu }$  was the counting measure, but other important examples are convolution kernels like the Markov kernel defined by the heat equation e.g. the Gaussian on ${\displaystyle X=Y=\mathbb {R} }$  with ${\displaystyle \nu (dx)=dx}$  standard Lebesgue measure and

${\displaystyle k_{t}(y,x)={\frac {1}{{\sqrt {2\pi }}t}}e^{-(y-x)^{2}/(2t^{2})}}$ .

Measurable functions.

Take ${\displaystyle (X,{\mathcal {A}})}$  and ${\displaystyle (B,{\mathcal {B}})}$  arbitrary measurable spaces, and let ${\displaystyle f:X\to Y}$  be a measurable function. Now define ${\displaystyle \kappa (dy|x)=\delta _{f(x)}(dy)}$  i.e.

${\displaystyle \kappa (B|x)=\mathbf {1} _{B}(f(x))=\mathbf {1} _{f^{-1}(B)}(x)}$  for all ${\displaystyle B\in {\mathcal {B}}}$ .

Note that the indicator function ${\displaystyle \mathbf {1} _{f^{-1}(B)}}$  is ${\displaystyle {\mathcal {A}}}$ -measurable for all ${\displaystyle B\in {\mathcal {B}}}$  iff ${\displaystyle f}$  is measurable.

This example allows us to think of a Markov kernel as a generalised function with a (in general) random rather than certain value.

Galton–Watson process

As a less obvious example, take ${\displaystyle X=\mathbb {N} ,{\mathcal {A}}={\mathcal {P}}(\mathbb {N} ),}$ , and ${\displaystyle (Y,{\mathcal {B}})}$  the real numbers ${\displaystyle \mathbb {R} }$  with the standard sigma algebra of Borel sets. Then

${\displaystyle \kappa (B|n)={\begin{cases}\mathbf {1} _{B}(0)&n=0\\\Pr(\xi _{1}+\cdots +\xi _{x}\in B)&n\neq 0\\\end{cases}}}$ 

with i.i.d. random variables ${\displaystyle \xi _{i}}$  (usually with mean 0) and where ${\displaystyle \mathbf {1} _{B}}$  is the indicator function. For the simple case of coin flips this models the different levels of a Galton board.

Composition of Markov Kernels and the Markov Categorie

Given measurable spaces ${\displaystyle (X,{\mathcal {A}})}$ , ${\displaystyle (Y,{\mathcal {B}})}$  and ${\displaystyle (Z,{\mathcal {C}})}$ , and probability kernels ${\displaystyle \kappa :X\to Y}$  and ${\displaystyle \lambda :Y\to Z}$ , we can define a composition ${\displaystyle \lambda \circ \kappa :X\to Z}$  by

${\displaystyle (\lambda \circ \kappa )(dz|x)=\int _{Y}\lambda (dz|y)\kappa (dy|x)}$ 

The composition is associative by Tonelli's theorem and the identity function considered as Markov kernel (i.e. the delta measure ${\displaystyle \kappa _{1}(dx'|x)=\delta _{x}(dx')}$ ) is the unit for this composition.

This composition defines the structure of a category on the measurable spaces with Markov kernels as morphisms first defined by Lawvere ^[4]. The category has the empty set as initial object and the one point set ${\displaystyle *}$  as the terminal object. A probability measure on a measurable space ${\displaystyle (X,{\mathcal {A}})}$  is the same thing as a morphism ${\displaystyle *\to X}$  in this category also denoted by ${\displaystyle P}$ . By composition, a probability space ${\displaystyle (X,{\mathcal {A}},P)}$  and a probability kernel ${\displaystyle \kappa :(X,{\mathcal {A}})\to (Y,{\mathcal {B}})}$  defines a probability space ${\displaystyle (Y,{\mathcal {B}},\kappa \circ P)}$ .

Properties

Semidirect product

Let ${\displaystyle (X,{\mathcal {A}},P)}$  be a probability space and ${\displaystyle \kappa }$  a Markov kernel from ${\displaystyle (X,{\mathcal {A}})}$  to some ${\displaystyle (Y,{\mathcal {B}})}$ . Then there exists a unique measure ${\displaystyle Q}$  on ${\displaystyle (X\times Y,{\mathcal {A}}\otimes {\mathcal {B}})}$ , such that:

${\displaystyle Q(A\times B)=\int _{A}\kappa (B|x)\,P(dx),\quad \forall A\in {\mathcal {A}},\quad \forall B\in {\mathcal {B}}.}$ 

Regular conditional distribution

Let ${\displaystyle (S,Y)}$  be a Borel space, ${\displaystyle X}$  a ${\displaystyle (S,Y)}$ -valued random variable on the measure space ${\displaystyle (\Omega ,{\mathcal {F}},P)}$  and ${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$  a sub-${\displaystyle \sigma }$ -algebra. Then there exists a Markov kernel ${\displaystyle \kappa }$  from ${\displaystyle (\Omega ,{\mathcal {G}})}$  to ${\displaystyle (S,Y)}$ , such that ${\displaystyle \kappa (\cdot ,B)}$  is a version of the conditional expectation ${\displaystyle \mathbb {E} [\mathbf {1} _{\{X\in B\}}\mid {\mathcal {G}}]}$  for every ${\displaystyle B\in Y}$ , i.e.

${\displaystyle P(X\in B\mid {\mathcal {G}})=\mathbb {E} \left[\mathbf {1} _{\{X\in B\}}\mid {\mathcal {G}}\right]=\kappa (\omega ,B),\qquad P{\text{-a.s.}}\,\,\forall B\in {\mathcal {G}}.}$ 

It is called regular conditional distribution of ${\displaystyle X}$  given ${\displaystyle {\mathcal {G}}}$  and is not uniquely defined.

Generalizations

Transition kernels generalize Markov kernels in the sense that the map

${\displaystyle B\mapsto \kappa (x,B)}$ 

is not necessarily a probability measure but can be any type of measure.

References

1. Reiss, R. D. (1993). "A Course on Point Processes". Springer Series in Statistics. doi:10.1007/978-1-4613-9308-5. ISBN 978-1-4613-9310-8. {{cite journal}}: Cite journal requires |journal= (help)
2. Klenke, Achim. Probability Theory: A Comprehensive Course (2 ed.). Springer. p. 180. doi:10.1007/978-1-4471-5361-0.
3. Erhan, Cinlar (2011). Probability and Stochastics. New York: Springer. pp. 37–38. ISBN 978-0-387-87858-4.
4. F. W. Lawvere (1962). "The Category of Probabilistic Mappings" (PDF).

• Bauer, Heinz (1996), Probability Theory, de Gruyter, ISBN 3-11-013935-9

§36. Kernels and semigroups of kernels