Computing Multi-Step Markov Probabilities

From One-Step Transitions to Several Steps

A transition matrix records the probabilities of moving between states in one step. For a model with several states, multiplying by that matrix updates the probability distribution for the current step. Repeating the multiplication gives probabilities after two, three, or more steps. The order of multiplication matters: here, as in the state-vector convention, distributions are columns.

Suppose a process has \(n\) states, labelled \(1,\dots,n\), and the probability of moving from state \(j\) to state \(i\) in one step is \(p_{ij}\). The transition matrix is \(\mathbf{P}=[p_{ij}]\). Thus the starting state indexes the column and the destination state indexes the row. A state distribution is a column \(\mathbf{x}\) whose entries are nonnegative and sum to \(1\); its \(i\)-th entry is the probability that the process is in state \(i\).

For example, if the process starts with certainty in state \(j\), its initial distribution is the standard basis vector \(\mathbf{e}_j\). Then \(\mathbf{P}^k\mathbf{e}_j\) is column \(j\) of \(\mathbf{P}^k\). Its entry in row \(i\) is the probability of being in state \(i\) after \(k\) steps, starting from state \(j\). In particular, the entry in row \(i\), column \(j\) of \(\mathbf{P}^k\) is the \(k\)-step probability from \(j\) to \(i\).

Why Matrix Powers Give Multi-Step Probabilities

Proof. For one step, the assertion is the definition of \(p_{ij}\), so it holds when \(k=1\). Suppose it holds for \(k\). To be in state \(i\) after \(k+1\) steps, the process must be in some state \(r\) after the first \(k\) steps and then move from \(r\) to \(i\). The events corresponding to the different states \(r\) are mutually exclusive and cover all possibilities. By the Markov property, the probability of the last transition from \(r\) to \(i\) is \(p_{ir}\). Therefore the total probability is \(\sum_{r=1}^{n}p_{ir}(\mathbf{P}^k)_{rj}\), which is the \((i,j)\)-entry of \(\mathbf{P}\mathbf{P}^k=\mathbf{P}^{k+1}\). This proves the assertion for every \(k\geq1\) by induction. More explicitly, for a sequence of states \(x_0=j,x_1,\dots,x_k=i\), the probability of that particular sequence is \(\prod_{t=1}^{k}p_{x_t x_{t-1}}\). Summing these products over all intermediate states \(x_1,\dots,x_{k-1}\) gives the same matrix-product entry. \(\square\)

This result explains the meaning of matrix multiplication in this setting. Each product of entries describes one route through the intermediate states, and the sum adds the probabilities of all routes that finish at the specified destination. The routes must be combined because the question asks only where the process ends, not which route it took.

Proof. For \(k=0\), \(\mathbf{P}^0=\mathbf{I}_n\), whose entries are nonnegative and whose columns each sum to \(1\). For \(k\geq1\), entries of \(\mathbf{P}^k\) are nonnegative because each is a sum of products of nonnegative entries of \(\mathbf{P}\). It remains to check the column sums. The claim holds for \(k=0\). If it holds for \(k\), then for each column \(j\) of \(\mathbf{P}^{k+1}=\mathbf{P}\mathbf{P}^k\), \(\sum_{i=1}^{n}(\mathbf{P}^{k+1})_{ij}=\sum_{r=1}^{n}(\mathbf{P}^k)_{rj}\left(\sum_{i=1}^{n}p_{ir}\right)=\sum_{r=1}^{n}(\mathbf{P}^k)_{rj}=1\), because each column of \(\mathbf{P}\) sums to \(1\) and each column of \(\mathbf{P}^k\) sums to \(1\). Induction proves the claim for all \(k\). \(\square\)

Worked Two-Step Probabilities

Three Steps and a Starting Distribution

To obtain the next power, multiply \(\mathbf{P}^2\mathbf{P}\), or equivalently \(\mathbf{P}\mathbf{P}^2\); both are \(\mathbf{P}^3\) by associativity of matrix multiplication. The columns of the resulting matrix describe the three-step distributions for each possible starting state. If the initial state is not certain, the whole initial distribution is multiplied by the power instead.

Interpreting an Entry Through Its Routes

Common Pitfall: Reversing the Indices

With column state vectors, the entry in row \(i\), column \(j\) means a move from \(j\) to \(i\). The column is the starting state; the row is the destination. For the first model, the one-step probability of moving from \(A\) to \(C\) is \(p_{CA}=0\), not \(p_{AC}=\tfrac12\). The latter is the probability of moving from \(C\) to \(A\).

A related mistake is to update a column distribution by multiplying on the right. For a certain start at \(A\), the correct one-step calculation is \(\mathbf{P}\mathbf{e}_A=(\tfrac12,\tfrac12,0)^{\top}\), which lists the probabilities of \(A,B,C\). Multiplying in the opposite order, \(\mathbf{e}_A^{\top}\mathbf{P}\), uses a row vector and is not the stated column-vector update. Keeping the convention fixed prevents both index reversals and incorrect interpretations of matrix powers.

Matrix powers are useful whenever a question concerns a fixed number of transitions: for example, the chance of arriving at a particular location after four moves, or the full distribution of an agent after several rounds. To answer such questions, identify the starting state or distribution, form the appropriate power, and read the destination entry or multiply the power by the initial column. A quick check is that every resulting distribution has nonnegative entries summing to \(1\).