Multi-Step Markov Probabilities

Definition Let $P$ be the transition matrix of a time-homogeneous Markov chain $X_0, X_1, X_2, \dots$ on a finite or countable state space $S$. For $n \ge 0$ and states $i, j$, the $n$-step transition probability $p_{ij}^{(n)}$ is the probability that the chain, started in state $i$, is in state $j$ after $n$ steps. For any initial distribution and every $m \ge 0$ with $P(X_m = i) > 0$,

For $n = 0$ it is $1$ when $j = i$ and $0$ otherwise, and for $n = 1$ it is $P_{ij}$. For $n \ge 2$ it is the sum, over every list of intermediate states, of the product of the one-step probabilities along the path. For two steps,

By the Markov property and time homogeneity, each path probability is a product of conditional one-step probabilities, and the paths add because different lists of intermediate states are disjoint events.

Definition For $n \ge 1$ the matrix power $P^n$ is the matrix product $P P \cdots P$ with $n$ factors, and $P^0 = I$ is the identity matrix. For a time-homogeneous chain on a finite state space,

for all states $i, j$ and all $n \ge 0$, so $P^n$ is the $n$-step transition matrix. Every $P^n$ is again row-stochastic. A power of a matrix means repeated matrix multiplication, not the matrix of powers of the entries. If the rule changes over time, with a matrix $P_k$ for the step from time $k - 1$ to time $k$, the $n$-step matrix from time $0$ is the product $P_1 P_2 \cdots P_n$ in time order, and in general no single power describes it.

Definition The row vector $\pi_n$ lists the probabilities $P(X_n = i)$ for $i \in S$, in the order of the rows of $P$, so $\pi_0$ is the initial distribution. For a time-homogeneous chain with transition matrix $P$ and every $n \ge 0$,

The distribution stands on the left of the matrix, and the order of the factors matters. Under the column convention every matrix and vector is transposed, and the two conventions must not be mixed. Each $\pi_n$ has nonnegative entries that add to $1$. That check often exposes a slip such as a transposed matrix, but passing it does not prove that every entry is right.

Definition For a time-homogeneous Markov chain on a finite or countable state space, all $m, n \ge 0$ and all states $i, j$,

In matrix form, $P^{m+n} = P^m P^n$. The index $k$ runs over the possible states at the intermediate time $m$. The relation follows by conditioning on $X_m$, with the law of total probability and the Markov property.

Definition An endpoint probability is the probability that the chain is in a given state at a given time, such as $P(X_n = j)$, or $P(X_n = j \mid X_0 = i) = p_{ij}^{(n)}$ for a chain started in $i$. It is the $j$ coordinate of $\pi_0 P^n$. It depends only on the state at time $n$, so every path that ends in $j$ counts, whatever states it passed through.

Definition For a chain started in state $i$, a state $j$ and $n \ge 1$, the probability of visiting $j$ by step $n$ is the conditional probability, given $X_0 = i$, that $X_k = j$ for at least one time $k$ with $1 \le k \le n$. It equals $1$ minus the total probability of the paths that avoid $j$ at every time $1, \dots, n$. The event $\{X_n = j\}$ is contained in this event, so the visiting probability is at least the endpoint probability $p_{ij}^{(n)}$, and in general it is not an entry of $P^n$. For $i \ne j$ it equals the endpoint probability of $j$ after $n$ steps in a modified chain in which $j$ is absorbing, that is, in which the row of $j$ is replaced by staying in $j$ with probability $1$.