How Matrix Products Preserve Stochasticity

Why Stochasticity Must Survive Multiplication

A transition matrix describes one step of a Markov chain: its entry in row \(i\), column \(j\), is the probability of moving from state \(i\) to state \(j\). After two steps, the transition probabilities are obtained by matrix multiplication. That multiplication is meaningful as a probability model only if its entries remain nonnegative and each row still sums to one. The same question arises when composing different transition rules, and when taking many steps with one fixed rule.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain with finite or countable state space \(S\). Its transition matrix \(P=(p_{ij})\) is row-stochastic: its entries are nonnegative and each row sums to one. The transition probabilities are specified for every state \(i\); whenever \(\mathbb{P}(X_n=i)>0\), they agree with \(\mathbb{P}(X_{n+1}=j\mid X_n=i)\). The matrix convention is that rows are starting states and columns are destination states.

Definition: A matrix \(A=(a_{ij})_{i,j\in S}\) on a finite or countable state space \(S\) is row-stochastic if \(a_{ij}\ge0\) for every \(i,j\in S\) and \(\sum_{j\in S}a_{ij}=1\) for every \(i\in S\). For countably infinite \(S\), the row sum means the sum of a series of nonnegative terms.

Suppose two such matrices \(A\) and \(B\) use the same state space. Their product is defined by \(C=AB\), with \(c_{ij}=\sum_{k\in S}a_{ik}b_{kj}\). The intermediate index \(k\) represents the state after the first transition and before the second. The product is row-stochastic, as the next result proves. The proof also covers countably infinite state spaces, where the order of summation needs justification.

The Product Theorem

Theorem: If \(A=(a_{ik})\) and \(B=(b_{kj})\) are row-stochastic matrices on the same finite or countable state space \(S\), then their product \(C=AB\), defined by \(c_{ij}=\sum_{k\in S}a_{ik}b_{kj}\), is row-stochastic.

Proof. Fix \(i,j\in S\). Each term \(a_{ik}b_{kj}\) is nonnegative, so its sum over \(k\) is nonnegative; hence \(c_{ij}\ge0\). To check row \(i\), sum the entries over \(j\). All terms \(a_{ik}b_{kj}\) are nonnegative, so the theorem for rearranging nonnegative series (Tonelli’s theorem for series) permits exchanging the order of summation. Therefore, using the row sums of \(B\) and then of \(A\),

\sum_{j\in S}c_{ij} =\sum_{j\in S}\sum_{k\in S}a_{ik}b_{kj} =\sum_{k\in S}a_{ik}\sum_{j\in S}b_{kj} =\sum_{k\in S}a_{ik}\cdot 1 =1.

This holds for each \(i\), so every row of \(C\) sums to one. Thus \(C\) is row-stochastic. \(\square\)

The theorem requires both factors to be row-stochastic and to use the same state space, so the product has a common intermediate index. Nonnegativity is essential: it both gives nonnegative product entries and justifies the summation exchange in the countable case. In a finite state space the sums are finite, so their order can be exchanged directly.

Worked Example: Multiplying Two Two-State Kernels

Consider the two matrices

A=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac13&\tfrac23\end{bmatrix}, \qquad B=\begin{bmatrix}\tfrac13&\tfrac23\\[2pt]\tfrac23&\tfrac13\end{bmatrix}.

Before multiplying, check the input rows. For \(A\), the row sums are \(\tfrac12+\tfrac12=1\) and \(\tfrac13+\tfrac23=1\). For \(B\), they are \(\tfrac13+\tfrac23=1\) and \(\tfrac23+\tfrac13=1\). All entries are nonnegative, so both matrices are row-stochastic.

Compute \(C=AB\) entry by entry. For row 1, column 1, \(c_{11}=\tfrac12\cdot\tfrac13+\tfrac12\cdot\tfrac23=\tfrac16+\tfrac13=\tfrac12\). For row 1, column 2, \(c_{12}=\tfrac12\cdot\tfrac23+\tfrac12\cdot\tfrac13=\tfrac13+\tfrac16=\tfrac12\). For row 2, column 1, \(c_{21}=\tfrac13\cdot\tfrac13+\tfrac23\cdot\tfrac23=\tfrac19+\tfrac49=\tfrac59\). For row 2, column 2, \(c_{22}=\tfrac13\cdot\tfrac23+\tfrac23\cdot\tfrac13=\tfrac29+\tfrac29=\tfrac49\). Thus

AB=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac59&\tfrac49\end{bmatrix}.

Check: the product entries are nonnegative; its first row sums to \(\tfrac12+\tfrac12=1\), and its second row sums to \(\tfrac59+\tfrac49=1\). This verifies the theorem’s conclusion directly for this product.

The order of multiplication records the order of the transitions: \(AB\) first uses \(A\), then \(B\). The theorem guarantees stochasticity for either order if both factors are row-stochastic, but it does not say the two products are equal. The entries of the product depend on which matrix supplies the first transition.

Worked Example: A Three-State Composition

Let

A=\begin{bmatrix} \tfrac12&\tfrac12&0\\ 0&\tfrac12&\tfrac12\\ 1&0&0 \end{bmatrix}, \qquad B=\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}.

Every row of \(A\) sums to one: \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(1+0+0=1\). Every row of \(B\) also sums to one: \(0+1+0=1\), \(0+0+1=1\), and \(1+0+0=1\). All entries are nonnegative, so the product theorem applies.

For any row vector \((x_1,x_2,x_3)\), multiplication by \(B\) gives \((x_3,x_1,x_2)\): the first output coordinate is \(x_3\cdot1\), the second is \(x_1\cdot1\), and the third is \(x_2\cdot1\). Apply this to each row of \(A\). Its first row \((\tfrac12,\tfrac12,0)\) becomes \((0,\tfrac12,\tfrac12)\); its second row \((0,\tfrac12,\tfrac12)\) becomes \((\tfrac12,0,\tfrac12)\); and its third row \((1,0,0)\) becomes \((0,1,0)\). Therefore

AB=\begin{bmatrix} 0&\tfrac12&\tfrac12\\ \tfrac12&0&\tfrac12\\ 0&1&0 \end{bmatrix}.

Check: the product row sums are \(0+\tfrac12+\tfrac12=1\), \(\tfrac12+0+\tfrac12=1\), and \(0+1+0=1\); all displayed entries are nonnegative. Thus the computed composition is row-stochastic, as required.

Why Every Power Is a Transition Matrix

For a single homogeneous Markov chain, the one-step transition matrix is \(P\). The Chapman–Kolmogorov equations, established in the earlier material, identify the \(n\)-step transition matrix with the matrix power \(P^n\). The product theorem now supplies a direct guarantee that these powers have the necessary probability structure.

Corollary: If \(P\) is a row-stochastic matrix on a finite or countable state space \(S\), then \(P^n\) is row-stochastic for every integer \(n\ge0\). Here \(P^0=I\), the identity matrix.

Proof. For \(n=0\), \(P^0=I\). Each entry of \(I\) is nonnegative, and each row has one entry equal to one and all others zero, so each row sums to one. This includes the countable case because the identity row has only one nonzero entry. For \(n=1\), the claim is the assumption that \(P\) is row-stochastic. Now let \(n\ge1\) and suppose \(P^n\) is row-stochastic. By the product theorem, \(P^nP\) is row-stochastic, since both factors are row-stochastic on \(S\). By the definition and associativity of matrix powers, \(P^nP=P^{n+1}\). Thus \(P^{n+1}\) is row-stochastic. Induction proves the claim for every \(n\ge0\). \(\square\)

For countable \(S\), each product in this induction is defined by nonnegative series. The product theorem has already shown that these entries are well-defined and that each resulting row sums to one. The argument therefore does not require \(S\) to be finite.

Worked Example: Squaring and Cubing a Transition Matrix

Take

P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac12&\tfrac12\end{bmatrix}.

Its entries are nonnegative. Its row sums are \(\tfrac34+\tfrac14=1\) and \(\tfrac12+\tfrac12=1\), so \(P\) is row-stochastic. First compute \(P^2=PP\). Its entries are \(p_{11}^{(2)}=\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac12=\tfrac9{16}+\tfrac18=\tfrac{11}{16}\), \(p_{12}^{(2)}=\tfrac34\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac3{16}+\tfrac18=\tfrac5{16}\), \(p_{21}^{(2)}=\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac12=\tfrac38+\tfrac14=\tfrac58\), and \(p_{22}^{(2)}=\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac12=\tfrac18+\tfrac14=\tfrac38\). Hence

P^2=\begin{bmatrix}\tfrac{11}{16}&\tfrac5{16}\\[2pt]\tfrac58&\tfrac38\end{bmatrix}.

Check: \(P^2\) has nonnegative entries; its row sums are \(\tfrac{11}{16}+\tfrac5{16}=1\) and \(\tfrac58+\tfrac38=1\). Next multiply \(P^2P\). The entries of its first row are \(\tfrac{11}{16}\cdot\tfrac34+\tfrac5{16}\cdot\tfrac12=\tfrac{33}{64}+\tfrac{10}{64}=\tfrac{43}{64}\) and \(\tfrac{11}{16}\cdot\tfrac14+\tfrac5{16}\cdot\tfrac12=\tfrac{11}{64}+\tfrac{10}{64}=\tfrac{21}{64}\). The entries of its second row are \(\tfrac58\cdot\tfrac34+\tfrac38\cdot\tfrac12=\tfrac{15}{32}+\tfrac6{32}=\tfrac{21}{32}\) and \(\tfrac58\cdot\tfrac14+\tfrac38\cdot\tfrac12=\tfrac5{32}+\tfrac6{32}=\tfrac{11}{32}\). Therefore

P^3=\begin{bmatrix}\tfrac{43}{64}&\tfrac{21}{64}\\[2pt]\tfrac{21}{32}&\tfrac{11}{32}\end{bmatrix}.

Check: the entries of \(P^3\) are nonnegative, its first row sums to \(\tfrac{43}{64}+\tfrac{21}{64}=1\), and its second row sums to \(\tfrac{21}{32}+\tfrac{11}{32}=1\). This direct computation agrees with the induction result for both powers.

A Common Indexing Pitfall

When computing \(AB\), the entry \(c_{ij}\) uses row \(i\) of \(A\) and column \(j\) of \(B\), or equivalently it sums \(a_{ik}b_{kj}\) over the intermediate state \(k\). Repeating the same row of \(B\) for every value of \(k\) is an indexing error. It can produce an incorrect product even when the resulting row still sums to one, so a row-sum check alone does not verify every entry.

For the first row of the two-state example, the incorrect calculation that repeats row 1 of \(B\) gives the alleged product row \((\tfrac13,\tfrac23)\). Its sum is computed as

\tfrac12(\tfrac13+\tfrac23)+\tfrac12(\tfrac13+\tfrac23) =\tfrac12\cdot1+\tfrac12\cdot1 =1,

not \(\tfrac12\). The repeated-row error therefore gives the wrong product row \((\tfrac13,\tfrac23)\), but it does not give an incorrect row sum in this example. The correct calculation uses both rows of \(B\): the first row of \(A\) weights row 1 of \(B\) by \(\tfrac12\) and row 2 of \(B\) by \(\tfrac12\), giving \((\tfrac12,\tfrac12)\). To check a product reliably, verify both the individual entries using the correct intermediate index and the row sums.

The preservation result is useful whenever a transition is built by composing valid transition rules or by repeating one rule. It separates two questions: whether the matrix multiplication is computed correctly, and whether its result can still represent transition probabilities. The theorem answers the second question; entry-by-entry calculations and row checks address the first.

Check Your Understanding

Use the definition and proofs above to justify each answer.

State the two conditions a matrix must satisfy to be row-stochastic.
For countable \(S\), why is it valid to exchange the sums when proving that a product row sums to one?
If \(A\) and \(B\) are row-stochastic on the same state space, what is the formula for \((AB)_{ij}\), and what does the index \(k\) represent?
Why must the identity matrix be included as the \(n=0\) case when proving the claim about all nonnegative powers?
Why can a wrong entry calculation still produce a row whose entries sum to one?

How Matrix Products Preserve Stochasticity

What You'll Learn