Markov kernel – Wikipedia

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

Formal definition[edit]

Let

${displaystyle (X,{mathcal {A}})}$

and

${displaystyle (Y,{mathcal {B}})}$

be measurable spaces. A Markov kernel with source

${displaystyle (X,{mathcal {A}})}$

and target

${displaystyle (Y,{mathcal {B}})}$

is a map

${displaystyle kappa :{mathcal {B}}times Xto [0,1]}$

with the following properties:

1. For every (fixed)
   ${displaystyle Bin {mathcal {B}}}$

   , the map

   ${displaystyle xmapsto kappa (B,x)}$

   is

   ${displaystyle {mathcal {A}}}$

   -measurable

2. For every (fixed)
   ${displaystyle xin X}$

   , the map

   ${displaystyle Bmapsto kappa (B,x)}$

   is a probability measure on

   ${displaystyle (Y,{mathcal {B}})}$

   

In other words it associates to each point

${displaystyle xin X}$

a probability measure

${displaystyle kappa (dy|x):Bmapsto kappa (B,x)}$

on

${displaystyle (Y,{mathcal {B}})}$

such that, for every measurable set

${displaystyle Bin {mathcal {B}}}$

, the map

${displaystyle xmapsto kappa (B,x)}$

is measurable with respect to the

${displaystyle sigma }$

-algebra

${displaystyle {mathcal {A}}}$

.^[2]

Examples[edit]

Simple random walk on the integers[edit]

Take

${displaystyle X=Y=mathbb {Z} }$

, and

${displaystyle {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 singletons

${displaystyle {m},,min Y=mathbb {Z} }$

for each

${displaystyle nin X=mathbb {Z} }$

:

${displaystyle kappa (B|n)=sum _{min B}kappa ({m}|n),qquad forall nin mathbb {Z} ,,forall Bin {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)=pdelta _{m,n+1}+(1-p)delta _{m,n-1},quad forall n,min 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[edit]

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 iin X}$

${displaystyle kappa (B|i)=sum _{jin B}kappa ({j}|i),qquad forall iin X,,forall Bin {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 Ytimes X,\sum _{jin Y}K_{ji}&=1,qquad &forall iin X.\end{aligned}}}$

We then define

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

.

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

Markov kernel defined by a kernel function and a measure[edit]

Let

${displaystyle nu }$

be a measure on

${displaystyle (Y,{mathcal {B}})}$

, and

${displaystyle k:Ytimes Xto [0,infty ]}$

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 xin X}$

,

then

${displaystyle kappa (dy|x)=k(y,x)nu (dy)}$

i.e. the mapping

${displaystyle {begin{cases}kappa :{mathcal {B}}times Xto [0,1]\kappa (B|x)=int _{B}k(y,x)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. Moreover it encompasses other important examples such as the convolution kernels, in particular the Markov kernels defined by the heat equation. The latter example includes the Gaussian kernel on

${displaystyle X=Y=mathbb {R} }$

with

${displaystyle nu (dx)=dx}$

standard Lebesgue measure and

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

.

Measurable functions[edit]

Take

${displaystyle (X,{mathcal {A}})}$

and

${displaystyle (Y,{mathcal {B}})}$

arbitrary measurable spaces, and let

${displaystyle f:Xto 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)={begin{cases}1&{text{if }}f(x)in B\0&{text{otherwise}}end{cases}}}$

for all

${displaystyle Bin {mathcal {B}}}$

.

Note that the indicator function

${displaystyle mathbf {1} _{f^{-1}(B)}}$

is

${displaystyle {mathcal {A}}}$

-measurable for all

${displaystyle Bin {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. That is, it is a multivalued function where the values are not equally weighted.

Galton–Watson process[edit]

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)&nneq 0\end{cases}}}$

^{[clarification needed]}

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 Category[edit]

Given measurable spaces

${displaystyle (X,{mathcal {A}})}$

,

${displaystyle (Y,{mathcal {B}})}$

we consider a Markov kernel

${displaystyle kappa :{mathcal {B}}times Xto [0,1]}$

as a morphism

${displaystyle kappa :Xto Y}$

. Intuitively, rather than assigning to each

${displaystyle xin X}$

a sharply defined point

${displaystyle yin Y}$

the kernel assigns a “fuzzy” point in

${displaystyle Y}$

which is only known with some level of uncertainty, much like actual physical measurements. If we have a third measurable space

${displaystyle (Z,{mathcal {C}})}$

, and probability kernels

${displaystyle kappa :Xto Y}$

and

${displaystyle lambda :Yto Z}$

, we can define a composition

${displaystyle lambda circ kappa :Xto Z}$

by

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

.

The composition is associative by the Monotone Convergence Theorem and the identity function considered as a 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. From this point of view a probability space

${displaystyle (Omega ,{mathcal {A}},mathbb {P} )}$

is the same thing as a pointed space

${displaystyle *to Omega }$

in the Markov category.

Probability Space defined by Probability Distribution and a Markov Kernel[edit]

A composition of a probability space

${displaystyle (X,{mathcal {A}},P_{X})}$

and a probability kernel

${displaystyle kappa :(X,{mathcal {A}})to (Y,{mathcal {B}})}$

defines a probability space

${displaystyle (Y,{mathcal {B}},P_{Y}=kappa circ P_{X})}$

, where the probability measure is given by

${displaystyle P_{Y}(B)=int _{X}int _{B}kappa (dy|x)P_{X}(dx)=int _{X}kappa (B|x)P_{X}(dx)=mathbb {E} _{P_{X}}kappa (B|cdot ).}$

Properties[edit]

Semidirect product[edit]

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 (Xtimes Y,{mathcal {A}}otimes {mathcal {B}})}$

, such that:

${displaystyle Q(Atimes B)=int _{A}kappa (B|x),P(dx),quad forall Ain {mathcal {A}},quad forall Bin {mathcal {B}}.}$

Regular conditional distribution[edit]

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} _{{Xin B}}mid {mathcal {G}}]}$

for every

${displaystyle Bin Y}$

, i.e.

${displaystyle P(Xin Bmid {mathcal {G}})=mathbb {E} left[mathbf {1} _{{Xin B}}mid {mathcal {G}}right]=kappa (cdot ,B),qquad P{text{-a.s.}},,forall Bin {mathcal {G}}.}$

It is called regular conditional distribution of

${displaystyle X}$

given

${displaystyle {mathcal {G}}}$

and is not uniquely defined.

Generalizations[edit]

Transition kernels generalize Markov kernels in the sense that for all

${displaystyle xin X}$

, the map

${displaystyle Bmapsto kappa (B|x)}$

can be any type of (non negative) measure, not necessarily a probability measure.

References[edit]

§36. Kernels and semigroups of kernels