From Transition Probabilities to a Matrix
A transition matrix records how probability moves between a fixed collection of states in one step. The essential task is to keep track of which index names the current state and which names the next state. That choice determines both the placement of each probability in the matrix and the side on which the matrix multiplies the state vector.
Suppose there are \(n\) states, labelled \(1,\dots,n\). A state distribution is a list of probabilities \(x_1,\dots,x_n\), where \(x_i\) is the probability that the system is currently in state \(i\). We represent the distribution by the column vector \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\). It is a probability distribution when each \(x_i\geq 0\) and \(\sum_{i=1}^n x_i=1\). A one-step transition probability specifies the probability of the next state, conditional on the current state.
These definitions describe the same kind of transition information with different index placements. In the row convention, the current state labels the row and the next state labels the column. In the column convention, the next state labels the row and the current state labels the column. For the same transitions, \(\mathbf{Q}=\mathbf{P}^{\top}\). The two update rules are compatible because \((\mathbf{x}^{\top}\mathbf{P})^{\top}=\mathbf{P}^{\top}\mathbf{x}\).
Building the Row-Stochastic Matrix
Worked Example: Three States Listed by Current State
Consider states \(A,B,C\). The transition information is listed by current state: from \(A\), the probabilities of going to \(A,B,C\) are \(\tfrac12,\tfrac14,\tfrac14\); from \(B\), they are \(0,\tfrac34,\tfrac14\); from \(C\), they are \(\tfrac15,\tfrac3{10},\tfrac12\). Build the row-stochastic transition matrix.
Rows correspond to current states and columns to next states, in the order \(A,B,C\). Thus the first row contains the transitions out of \(A\), the second row those out of \(B\), and the third row those out of \(C\):
Check: the row sums are \(\tfrac12+\tfrac14+\tfrac14=1\), \(0+\tfrac34+\tfrac14=1\), and \(\tfrac15+\tfrac3{10}+\tfrac12=\tfrac2{10}+\tfrac3{10}+\tfrac5{10}=1\). All entries are nonnegative, so the matrix has the required row-stochastic form.
The row-sum condition has a direct interpretation: once the current state is fixed, the possible next states account for all the probability. The entries in a row must therefore sum to one. It is not the columns that are required to sum to one under this convention.
Why the Multiplication Rules Work
Proof. The \(j\)th entry of the row vector \(\mathbf{x}^{\top}\mathbf{P}\) is \(\sum_{i=1}^n x_i p_{ij}\). Each term is nonnegative, so every entry of \(\mathbf{x}'\) is nonnegative. Its entries sum to \(\sum_{j=1}^n\sum_{i=1}^n x_i p_{ij} =\sum_{i=1}^n x_i\left(\sum_{j=1}^n p_{ij}\right) =\sum_{i=1}^n x_i=1\), using the row sums of \(\mathbf{P}\) and the fact that \(\mathbf{x}\) is a probability distribution. Hence \(\mathbf{x}'\) is a probability distribution. The identity \((\mathbf{x}^{\top}\mathbf{P})^{\top}=\mathbf{P}^{\top}\mathbf{x}\) gives the stated column-vector rule. Finally, transposing \(\mathbf{P}\) makes each column sum equal to the sum of the corresponding row of \(\mathbf{P}\), which is \(1\); its entries remain nonnegative. Thus \(\mathbf{Q}\) is column-stochastic. \(\square\)
The entry formula also explains the rule: the probability of arriving in state \(j\) is the sum, over all possible current states \(i\), of the probability of being in \(i\) multiplied by the probability of going from \(i\) to \(j\). For the row convention, the matrix must therefore be multiplied on the right of the row representation \(\mathbf{x}^{\top}\), not on the left of the column \(\mathbf{x}\).
Using Both Conventions for One Update
Worked Example: Matching a Distribution to the Convention
Use the matrix from the three-state example, with initial distribution \(\mathbf{x}=(\tfrac12,\tfrac13,\tfrac16)^{\top}\). Find the one-step distribution using the row-stochastic convention, and then express the same calculation using a column-stochastic matrix.
First use the row representation. The entry for next state \(A\) is \(\tfrac12\cdot\tfrac12+\tfrac13\cdot0+\tfrac16\cdot\tfrac15=\tfrac14+\tfrac1{30}=\tfrac{17}{60}\). The entry for next state \(B\) is \(\tfrac12\cdot\tfrac14+\tfrac13\cdot\tfrac34+\tfrac16\cdot\tfrac3{10}=\tfrac18+\tfrac14+\tfrac1{20}=\tfrac{17}{40}\). The entry for next state \(C\) is \(\tfrac12\cdot\tfrac14+\tfrac13\cdot\tfrac14+\tfrac16\cdot\tfrac12=\tfrac18+\tfrac1{12}+\tfrac1{12}=\tfrac7{24}\). Therefore
As a column state vector, the result is \(\mathbf{x}'=(\tfrac{17}{60},\tfrac{17}{40},\tfrac7{24})^{\top}\). For the column-stochastic convention, transpose the transition matrix and multiply it by \(\mathbf{x}\):
Check: the entries are nonnegative, and their sum is \(\tfrac{17}{60}+\tfrac{17}{40}+\tfrac7{24}=\tfrac{34}{120}+\tfrac{51}{120}+\tfrac{35}{120}=1\). Both conventions give the same updated distribution.
Reading a Column-Stochastic Matrix
Worked Example: Recovering Transitions from Columns
Suppose a two-state model is supplied directly in the column-stochastic convention by \(\mathbf{Q}=\begin{bmatrix}\tfrac12&\tfrac14\\\tfrac12&\tfrac34\end{bmatrix}\). Interpret its columns as current states, and update the initial distribution \(\mathbf{y}=(\tfrac13,\tfrac23)^{\top}\).
Column 1 says that from state 1 the probabilities of going to states 1 and 2 are \(\tfrac12\) and \(\tfrac12\). Column 2 says that from state 2 they are \(\tfrac14\) and \(\tfrac34\). Each column sums to one: \(\tfrac12+\tfrac12=1\) and \(\tfrac14+\tfrac34=1\). The update is
Check: the updated entries are nonnegative and sum to \(\tfrac13+\tfrac23=1\). The first entry is the total probability of arriving in state 1, contributed by the initial probability in each of the two states.
A Common Convention Error
A frequent mistake is to take a row-stochastic matrix and multiply it on the left of a column state vector. The resulting numbers can look plausible, but they do not generally represent the next-state probabilities. For example, take the two-state row-stochastic matrix \(\mathbf{P}=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac13&\tfrac23\end{bmatrix}\) and the column distribution \(\mathbf{x}=(\tfrac25,\tfrac35)^{\top}\). The incorrect multiplication gives
These entries sum to \(\tfrac9{20}+\tfrac8{15}=\tfrac{27}{60}+\tfrac{32}{60}=\tfrac{59}{60}\), not \(1\). The correction is to use the row representation, \(\mathbf{x}^{\top}\mathbf{P}\), or transpose the matrix and use the column representation, \(\mathbf{P}^{\top}\mathbf{x}\). Both give \((\tfrac12,\tfrac12)\) as a row or column, respectively: the first entry is \(\tfrac25\cdot\tfrac34+\tfrac35\cdot\tfrac13=\tfrac3{10}+\tfrac15=\tfrac12\), and the second is \(\tfrac25\cdot\tfrac14+\tfrac35\cdot\tfrac23=\tfrac1{10}+\tfrac25=\tfrac12\).
The practical safeguard is to write down what each entry means before multiplying. If rows are current states, use the row-distribution rule; if columns are current states, use the column-vector rule. In either case, the updated entries should be nonnegative and sum to one. These checks help catch an inconsistent convention, but the meanings of the row and column indices determine the correct setup.
Check Your Understanding
For each question, identify the source and destination states explicitly before carrying out a calculation.
- A row-stochastic matrix has rows \((\tfrac23,\tfrac13)\) and \((\tfrac14,\tfrac34)\). Which entry gives the probability of moving from state 2 to state 1?
- Write the column-stochastic matrix corresponding to \(\mathbf{P}=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac13&\tfrac23\end{bmatrix}\).
- For that row-stochastic \(\mathbf{P}\), update \(\mathbf{x}=(\tfrac25,\tfrac35)^{\top}\) using \(\mathbf{x}^{\top}\mathbf{P}\).
- State the index meaning of \(q_{ij}\) under the column-stochastic convention, and identify which sum must equal \(1\).
- Explain why \(\mathbf{P}\mathbf{x}\) is not the matching update rule when \(\mathbf{P}\) is row-stochastic and \(\mathbf{x}\) is a column distribution.
