Finite-State Markov Chains: States, Times, and Sample Paths

From a Random Process to a Sample Path

A discrete-time Markov chain is a random process whose possible values lie in a state space and whose conditional law for the next state depends on the present state, not the full observed history. The distinction between the process and one of its realizations matters: the process is a family of random variables on a probability space, whereas a sample path is the sequence of values obtained at one outcome. A single path can illustrate what the process did on one occasion, but by itself it does not specify the probabilities governing the process.

We first fix the objects needed to describe a chain. The time index is \(n=0,1,2,\ldots\). The state space \(S\) is finite, and \((\Omega,\mathcal{F},\mathbb{P})\) is the probability space. At each time \(n\), \(X_n\) is a random variable with values in \(S\). The history through time \(n\) is represented by the natural filtration \(\mathcal{F}_n^X=\sigma(X_0,\ldots,X_n)\), the information generated by the values observed so far.

This definition uses only finite histories: at time \(n\), the condition compares the conditional distribution of \(X_{n+1}\) given the whole history with a probability vector indexed by the current state \(X_n\). The detailed interpretation of this condition as conditional independence is a separate topic. Here the focus is on what the process and its paths are, and on how an observed path differs from the chain itself.

The last qualification prevents a subtle set-theoretic error. Separate probability-one statements for each time do imply that, with probability one, all times have values in \(S\), because there are only countably many times. They do not imply that the original coordinate map takes values in the path space on every outcome, including outcomes in the exceptional null set.

Proof. For each \(n\), let \(A_n=\{\omega:X_n(\omega)\in S\}\). Each \(A_n\) is measurable because \(X_n\) is a random variable and \(S\) is measurable in its state space, and \(\mathbb{P}(A_n)=1\) by assumption. Put \(A=\bigcap_{n\ge0}A_n\). This countable intersection is measurable, and its complement is \(\bigcup_{n\ge0}A_n^c\). Countable subadditivity gives \(\mathbb{P}(A^c)\le\sum_{n\ge0}\mathbb{P}(A_n^c)=0\), so \(\mathbb{P}(A)=1\). For measurability of the restricted path map, it suffices to check the generating sets that prescribe finitely many coordinates: for times \(n_1,\ldots,n_r\) and states \(s_1,\ldots,s_r\), the preimage in \(A\) is \(A\cap\bigcap_{\ell=1}^r\{\omega:X_{n_\ell}(\omega)=s_\ell\}\), which belongs to the sigma-algebra on \(A\) inherited from \(\mathcal{F}\). Thus the restricted map is measurable. The argument asserts measurability on \(A\), not that the original map is path-valued on all of \(\Omega\). \(\square\)

What the Process Contains

The process consists of the random variables \((X_n)_{n\ge0}\), together with their joint behavior on the probability space. The distribution of the process records probabilities of events involving its coordinates, such as \(\{X_0=i,X_1=j\}\). An observed realization is just one sequence of coordinate values. Different outcomes can produce the same sequence, and a single observed sequence does not reveal how likely that sequence—or other sequences—was.

For a finite state space \(S\), one may list states in a fixed order and arrange transition probabilities in a matrix \(P=(p_{ij})\), where \(p_{ij}\) is the probability of moving from state \(i\) to state \(j\) when the chain is time-homogeneous. Such a matrix is row-stochastic: entries are nonnegative and each row sums to \(1\). A matrix describes transition probabilities; it is not itself a sample path. The examples below use matrices only when useful for making that distinction explicit.

Reading a Path Without Over-Interpreting It

The examples separate three things that are easy to conflate: the probability space, which supplies the outcomes; the process, which assigns a random state to each time; and a sample path, which lists the states at one outcome. The transition law is another part of the description: it states how probabilities of next states depend on the current state and, in the general definition, may also depend on time.

A common mistake is to see one observed path and treat its frequencies or transitions as if they were the process’s transition probabilities. For instance, in the second example, suppose the observed path begins \(0,1,1\). A wrong calculation might count the one observed transition out of state \(0\) and conclude that the probability of moving from \(0\) to \(1\) is \(1\). That conclusion confuses a single observed transition with a conditional probability. In the specified process, when \(X_0=0\), outcomes \(a\) and \(b\) are equally likely, so \[ \mathbb{P}(X_1=1\mid X_0=0)=\frac{\mathbb{P}(\{b\})}{\mathbb{P}(\{a,b\})} =\frac{\tfrac14}{\tfrac12}=\tfrac12. \] One observed realization does not change this probability; it only tells us which outcome occurred in that observation.

When describing a finite-state chain, make the time index and state space explicit, say whether the process is defined on all outcomes or only takes values in the state space almost surely, and distinguish a path from the law of the process. When checking whether a process is Markov, compare conditional probabilities across positive-probability histories that end in the same current state. If those probabilities disagree, the process cannot satisfy the defining condition.