Markov Chain Path Measures from Transition Kernels

From One-Step Transitions to Entire Paths

A transition rule describes the next state given the current state. To describe a whole chain, one also needs an initial distribution and a way to combine successive transitions. The resulting finite-time laws must agree when a coordinate is discarded: for example, summing over the last state must recover the law of the earlier states. Once this consistency is verified, the Kolmogorov extension theorem supplies a probability measure on the space of infinite paths.

Let $(S,\mathcal{S})$ be a standard Borel measurable space; that is, a measurable space measurably isomorphic to a Borel subset of a complete separable metric space. We use this assumption so the countable Kolmogorov extension theorem applies. A probability measure $\lambda$ on $(S,\mathcal{S})$ is the initial distribution. The transition rule is a probability kernel $P$ from $S$ to $S$.

Definition: A probability kernel $P$ from $S$ to $S$ assigns a number $P(x,A)$ to each $x\in S$ and $A\in\mathcal{S}$, such that (i) for each fixed $x$, $A\mapsto P(x,A)$ is a probability measure on $(S,\mathcal{S})$, and (ii) for each fixed $A$, $x\mapsto P(x,A)$ is $\mathcal{S}$-measurable. In particular, $P(x,S)=1$ for every $x$.

For a measurable function $g:S\to[0,\infty]$, the notation $Pg(x)=\int_S g(y)\,P(x,dy)$ is meaningful and measurable in $x$. The corresponding assertion for bounded real-valued measurable $g$ follows by taking positive and negative parts. At each finite stage, successive kernels define a probability measure on the finite product: this is the standard finite kernel-product construction, whose countable additivity follows from monotone convergence. It gives the following finite-dimensional laws.

Definition: For $n\geq 0$, define the law $\mu_n$ on $(S^{n+1},\mathcal{S}^{\otimes(n+1)})$ by the iterated-kernel formula $$ \mu_n(dx_0,\ldots,dx_n) =\lambda(dx_0)P(x_0,dx_1)\cdots P(x_{n-1},dx_n). $$ Precisely, for measurable rectangles $A_0\times\cdots\times A_n$, its value is $$ \int_{A_0}\lambda(dx_0)\int_{A_1}P(x_0,dx_1)\cdots \int_{A_n}P(x_{n-1},dx_n). $$ The finite kernel-product construction defines the measure on the full product sigma-algebra, not just on rectangles.

The rectangle formula is convenient for calculations, but consistency concerns the full laws. Integrating over the last coordinate uses $P(x,S)=1$. Integrating over the first coordinate instead replaces the initial distribution by the one-step distribution $A\mapsto\int_S P(x,A)\lambda(dx)$. More generally, integrating out intermediate coordinates composes the kernels. Thus the marginal on any retained set of times is the law obtained by starting with $\lambda$ and applying the transitions across the elapsed steps.

Consistency and the Path-Space Measure

Proposition: The measures $(\mu_n)_{n\geq0}$ are consistent: the marginal of $\mu_n$ on coordinates $0,\ldots,n-1$ is $\mu_{n-1}$. In addition, the marginal on coordinates $1,\ldots,n$ is the law formed by starting with the one-step distribution $\lambda P$ and then applying $n-1$ transitions, where $(\lambda P)(A)=\int_S P(x,A)\lambda(dx)$.

Proof. To obtain the marginal on coordinates $0,\ldots,n-1$, integrate the last coordinate in the defining iterated integral. For each fixed $x_{n-1}$, the integral of the constant function $1$ against $P(x_{n-1},\cdot)$ is $P(x_{n-1},S)=1$. The remaining iterated integral is exactly the defining formula for $\mu_{n-1}$, so the first assertion holds. For the marginal on coordinates $1,\ldots,n$, integrate $x_0$ first. Its contribution to the next coordinate is $\int_S P(x_0,dx_1)\lambda(dx_0)$, which is $(\lambda P)(dx_1)$; the remaining factors are the next $n-1$ kernels. This proves the second assertion. The same integrations, one coordinate at a time, establish the corresponding statements for any retained collection of times. $\square$

Consistency is exactly the compatibility required to apply the extension theorem. We use its standard countable form, established in the earlier material on the Kolmogorov extension theorem: consistent probability laws on finite coordinate products of standard Borel spaces extend to a unique probability measure on the countable product sigma-algebra.

Theorem (Markov chain path measure): Let $(S,\mathcal{S})$ be standard Borel, let $\lambda$ be a probability measure on it, and let $P$ be a probability kernel from $S$ to $S$. There is a unique probability measure $\mathbb{P}$ on $(S^{\mathbb{N}_0},\mathcal{S}^{\otimes\mathbb{N}_0})$ whose marginal on coordinates $0,\ldots,n$ is $\mu_n$ for every $n\geq0$. Here $\mathbb{N}_0=\{0,1,2,\ldots\}$. The coordinate maps $X_n(\omega)=\omega_n$ are measurable $S$-valued random variables on this path probability space.

Proof. The finite kernel-product construction gives probability measures $\mu_n$, and the proposition verifies their consistency. The standard countable Kolmogorov extension theorem therefore gives a probability measure on the product sigma-algebra with these finite-coordinate marginals. The same theorem gives uniqueness. Each coordinate map is measurable because the inverse image of $A\in\mathcal{S}$ is the coordinate cylinder $\{\omega:\omega_n\in A\}$, which belongs to the product sigma-algebra. $\square$

This is a measure on the measurable space of paths, not a claim that every individual path has positive probability. It also makes the transition rule precise: for each $n$ and measurable $C\subseteq S^{n+1}$, the finite kernel formula gives $$ \mathbb{P}\big((X_0,\ldots,X_n)\in C,\ X_{n+1}\in A\big) =\int_C P(x_n,A)\,\mu_n(d(x_0,\ldots,x_n)). $$ Consequently, the conditional probability of $X_{n+1}\in A$ given the history through time $n$ is $P(X_n,A)$, almost surely. This statement uses the defining integral property of conditional expectation; it does not assert that a conditional probability is defined by division by the probability of a possibly null history.

Worked Finite-Time Calculations

Worked Example: A Two-State Chain

Take $S=\{A,B\}$ with all subsets measurable, initial probabilities $\lambda(A)=1/3$, $\lambda(B)=2/3$, and transition matrix (rows are current states, columns are next states) $$ P=\begin{pmatrix} 3/4&1/4\\ 1/2&1/2 \end{pmatrix}. $$ Each row sums to $1$: $3/4+1/4=1$ and $1/2+1/2=1$, so this is a probability kernel.

The probability of the path $(X_0,X_1,X_2)=(A,B,A)$ is the product of the initial probability and the two transitions: $$ \mathbb{P}(X_0=A,X_1=B,X_2=A) =\frac13\cdot\frac14\cdot\frac12=\frac1{24}. $$ To check a marginal, sum over the middle state for the event $X_0=A,X_2=A$. The two paths are $(A,A,A)$ and $(A,B,A)$, with probabilities $$ \frac13\cdot\frac34\cdot\frac34=\frac3{16}, \qquad \frac13\cdot\frac14\cdot\frac12=\frac1{24}. $$ Their sum is $3/16+1/24=9/48+2/48=11/48$. Independently, the two-step transition probability from $A$ to $A$ is $3/4\cdot3/4+1/4\cdot1/2=9/16+2/16=11/16$; multiplying by $\lambda(A)=1/3$ again gives $11/48$. This is an explicit marginalization check.

Worked Example: A Random Walk on the Integers

Let $S=\mathbb{Z}$ with its power-set sigma-algebra, $\lambda=\delta_0$, and $P(k,\{k-1\})=P(k,\{k+1\})=1/2$, with probability $0$ assigned to all other individual states. Since these two successors are distinct and their probabilities sum to $1/2+1/2=1$, this specifies a probability measure for each $k$; measurability in $k$ holds because every subset of $\mathbb{Z}$ is measurable.

The probability of the particular four-time path $(0,1,0,-1)$ is $$ \mathbb{P}(X_0=0,X_1=1,X_2=0,X_3=-1) =1\cdot\frac12\cdot\frac12\cdot\frac12=\frac18. $$ As a check on the endpoint marginal, $X_3=-1$ requires exactly two steps to the left and one to the right. There are three possible orders for the right step, and each of these three paths has probability $1/8$. Thus $\mathbb{P}(X_3=-1)=3/8$, which is also obtained by summing the three length-three path probabilities. The single path above is one of those three and has probability $1/8$, not $3/8$.

Worked Example: A Deterministic Transition

Let $S=[0,1]$ with its Borel sigma-algebra, $\lambda=m|_{[0,1]}$ (Lebesgue measure restricted to this interval), and $P(x,A)=\delta_{x/2}(A)$. The map $x\mapsto x/2$ is continuous, so $x\mapsto\delta_{x/2}(A)=\chi_A(x/2)$ is Borel measurable for each Borel set $A$. Each $P(x,\cdot)$ is a probability measure. The resulting chain has $X_0=U$ and $X_j=U/2^j$ for $j\geq0$, where $U$ has uniform distribution on $[0,1]$.

Consider $X_0\in[1/4,3/4]$ and $X_2\in[0,1/8]$, with the displayed closed endpoints included. The first condition is $U\in[1/4,3/4]$. Since $X_2=U/4$, the second is $U/4\leq1/8$, or $U\leq1/2$. Their intersection is $U\in[1/4,1/2]$, which has Lebesgue measure $1/2-1/4=1/4$. Hence the cylinder event has probability $1/4$. Directly, the two-coordinate law is the image of uniform $U$ under $u\mapsto(u,u/4)$; the same preimage interval has length $1/4$, confirming the calculation.

Normalization, Measurability, and a Common Error

The two kernel conditions do different work. The probability-measure condition in the second argument ensures that each step has total mass one and is countably additive. Measurability in the first argument ensures that the iterated integrals defining the finite laws are measurable and can be integrated. A matrix with nonnegative entries is not automatically a transition matrix: every row must sum to one.

Common mistake. Suppose a proposed two-state matrix is $$ Q=\begin{pmatrix} 1/2&1/2\\ 1/3&1/3 \end{pmatrix} $$ and the initial state is $B$ with probability one. A mistaken calculation might treat the second row as a probability distribution and report total mass $1$ after one step. But its entries sum to $1/3+1/3=2/3$, so the proposed one-step law has total mass $2/3$, not $1$. The correction is to normalize that row; for example, replacing it by $(1/2,1/2)$ makes its sum $1/2+1/2=1$. Only after every row is a probability distribution does the kernel construction produce consistent probability laws.

The assumption that $S$ is standard Borel is also part of the stated extension theorem, not a cosmetic convention. A formula for probabilities of finite-time events alone does not automatically provide a probability measure on every conceivable path sigma-algebra. Here the countable product sigma-algebra and the standard Borel hypothesis are the setting in which the extension theorem gives existence and uniqueness.

Check Your Understanding

For each question, distinguish a finite-dimensional calculation from the existence of the full path-space measure.

For a two-state transition matrix, what conditions must each row satisfy for it to define a probability kernel?
Explain why integrating the last coordinate in $\mu_n$ recovers $\mu_{n-1}$.
For the two-state chain in the first worked example, compute $\mathbb{P}(X_0=B,X_1=A,X_2=A)$.
For the integer random walk in the second example, list the three possible step orders that end at $-1$ after three steps.
In the deterministic example, compute the probability of $X_0\in[0,1/2]$ and $X_1\in[1/4,1/2]$, keeping the stated closed endpoints.
Which hypotheses allow the consistent finite-dimensional laws to determine a unique measure on the countable path space?

Markov Chain Path Measures from Transition Kernels

What You'll Learn