Markov Workshop: Estimating and Checking a Transition Model

From Observed Transitions to a Matrix

A transition model describes how counts move among a fixed collection of states in one time step. For example, the states might be locations, categories, or conditions, and the data record how many units began in each state and ended in each other state. The main bookkeeping challenge is to preserve the distinction between the state a unit came from and the state it moved to. A matrix can contain valid proportions but still give incorrect predictions if its rows and columns are interpreted in the wrong order.

Use a fixed ordering of the states, say \(S_1,\dots,S_n\). Let \(N_{ij}\) be the observed number of units that began in source state \(S_i\) and ended in destination state \(S_j\). Thus the count table \(\mathbf{N}\) has source states as rows and destination states as columns. The total number observed from source \(S_i\) is \(s_i=\sum_{j=1}^n N_{ij}\). If \(s_i>0\), the observed proportion moving from \(S_i\) to \(S_j\) is \(N_{ij}/s_i\).

The index order in \(p_{ji}\) is deliberate: the first index refers to the destination row and the second to the source column. Each observed source total supplies the denominator for one whole column of \(\mathbf{P}\). If \(s_i=0\), the observed data contain no transitions from \(S_i\), so that column cannot be estimated by this relative-frequency rule. It is not valid to divide by zero or to treat an unobserved source state as having zero probability of every destination. Additional data or an explicitly supplied model would be needed.

Estimating and Checking a Model

Observed counts and model predictions answer different questions. The data in the example estimate the transition proportions and, when applied to their own source totals, reproduce the observed destination totals. If a later source-count vector differs from \((10,10,10)^{\top}\), its product with \(\mathbf{P}\) is a new prediction; it should not be compared as though it were the historical destination totals.

Why the Column Convention Preserves Counts

Proof. Each entry of \(\mathbf{P}\mathbf{x}\) is \((\mathbf{P}\mathbf{x})_j=\sum_{i=1}^n p_{ji}x_i\). Since every \(p_{ji}\ge 0\) and every \(x_i\ge 0\), each such sum is nonnegative. Summing all entries and changing the order of the finite sums gives \(\sum_{j=1}^n(\mathbf{P}\mathbf{x})_j=\sum_{j=1}^n\sum_{i=1}^n p_{ji}x_i=\sum_{i=1}^n x_i\sum_{j=1}^n p_{ji}\). Column \(i\) sums to \(1\), so the last expression is \(\sum_{i=1}^n x_i\). \(\square\)

This result gives two useful checks. First, a valid model in this convention cannot create or remove total count in a one-step prediction. Second, because nonnegative source counts produce nonnegative destination counts, negative predicted counts indicate either a calculation error or an object that is not a transition matrix in this convention. The theorem does not say that each predicted count must be an integer: estimated proportions can produce fractional expected counts, as the next example shows.

Checking State Ordering

A transition matrix is meaningful only with its state ordering attached. In the convention used here, both the rows of \(\mathbf{P}\) and the entries of a destination vector follow the destination-state order; the columns of \(\mathbf{P}\) and the entries of a source vector follow the source-state order. When source and destination states are the same collection, the same ordering is used on both axes.

Proof. A permutation matrix reorders coordinates, so its columns are a rearrangement of the standard basis vectors. Consequently \(\mathbf{S}^{\top}\mathbf{S}=\mathbf{I}_n\). Reordering destination coordinates applies \(\mathbf{S}\) on the left of \(\mathbf{P}\). Reordering source coordinates applies \(\mathbf{S}^{\top}\) on the right, because \(\mathbf{S}^{\top}\mathbf{x}'=\mathbf{S}^{\top}\mathbf{S}\mathbf{x}=\mathbf{x}\). Thus the matrix in the new order is \(\mathbf{P}'=\mathbf{S}\mathbf{P}\mathbf{S}^{\top}\). Applying it to the reordered input gives \(\mathbf{P}'\mathbf{x}'=\mathbf{S}\mathbf{P}\mathbf{S}^{\top}\mathbf{S}\mathbf{x}=\mathbf{S}\mathbf{P}\mathbf{x}\). This is exactly the original prediction with its coordinates reordered. \(\square\)

Common Convention Mistake

Some tables instead use source states as rows and destination states as columns in a row-stochastic transition matrix \(\mathbf{Q}\). Its entries are \(q_{ij}=N_{ij}/s_i\), so each row sums to \(1\). Such a matrix naturally acts on a row vector from the left. If counts are kept as columns, the corresponding operation is \(\mathbf{Q}^{\top}\mathbf{x}\), not \(\mathbf{Q}\mathbf{x}\). These are two consistent conventions; trouble comes from mixing their matrix layout and multiplication rule.

For a concrete check, suppose two states have count table \(\begin{bmatrix}3&1\\1&5\end{bmatrix}\), with source rows. The row-stochastic matrix is \(\mathbf{Q}=\begin{bmatrix}3/4&1/4\\1/6&5/6\end{bmatrix}\). For the column input \((8,2)^{\top}\), the correct result is

The total is \(19/3+11/3=10\), matching the input total. A wrong calculation would multiply \(\mathbf{Q}(8,2)^{\top}\), giving \((13/2,3)^{\top}\), whose total is \(19/2\), not \(10\). The correction is to use \(\mathbf{Q}^{\top}\) for column counts, or to use the column-stochastic matrix \(\mathbf{P}=\mathbf{Q}^{\top}\) from the start.

Before trusting an estimated model, check the count table layout, the denominator used for each source state, the sums of the appropriate matrix columns, and the ordering of source and destination coordinates. Then test the matrix on the observed source totals: its output should reproduce the observed destination totals when the transition counts describe the same single transition period. If it does not, locate the discrepancy before interpreting new predictions.