Path Probabilities from Initial Laws and One-Step Transitions

From One-Step Transitions to a Whole Path

A transition matrix describes the probability of one move at a time, but many questions concern a sequence of specified states. For example, we may want the probability that a chain starts in state $i_0$, then visits $i_1$, then $i_2$, and continues along a prescribed route. The Markov property makes this calculation a product: the probability of starting at the first state, multiplied by the probabilities of the successive moves. Keeping the initial probability in the product is essential when the chain does not start at a fixed state.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite or countable state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Write $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$ for its natural filtration. Suppose first that the chain is time-homogeneous, with transition matrix $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$ whenever the conditioning event has positive probability. Each row of $P$ sums to $1$. Its initial distribution is the row vector $\mu$, where $\mu_i=\mathbb{P}(X_0=i)$.

Definition: For $n\ge0$ and states $i_0,\ldots,i_n\in S$, the specified path event is $E(i_0,\ldots,i_n)=\{X_0=i_0,\ldots,X_n=i_n\}$. Its unconditional probability includes the probability of the initial state. The product over no transitions, as occurs when $n=0$, is defined to be $1$.

The Markov property means that the conditional distribution of $X_{r+1}$, given the history through time $r$, depends on that history only through $X_r$. In particular, for each $i,j\in S$, $\mathbb{P}(X_{r+1}=j\mid\mathcal{F}_r)=p_{ij}$ almost surely on $\{X_r=i\}$. We use this property together with the chain rule. The proof below is written so it does not require conditioning on a path prefix that might itself have probability zero.

Theorem (Finite path probability): For any $i_0,\ldots,i_n\in S$, $$ \mathbb{P}(X_0=i_0,\ldots,X_n=i_n) =\mu_{i_0}\prod_{r=0}^{n-1}p_{i_r i_{r+1}}. $$ If $\mu_{i_0}>0$, then the conditional probability given $X_0=i_0$ is $$ \mathbb{P}(X_1=i_1,\ldots,X_n=i_n\mid X_0=i_0) =\prod_{r=0}^{n-1}p_{i_r i_{r+1}}. $$

Proof. Define $E_r=\{X_0=i_0,\ldots,X_r=i_r\}$. For $0\le r<n$, the event $E_r$ belongs to $\mathcal{F}_r$, and on $E_r$ we have $X_r=i_r$. By the defining property of conditional expectation and the Markov property,

\begin{aligned} \mathbb{P}(E_{r+1}) &=\mathbb{E}\!\left[\mathbf{1}_{E_r}\mathbf{1}_{\{X_{r+1}=i_{r+1}\}}\right]\\ &=\mathbb{E}\!\left[\mathbf{1}_{E_r} \mathbb{E}\!\left[\mathbf{1}_{\{X_{r+1}=i_{r+1}\}}\mid\mathcal{F}_r\right]\right]\\ &=p_{i_r i_{r+1}}\mathbb{P}(E_r). \end{aligned}

This equality remains valid when $\mathbb{P}(E_r)=0$: both the expectation and the last expression are then zero. Starting with $\mathbb{P}(E_0)=\mu_{i_0}$ and applying the equality successively gives the unconditional product formula. If $\mu_{i_0}>0$, the event $\{X_0=i_0\}$ has positive probability, so ordinary conditioning is defined; dividing the unconditional formula by $\mathbb{P}(X_0=i_0)=\mu_{i_0}$ gives the conditional formula. When $n=0$, the unconditional formula reads $\mathbb{P}(X_0=i_0)=\mu_{i_0}$, and the conditional formula, when defined, is $1$, as required. $\square$

The theorem also covers impossible routes: if any required transition has probability zero, the path probability is zero. It does not make conditioning on a zero-probability starting state meaningful. For a time-inhomogeneous chain, the same proof applies with the transition probability at time $r$, denoted $p_{i_r i_{r+1}}(r)$, in the $r$th factor.

Worked Path Calculations

Worked Example: A Specified Route with a Fixed Start

Consider the chain on $S=\{A,B,C\}$ with transition matrix, in the order $A,B,C$,

P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac13&\tfrac13&\tfrac13 \end{bmatrix}.

Each row sums to $1$: row $A$ has sum $\tfrac12+\tfrac13+\tfrac16=\tfrac36+\tfrac26+\tfrac16=1$; row $B$ has sum $\tfrac14+\tfrac12+\tfrac14=\tfrac14+\tfrac24+\tfrac14=1$; row $C$ has sum $\tfrac13+\tfrac13+\tfrac13=1$. Suppose $X_0=A$ with probability $1$. The probability of the path $A,B,C,B$ is the product of its three transition probabilities:

\mathbb{P}(X_0=A,X_1=B,X_2=C,X_3=B) =1\cdot\tfrac13\cdot\tfrac14\cdot\tfrac13 =\tfrac1{36}.

Check: The first move has probability $p_{AB}=\tfrac13$, the second $p_{BC}=\tfrac14$, and the third $p_{CB}=\tfrac13$; their product is $\tfrac{1\cdot1\cdot1}{3\cdot4\cdot3}=\tfrac1{36}$. Since the starting state is certain, the unconditional path probability equals the probability of those moves given $X_0=A$.

Worked Example: A Random Initial State

Use the same transition matrix, whose row sums are $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $\tfrac13+\tfrac13+\tfrac13=1$. Let the initial distribution, in the order $A,B,C$, be $\mu=(\tfrac12,\tfrac13,\tfrac16)$. Each entry is nonnegative and the entries sum to $\tfrac12+\tfrac13+\tfrac16=1$. Find the unconditional probability of the path $B,A,B$, and then its probability conditional on $X_0=B$.

The initial state $B$ has probability $\mu_B=\tfrac13>0$, so conditioning on $X_0=B$ is defined. The two transitions are $p_{BA}=\tfrac14$ and $p_{AB}=\tfrac13$. Thus

\mathbb{P}(X_0=B,X_1=A,X_2=B) =\tfrac13\cdot\tfrac14\cdot\tfrac13 =\tfrac1{36}.

For the conditional probability, divide by $\mathbb{P}(X_0=B)=\tfrac13$, or directly use the product of the transition probabilities:

\mathbb{P}(X_1=A,X_2=B\mid X_0=B) =\tfrac14\cdot\tfrac13 =\tfrac1{12}.

Check: Multiplying the conditional probability by the probability of the conditioning event gives $\tfrac13\cdot\tfrac1{12}=\tfrac1{36}$, matching the unconditional calculation. This check also shows why the initial factor cannot be omitted from an unconditional path probability.

Worked Example: Add Paths to Find an Endpoint Probability

Again use the displayed matrix, and check its rows before computing: $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $\tfrac13+\tfrac13+\tfrac13=1$. Starting from $A$, find the probability that $X_2=C$ by listing all paths of length two from $A$ to $C$.

The intermediate state at time $1$ can be $A$, $B$, or $C$. These three path events are disjoint, so their probabilities add. The paths and products are

\begin{aligned} \mathbb{P}(A,A,C\mid X_0=A)&=\tfrac12\cdot\tfrac16=\tfrac1{12},\\ \mathbb{P}(A,B,C\mid X_0=A)&=\tfrac13\cdot\tfrac14=\tfrac1{12},\\ \mathbb{P}(A,C,C\mid X_0=A)&=\tfrac16\cdot\tfrac13=\tfrac1{18}. \end{aligned}

Therefore $\mathbb{P}(X_2=C\mid X_0=A)=\tfrac1{12}+\tfrac1{12}+\tfrac1{18}=\tfrac3{36}+\tfrac3{36}+\tfrac2{36}=\tfrac8{36}=\tfrac29$.

Check by a two-step calculation: The probability of moving from $A$ to $C$ in two steps is the sum over possible intermediate states $k$. Substituting the three entries gives $\sum_{k\in\{A,B,C\}}p_{Ak}p_{kC}=\tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac14+\tfrac16\cdot\tfrac13=\tfrac1{12}+\tfrac1{12}+\tfrac1{18}=\tfrac29$, the same answer.

Summing Over Paths

The previous calculation is an instance of a general identity: to find the probability of an endpoint after several steps, add the probabilities of all paths that end there. For a countable state space this can involve infinitely many paths. Since all path probabilities are nonnegative, the sum is well-defined, and the identity below follows by grouping the endpoint event according to the intermediate states.

Proposition (Path decomposition): For a time-homogeneous Markov chain and states $i,j\in S$, the $n$-step transition probability satisfies $$ p_{ij}^{(n)} =\sum_{\substack{i_1,\ldots,i_{n-1}\in S}} p_{i i_1}p_{i_1 i_2}\cdots p_{i_{n-1}j}, $$ where for $n=1$ the expression is $p_{ij}$, with no intermediate states to sum over. For a chain with initial distribution $\mu$, $$ \mathbb{P}(X_n=j)=\sum_{i\in S}\mu_i p_{ij}^{(n)}. $$

Proof. Fix $i$ and condition on $X_0=i$, an event with positive probability in the chain started at $i$. For each choice of intermediate states $i_1,\ldots,i_{n-1}$, the finite path formula gives the probability of that path, conditional on $X_0=i$, as the product of its one-step transition probabilities. The events indexed by these intermediate states are disjoint, and their union is $\{X_n=j\}$ under this initial condition: every realized finite sequence has exactly one list of intermediate states. Countable additivity therefore gives the sum in the first identity. For $n=1$ there is just the transition $i$ to $j$, so the identity is $p_{ij}$. For a random initial state, partition $\{X_n=j\}$ by the countable collection of events $\{X_0=i\}$. On each event with $\mu_i>0$, the conditional endpoint probability is $p_{ij}^{(n)}$; states with $\mu_i=0$ contribute zero. Adding these disjoint contributions gives $\mathbb{P}(X_n=j)=\sum_i\mu_i p_{ij}^{(n)}$. $\square$

This identity is useful both conceptually and computationally. A particular path probability uses one product. An endpoint probability usually requires a sum over many paths, because distinct routes can arrive at the same state. For a finite state space and a fixed number of steps, the sum is finite. For a countable state space, it is a countable sum of nonnegative terms, so no cancellation or order-dependent rearrangement is involved.

Common Mistakes and Careful Conditioning

A common mistake is to report the product of transition probabilities as the unconditional probability of a path when the initial state is random. In the example with $\mu_B=\tfrac13$, the product for $B,A,B$ is $\tfrac14\cdot\tfrac13=\tfrac1{12}$. That is the probability conditional on $X_0=B$, not the unconditional probability. The unconditional probability is $\tfrac13\cdot\tfrac1{12}=\tfrac1{36}$. Omitting the initial factor overstates the unconditional probability by a factor of $3$.

A second error is to use a conditional probability without checking that the conditioning event has positive probability. If an initial distribution assigns $\mu_A=0$, then $\mathbb{P}(X_0=A)=0$, and the ordinary conditional probability given $X_0=A$ is undefined. The unconditional path formula still applies: every path beginning at $A$ has probability zero because its product includes $\mu_A=0$. One may describe the transition probabilities of a chain started at $A$ as a separate model, but that is not the same as conditioning a process on an initial event of probability zero.

It is also important not to replace a specified route by an endpoint probability. For instance, the probability of the single route $A,B,C$ given $X_0=A$ is $\tfrac13\cdot\tfrac14=\tfrac1{12}$. The probability of $X_2=C$ given $X_0=A$ includes the routes through $A$, $B$, and $C$, and equals $\tfrac29$, as calculated above. These are different events: one specifies the intermediate state, while the other does not.

The calculation depends on the Markov property. Multiplying the displayed one-step transition probabilities is justified because, conditional on the history so far, the next-state probability is determined by the current state. The formula should not be applied to a process merely because one-step conditional probabilities have been written down; the required conditional law given the full history must agree with the transition rule. The path formula calculates consequences of the Markov property; it does not by itself establish that a process has that property.

Check Your Understanding

For each question, state whether the requested probability is unconditional or conditional, and show the factors you use.

A chain starts at state $1$ with probability $\tfrac25$, and $p_{12}=\tfrac13$, $p_{23}=\tfrac12$. Find the unconditional probability of the path $1,2,3$.
For a chain with $p_{12}=\tfrac14$ and $p_{23}=\tfrac23$, what is the probability of the moves $1,2,3$ conditional on $X_0=1$, provided $\mathbb{P}(X_0=1)>0$?
If $\mathbb{P}(X_0=1)=0$, is the ordinary conditional probability given $X_0=1$ defined? What does the unconditional formula say about paths that start at $1$?
Starting from state $i$, express the probability of $X_2=j$ as a sum over the possible state at time $1$.
Explain why the probabilities of distinct paths with the same initial and final states must be added to obtain the endpoint probability.

Path Probabilities from Initial Laws and One-Step Transitions

What You'll Learn