Why Transition Matrices Are Row-Stochastic

Why Each Row Describes All Possible Next States

A transition matrix records the possible destinations of a process after one step. For a fixed current state, those destinations are mutually exclusive: the next state cannot be two different states at once. They are also exhaustive: if the process takes values in its stated state space, its next state must be one of those states. These two facts explain why the probabilities in each row are nonnegative and add to one.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a discrete-time process taking values in a finite or countable state space \(S\). Write \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) for its natural filtration. For a time-homogeneous Markov chain, the transition probabilities \(p_{ij}\) give the conditional probability of moving to \(j\) at the next step when the present state is \(i\). In particular, whenever \(\mathbb{P}(X_n=i)>0\), they satisfy \(\mathbb{P}(X_{n+1}=j\mid X_n=i)=p_{ij}\). The Markov property expresses the corresponding conditional law given \(\mathcal{F}_n\) using only \(X_n\).

If state \(i\) has probability zero at a particular time, conditioning on the event \(\{X_n=i\}\) does not define a conditional probability by the elementary event formula. A transition matrix is understood to specify a probability distribution for each state in its stated state space, including states that might not be reached from the chosen initial condition. The Markov property’s conditional identity is an almost-sure identity; it does not by itself determine the transition probabilities at states that are never visited. This distinction lets us discuss a transition law for every state without assigning a conditional probability to a zero-probability event.

Nonnegativity is a direct consequence of the definition of probability. The row sum requires one additional idea: partition the event that the current state is \(i\) according to the next state. Because \(S\) is countable, countable additivity applies even when there are infinitely many possible destinations.

The Partition Argument

Proof. Fix a state \(i\) and a time \(n\). For any \(j\in S\), a transition probability is a probability under the one-step law from \(i\), so \(p_{ij}\ge0\). If the law is obtained by conditioning on \(\{X_n=i\}\), this statement applies whenever that event has positive probability; the specified transition law for state \(i\) is itself a probability distribution in any case. Now consider the events \(\{X_{n+1}=j\}\), as \(j\) ranges over \(S\), under the one-step law from \(i\). They are pairwise disjoint, since \(X_{n+1}\) has only one value. Their union has probability one, since \(X_{n+1}\in S\) almost surely. Countable additivity therefore gives \(\sum_{j\in S}p_{ij}=\mathbb{P}(X_{n+1}\in S\mid X_n=i)=1\) whenever conditioning on that event is meaningful, and the specified one-step law has the same total mass for every state. This proves both claims for the chosen state. Since \(i\) was arbitrary, they hold for every row. For a time-inhomogeneous law, fix a time as well as a state and apply the same partition argument to that time’s one-step distribution. \(\square\)

For finite \(S\), the partition has finitely many parts, so ordinary finite additivity suffices. For countable \(S\), the sum includes every possible destination; omitting even one destination can make the displayed total less than one. In neither case does the argument require the chain to visit every state with positive probability.

What the Conditions Do—and Do Not—Say

Row-stochasticity is a statement about each fixed current state. It does not say that a chain has the same distribution at different times, nor that different rows must be equal. The rows may assign very different probabilities to destinations, provided each row consists of nonnegative numbers with total one. Likewise, the condition is about a transition law, not about how often the chain visits a state under a particular initial distribution.

Proof. For the forward direction, if row \(i\) is a probability distribution on the possible next states, each of its probabilities is nonnegative and the probabilities of all destinations sum to one by the defining properties of a probability distribution. For the reverse direction, fix \(i\). Nonnegativity means every \(p_{ij}\) can serve as a probability assigned to destination \(j\), and the row-sum condition says the total assigned probability is one. Hence the row defines a probability distribution on \(S\). Since this reasoning applies to every \(i\), the array specifies a one-step distribution for every current state. The claim includes a state space with one element: its sole row must have its single entry equal to one. \(\square\)

This proposition checks whether a proposed array has the right form for one-step transition probabilities. It does not prove that a particular observed process has those probabilities: that requires examining its conditional laws. Nor does row-stochasticity alone specify an initial distribution or a complete model of a process. It verifies the probability bookkeeping for one step from each state.

Countably Many Possible Destinations

When \(S\) is countably infinite, partitioning still works, but the row total is an infinite series. Since the terms are nonnegative, the sum is the limit of its partial sums. The probabilities of the first several destinations need not total one by themselves; the remaining destinations account for the rest.

A Common Mistake: Adding Down the Columns

A frequent error is to treat each column as though it represented all destinations from one current state. In the displayed convention, each row fixes the current state, while the entries across that row list the possible next states. Requiring columns to sum to one would impose an extra condition that is not part of row-stochasticity.

For example, in the preceding three-state finite matrix, one might incorrectly reject the matrix because its first column sums to \(\tfrac{13}{12}\), not \(1\). That calculation is correct as a column sum, but it tests the wrong condition. The relevant check for state \(1\) is the first row: \(\tfrac12+\tfrac13+\tfrac16=\tfrac{6+2+1}{6}=\tfrac96=1\). The second and third rows also sum to one, as computed above, so the matrix passes the correct test. A column sum of \(\tfrac{13}{12}\) does not represent the total probability of the next state being anything; it adds entries associated with different current states.

Another common error is to stop after checking nonnegativity. For instance, a proposed row \((\tfrac12,\tfrac14,0)\) has nonnegative entries, but its total is \(\tfrac12+\tfrac14+0=\tfrac34\), not one. If the three states listed are the entire state space, the row omits probability mass \(\tfrac14\). The repair is not to call the row a probability distribution: one must identify a missing possible destination or correct the probabilities so the complete row sums to one.

In practice, verify a proposed transition matrix in two stages: check that every entry is nonnegative, then add the entries across each row. For an infinite state space, the second stage means checking the full nonnegative series, not just a finite partial sum. These checks establish the basic probability structure of a transition law before using it in further calculations.