Markov Transition Matrices and Probability-State Conventions

States, Probabilities, and Transition Rules

A finite-state Markov model describes a system that occupies one state at each discrete time. Its transition rule gives the probabilities of moving from one state to another in a single step. A matrix makes those probabilities easy to organize, but there are two consistent ways to do so: probability distributions can be written as rows or as columns. The multiplication rule depends on that choice. In either convention, a valid probability state has nonnegative entries whose sum is one, and a valid transition must preserve those properties.

Suppose the possible states are \(S_1,\dots,S_n\). A probability state is a list of numbers giving the probabilities of occupying each state at the current time. The probability of being in state \(S_i\) is its \(i\)th entry. A Markov transition rule specifies the probabilities of the next state given the current state; the rule is assumed not to depend on earlier states once the current state is known.

In the row convention, \(P_{ij}\) is the probability of moving from state \(S_i\) to state \(S_j\). The current distribution is a row vector \(\mathbf{q}\), and its next value is \(\mathbf{q}P\). Each row of \(P\) describes all possible destinations from one starting state, so the rows sum to one.

In the column convention, \(P_{ij}\) is the probability of moving from state \(S_j\) to state \(S_i\). The current distribution is a column vector \(\mathbf{x}\), and its next value is \(P\mathbf{x}\). Each column describes the destinations from one starting state, so the columns sum to one. For the same transitions, the column-convention matrix is the transpose of the row-convention matrix. Thus, the two conventions describe the same model when both the matrix and the probability vector are oriented consistently.

Why Each Update Remains a Probability State

Proof. First consider the row convention. The \(j\)th entry of \(\mathbf{q}P\) is \(\sum_{i=1}^{n}q_iP_{ij}\). Every term is nonnegative because \(q_i\geq0\) and \(P_{ij}\geq0\), so every entry of \(\mathbf{q}P\) is nonnegative. Its entries sum to \(\sum_{j=1}^{n}\sum_{i=1}^{n}q_iP_{ij} =\sum_{i=1}^{n}q_i\left(\sum_{j=1}^{n}P_{ij}\right) =\sum_{i=1}^{n}q_i=1\), because each row of \(P\) sums to \(1\) and \(\mathbf{q}\) is a probability vector.

Now consider the column convention. The \(i\)th entry of \(P\mathbf{x}\) is \(\sum_{j=1}^{n}P_{ij}x_j\), which is nonnegative because each factor is nonnegative. The sum of the entries is \(\sum_{i=1}^{n}\sum_{j=1}^{n}P_{ij}x_j =\sum_{j=1}^{n}x_j\left(\sum_{i=1}^{n}P_{ij}\right) =\sum_{j=1}^{n}x_j=1\), because each column of \(P\) sums to \(1\). Both updates therefore produce probability vectors. \(\square\)

This result also applies repeatedly: after each step, the updated vector still satisfies the conditions needed for the next step. In particular, if the same transition matrix is used at every step, then after \(k\) steps the row state is \(\mathbf{q}_0P^k\), or the column state is \(P^k\mathbf{x}_0\), where \(P^k\) means the product of \(k\) copies of \(P\). The probability-preservation theorem can be applied at each multiplication.

What Matrix Powers Record

Repeated multiplication is not just a convenient way to calculate. In the row convention, the entry in row \(i\), column \(j\) of \(P^k\) is the probability of being in state \(S_j\) after \(k\) steps, given that the system began in state \(S_i\). Intermediate states are included through the sums in matrix multiplication.

Proof. When \(k=1\), this statement is exactly the definition of \(P_{ij}\). Assume it holds for a positive integer \(k\). By matrix multiplication, \((P^{k+1})_{ij}=\sum_{\ell=1}^{n}(P^k)_{i\ell}P_{\ell j}\). For each intermediate state \(S_\ell\), the induction assumption makes \((P^k)_{i\ell}\) the probability of reaching \(S_\ell\) from \(S_i\) in \(k\) steps, and \(P_{\ell j}\) is the probability of moving from \(S_\ell\) to \(S_j\) in one further step. The Markov rule makes the probability of that combined route the product of these two probabilities. The routes distinguished by their intermediate state \(S_\ell\) are disjoint and cover all ways to reach \(S_j\) after \(k+1\) steps. Adding their probabilities gives the displayed sum, which is therefore the required probability. Induction proves the statement for every positive integer \(k\). \(\square\)

The theorem explains why a row distribution evolves as \(\mathbf{q}_0P^k\): its \(j\)th entry adds the probabilities of starting in each state \(S_i\), weighted by the chance \((P^k)_{ij}\) of reaching \(S_j\) from that state. The same interpretation holds in the column convention with the transposed matrix and the matching column distribution.

Modeling a Two-State Transition

A matrix should be built from conditional transition probabilities, not from the distribution at one particular time. In the row convention, each row starts with a current state and lists the probabilities of every possible next state. The row must sum to one because the system must move somewhere. Once the transition matrix is built, the current distribution supplies the weights for combining its rows.

Common Pitfall: Mixing the Two Conventions

The condition “the entries sum to one” is not enough by itself. A row-stochastic matrix must multiply a row probability vector on the left; a column-stochastic matrix must multiply a column probability vector on the right. Using the wrong orientation can produce numbers that do not sum to one.

For example, the location matrix above is row-stochastic. A mistaken calculation might treat the initial row \((1,0)\) as a column and compute

This is not a probability vector: its entries sum to \(\frac34+\frac13=\frac{13}{12}\), not \(1\). The correction is to keep the row state and calculate \((1,0)P=(\frac34,\frac14)\). Alternatively, use the column convention consistently by transposing the matrix and multiplying the column state:

Both corrected calculations give the same distribution, just written in different orientations. Checking nonnegativity and the sum of the entries after an update is a useful arithmetic check, but it does not replace choosing the correct convention before multiplying.