State Ordering and Row-Vector Conventions

Why State Ordering Matters

A transition matrix records probabilities between states, but its rows and columns are positions in an ordered list—not the state labels themselves. If the ordering is not stated, an entry such as $p_{12}$ may be impossible to interpret: it depends on which states have been assigned positions 1 and 2. A consistent ordering lets us read every entry, represent distributions as row vectors, and change coordinates without changing the underlying chain.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $(X_n)_{n\ge0}$ be a time-homogeneous Markov chain with finite state space $S$. Its natural filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. We use a transition kernel $p(i,j)$, defined for every pair $i,j\in S$, with $p(i,j)\ge0$ and $\sum_{j\in S}p(i,j)=1$. The Markov property says that on $\{X_n=i\}$, the conditional probability of $X_{n+1}=j$, given $\mathcal{F}_n$, is $p(i,j)$. A kernel is specified for every state, including states that may have probability zero under a particular law.

Definition: An ordering of the state space is a list $(s_1,\ldots,s_m)$ that contains every state in $S$ exactly once, where $m=|S|$. With this ordering, the transition matrix $P=(p_{ab})$ is defined by $p_{ab}=p(s_a,s_b)$. Thus, row $a$ corresponds to the current state $s_a$, and column $b$ corresponds to the next state $s_b$. Each entry is nonnegative, and each row sums to 1.

The indices $a,b$ refer to positions in the chosen list; the states $s_a,s_b$ are labels. These are different kinds of objects. For example, the state called “rain” might be in position 3 in one ordering and position 1 in another. The transition probability from rain to calm does not change, but its matrix location does.

We use row vectors for distributions on $S$. If $\alpha$ is a probability distribution on $S$, its coordinate row vector in the ordering $(s_1,\ldots,s_m)$ is $(\alpha(s_1),\ldots,\alpha(s_m))$. Its entries are nonnegative and sum to 1. When the state ordering changes, the coordinates of this row vector must change in the same way as the state labels. The next tutorial develops the role of such vectors for initial laws; here the point is how their coordinates depend on the ordering.

Changing the Ordering

Suppose the original ordering is $(s_1,\ldots,s_m)$. Choose a permutation $\sigma$ of $\{1,\ldots,m\}$, and use the new ordering $(s_{\sigma(1)},\ldots,s_{\sigma(m)})$. A permutation matrix records this change: define $R_{ai}=1$ if $i=\sigma(a)$, and $R_{ai}=0$ otherwise. Each row and each column of $R$ has exactly one 1. In particular, $R^{-1}=R^{\mathsf T}$.

Theorem (Reordering rule): If $P$ is the transition matrix in the original ordering and $P'$ is the matrix in the new ordering, then $$ P'=RPR^{\mathsf T}. $$ If $\alpha$ is a row vector of state probabilities in the original ordering, its coordinates in the new ordering are $\alpha'=\alpha R^{\mathsf T}$. Reordering preserves the entries’ nonnegativity and the fact that every row sums to 1.

Proof. By matrix multiplication, the entry in row $a$, column $b$ of $RPR^{\mathsf T}$ is $p_{\sigma(a),\sigma(b)}$: row $a$ of $R$ selects original row $\sigma(a)$, and column $b$ of $R^{\mathsf T}$ selects original column $\sigma(b)$. This is exactly the transition probability from $s_{\sigma(a)}$ to $s_{\sigma(b)}$, which defines $P'_{ab}$. For the row vector, its new coordinate in position $a$ must be the old coordinate in position $\sigma(a)$. The $a$th entry of $\alpha R^{\mathsf T}$ is $\alpha_{\sigma(a)}$, so this gives the required coordinates. Finally, $RPR^{\mathsf T}$ only rearranges entries of $P$, so its entries remain nonnegative. For each new row $a$, its row sum is $\sum_b p_{\sigma(a),\sigma(b)}$. Since $\sigma$ is a permutation, as $b$ ranges over all positions, $\sigma(b)$ ranges over all original positions. Therefore this sum is $\sum_j p_{\sigma(a),j}=1$. $\square$

The row-vector rule follows the same principle: a probability attached to a state stays attached to that state, even when its position changes. The matrix rule changes both axes because rows identify current states and columns identify next states. Reordering only one axis does not describe the same chain under the new ordering.

Worked Example: Writing a Matrix in a Stated Ordering

Consider a chain with state space $S=\{\text{calm},\text{windy},\text{rain}\}$, using the ordering $(\text{calm},\text{windy},\text{rain})$. Suppose the transition probabilities, listed destination by destination for each current state, are: from calm, $\tfrac12,\tfrac13,\tfrac16$; from windy, $\tfrac14,\tfrac12,\tfrac14$; from rain, $\tfrac13,\tfrac13,\tfrac13$. Write its matrix.

By definition, each listed group becomes one row, with its entries placed in the stated column order. Thus $$ P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac13&\tfrac13&\tfrac13 \end{bmatrix}. $$

Check the row sums: the calm row sums to $\tfrac12+\tfrac13+\tfrac16=\tfrac36+\tfrac26+\tfrac16=1$. The windy row sums to $\tfrac14+\tfrac12+\tfrac14=\tfrac14+\tfrac24+\tfrac14=1$. The rain row sums to $\tfrac13+\tfrac13+\tfrac13=1$. All entries are nonnegative, so the matrix has the required row-stochastic form. For instance, the probability of a transition from windy to rain is the entry in row 2, column 3, namely $\tfrac14$.

Worked Example: Reordering All Rows and Columns

Use the same chain, but change the ordering to $(\text{rain},\text{calm},\text{windy})$. Compute the new matrix directly from the old one and check the result.

The new first row is the old rain row, but its columns must now be read as rain, calm, windy. The old rain probabilities to those states are $\tfrac13,\tfrac13,\tfrac13$. The new second row is the old calm row with its entries arranged as rain, calm, windy, giving $\tfrac16,\tfrac12,\tfrac13$. The new third row is the old windy row in that column order, giving $\tfrac14,\tfrac14,\tfrac12$. Therefore $$ P'= \begin{bmatrix} \tfrac13&\tfrac13&\tfrac13\\ \tfrac16&\tfrac12&\tfrac13\\ \tfrac14&\tfrac14&\tfrac12 \end{bmatrix}. $$

Here the new positions correspond to old positions $3,1,2$, so $$ R= \begin{bmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}. $$ The theorem gives $P'=RPR^{\mathsf T}$, which selects the old rows in order $3,1,2$ and the old columns in the same order. The row sums are $\tfrac13+\tfrac13+\tfrac13=1$, $\tfrac16+\tfrac12+\tfrac13=\tfrac16+\tfrac36+\tfrac26=1$, and $\tfrac14+\tfrac14+\tfrac12=\tfrac14+\tfrac14+\tfrac24=1$. These checks confirm that the reordering preserved the transition-matrix conditions.

The state labels also make the entry locations easy to check: in this new ordering, the transition from calm to windy is in row 2, column 3, and equals $\tfrac13$. In the original ordering it was in row 1, column 2, and also equaled $\tfrac13$. The coordinate changed; the probability did not.

Row Vectors in the New Coordinates

The same permutation acts on state-probability coordinates. In the example above, suppose a distribution assigns probability $\tfrac12$ to calm, $\tfrac13$ to windy, and $\tfrac16$ to rain. In the original ordering its row vector is $\alpha=(\tfrac12,\tfrac13,\tfrac16)$. The entries sum to $\tfrac36+\tfrac26+\tfrac16=1$. In the new ordering, the coordinates must be listed as rain, calm, windy, so $$ \alpha'=\alpha R^{\mathsf T}=(\tfrac16,\tfrac12,\tfrac13). $$

As a check, the new coordinates sum to $\tfrac16+\tfrac12+\tfrac13=\tfrac16+\tfrac36+\tfrac26=1$, and each state still has its original probability: rain has $\tfrac16$, calm has $\tfrac12$, and windy has $\tfrac13$. A row vector is not attached to positions independently of the states; its entries must follow the labels when the ordering changes.

Worked Example: Applying Two Reorderings

Starting from the original ordering $(\text{calm},\text{windy},\text{rain})$, use the ordering $(\text{windy},\text{rain},\text{calm})$ instead. Compute the matrix directly, and then check it by reordering the matrix from the previous example.

In the new ordering, the windy row has probabilities to windy, rain, calm of $\tfrac12,\tfrac14,\tfrac14$. The rain row has probabilities to windy, rain, calm of $\tfrac13,\tfrac13,\tfrac13$. The calm row has probabilities to windy, rain, calm of $\tfrac13,\tfrac16,\tfrac12$. Thus $$ P''= \begin{bmatrix} \tfrac12&\tfrac14&\tfrac14\\ \tfrac13&\tfrac13&\tfrac13\\ \tfrac13&\tfrac16&\tfrac12 \end{bmatrix}. $$

To check sequentially, start from the ordering $(\text{rain},\text{calm},\text{windy})$ and its matrix $P'$. The target ordering selects its rows in order $3,1,2$, and selects its columns in order $3,1,2$. The resulting rows are $(\tfrac12,\tfrac14,\tfrac14)$, $(\tfrac13,\tfrac13,\tfrac13)$, and $(\tfrac13,\tfrac16,\tfrac12)$, exactly the direct result. The row sums are $\tfrac12+\tfrac14+\tfrac14=1$, $\tfrac13+\tfrac13+\tfrac13=1$, and $\tfrac13+\tfrac16+\tfrac12=\tfrac26+\tfrac16+\tfrac36=1$. This agreement verifies that the labels, rather than any fixed row or column positions, determine the entries.

A Common Ordering Error

A frequent mistake is to reorder the rows but leave the columns in their original order, then interpret both axes using the new ordering. In the second example, the new ordering is rain, calm, windy. If we take the old calm row $(\tfrac12,\tfrac13,\tfrac16)$ without changing its entries, we might incorrectly call it the new calm row with columns rain, calm, windy. That assigns probability $\tfrac12$ to calm-to-rain. But the original matrix says calm-to-rain is $\tfrac16$, and the correctly reordered row is $(\tfrac16,\tfrac12,\tfrac13)$.

The incorrect matrix may still have nonnegative entries and row sums of 1, so checking row sums alone cannot detect every labeling error. The correction is to identify the meaning of both axes before reading an entry: $p_{ab}$ is the probability of moving from the state in row position $a$ to the state in column position $b$. On changing the ordering, rearrange rows and columns together, and rearrange the coordinates of any row vector in the same state order.

Takeaway: State labels determine the chain; an ordering determines only how its transition probabilities and distributions are written as arrays. With new position $a$ corresponding to old position $\sigma(a)$, use $P'=RPR^{\mathsf T}$ for the matrix and $\alpha'=\alpha R^{\mathsf T}$ for a row vector.

Check Your Understanding

For each question, state the ordering you are using before assigning matrix positions.

A state space has ordering $(a,b,c)$. What state does entry $p_{23}$ describe?
If the new ordering is $(c,a,b)$, which old row positions form the new rows? Which old column positions form the new columns?
In the second worked example, what is the probability of transitioning from windy to calm, and where does it appear in each ordering?
Explain why changing an ordering preserves row sums when both rows and columns are rearranged.
For the probability vector $(\tfrac12,\tfrac13,\tfrac16)$ in ordering $(\text{calm},\text{windy},\text{rain})$, write its coordinates in ordering $(\text{rain},\text{calm},\text{windy})$ and check their sum.

State Ordering and Row-Vector Conventions

What You'll Learn