One-Step Prediction with a Transition Matrix

From a Transition Rule to a Predicted Distribution

A transition matrix describes what may happen next from each current state. An initial distribution describes how likely the chain is to be in each current state now. One-step prediction combines these two pieces: each possible current state contributes its probability of being occupied, weighted by its transition probabilities. With row vectors, this calculation is a matrix product in a particular order.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $(X_n)_{n\ge 0}$ be a discrete-time Markov chain with finite state space $S=\{1,\ldots,r\}$. Its initial distribution is the row vector $\mu_0$, where $\mu_0(i)=\mathbb{P}(X_0=i)$. Let $P=(p_{ij})$ be its one-step transition matrix, where $p_{ij}$ is the probability of moving from state $i$ to state $j$. Each entry is nonnegative and each row sums to $1$.

Definition (one-step Markov assumption): With $\mathcal{F}_0=\sigma(X_0)$, the transition law satisfies $\mathbb{P}(X_1=j\mid\mathcal{F}_0)=p_{X_0j}$ almost surely for every $j\in S$. The numbers $p_{ij}$ specify a transition kernel for all states $i$, including states to which $X_0$ assigns probability zero. The distribution of $X_1$ is the row vector $\mu_1$ with coordinates $\mu_1(j)=\mathbb{P}(X_1=j)$.

The key idea is to calculate the probability of each possible next state separately. For a fixed destination $j$, the chain can arrive there from any current state $i$. The probability of being at $i$ initially is $\mu_0(i)$, and the conditional probability of then moving to $j$ is $p_{ij}$. Adding these contributions gives the prediction formula.

Theorem (one-step prediction): Under the one-step Markov assumption, the distribution of $X_1$ is $$ \mu_1=\mu_0P, $$ or, coordinate by coordinate, $\mu_1(j)=\sum_{i\in S}\mu_0(i)p_{ij}$.

Proof. Fix any $j\in S$. By the definition of the distribution of $X_1$ and the rule of total probability over the disjoint events $\{X_0=i\}$, $\mathbb{P}(X_1=j)=\sum_{i\in S}\mathbb{P}(X_0=i,X_1=j)$. For each $i$, conditional expectation gives $\mathbb{P}(X_0=i,X_1=j)=\mathbb{E}[\mathbf{1}_{\{X_0=i\}}\mathbf{1}_{\{X_1=j\}}]=\mathbb{E}[\mathbf{1}_{\{X_0=i\}}\mathbb{P}(X_1=j\mid\mathcal{F}_0)]$. The Markov assumption makes the conditional probability $p_{X_0j}$; on $\{X_0=i\}$, this equals $p_{ij}$. Thus the joint probability is $p_{ij}\mathbb{P}(X_0=i)=p_{ij}\mu_0(i)$, including when $\mu_0(i)=0$. Summing over $i$ yields $\mu_1(j)=\sum_i\mu_0(i)p_{ij}$. This is exactly the $j$th coordinate of the row-vector product $\mu_0P$, proving the formula for every coordinate. $\square$

The formula also produces a probability distribution, as it must. Indeed, its coordinates are nonnegative because they are sums of products of nonnegative numbers. Moreover, using the fact that every row of $P$ sums to $1$,

\sum_{j\in S}\mu_1(j) =\sum_{j\in S}\sum_{i\in S}\mu_0(i)p_{ij} =\sum_{i\in S}\mu_0(i)\sum_{j\in S}p_{ij} =\sum_{i\in S}\mu_0(i) =1.

All sums here are finite, so changing their order does not require any additional convergence condition. This calculation is a useful check whenever a predicted distribution has been computed by hand.

Corollary (probability of a next-time event): For any subset $A\subseteq S$, $$ \mathbb{P}(X_1\in A)=\sum_{j\in A}\mu_1(j) =\sum_{i\in S}\mu_0(i)\sum_{j\in A}p_{ij}. $$

Proof. The events $\{X_1=j\}$, for $j\in A$, are disjoint and their union is $\{X_1\in A\}$. Therefore $\mathbb{P}(X_1\in A)=\sum_{j\in A}\mathbb{P}(X_1=j)=\sum_{j\in A}\sum_{i\in S}\mu_0(i)p_{ij}$, by the theorem. Rearranging the finite sums gives the stated expression. If $A$ is empty, both sums are zero; if $A=S$, the expression is $\sum_i\mu_0(i)\sum_jp_{ij}=1$. Thus the formula includes both boundary cases. $\square$

Computing the Matrix Product

For row vectors, the coordinate for destination $j$ is obtained from column $j$ of $P$: multiply each entry $p_{ij}$ by the current probability $\mu_0(i)$, then add over the possible starting states. Before using a matrix, verify its rows sum to $1$. Before accepting the answer, verify that its coordinates are nonnegative and sum to $1$.

Worked Example: Prediction for a Two-State Chain

Let $S=\{1,2\}$, let the initial distribution be $\mu_0=(\tfrac25,\tfrac35)$, and let $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac13&\tfrac23\end{bmatrix}. $$ The first row sums to $\tfrac34+\tfrac14=1$, and the second row sums to $\tfrac13+\tfrac23=1$. The initial probabilities sum to $\tfrac25+\tfrac35=1$, so both inputs are probability distributions.

For destination $1$, multiply the probability of starting in each state by that state's probability of moving to $1$: $$ \mu_1(1)=\tfrac25\cdot\tfrac34+\tfrac35\cdot\tfrac13 =\tfrac6{20}+\tfrac3{15} =\tfrac3{10}+\tfrac15 =\tfrac12. $$ For destination $2$, the corresponding calculation is $$ \mu_1(2)=\tfrac25\cdot\tfrac14+\tfrac35\cdot\tfrac23 =\tfrac1{10}+\tfrac6{15} =\tfrac1{10}+\tfrac25 =\tfrac12. $$ Hence $\mu_1=(\tfrac12,\tfrac12)$. Check: the two entries sum to $\tfrac12+\tfrac12=1$, and direct row-vector multiplication gives $(\tfrac25,\tfrac35)P=(\tfrac3{10}+\tfrac15,\tfrac1{10}+\tfrac25)=(\tfrac12,\tfrac12)$.

Worked Example: Prediction for a Three-State Chain

Let $S=\{1,2,3\}$, let $\mu_0=(\tfrac12,\tfrac13,\tfrac16)$, and take $$ P=\begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\[2pt] \tfrac14&\tfrac12&\tfrac14\\[2pt] 0&\tfrac25&\tfrac35 \end{bmatrix}. $$ The row sums are $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $0+\tfrac25+\tfrac35=1$. Also, $\tfrac12+\tfrac13+\tfrac16=1$ for the initial distribution.

Compute each destination coordinate using the corresponding column: $$ \begin{aligned} \mu_1(1) &=\tfrac12\cdot\tfrac12+\tfrac13\cdot\tfrac14+\tfrac16\cdot0 =\tfrac14+\tfrac1{12}+0 =\tfrac13,\\ \mu_1(2) &=\tfrac12\cdot\tfrac13+\tfrac13\cdot\tfrac12+\tfrac16\cdot\tfrac25 =\tfrac16+\tfrac16+\tfrac1{15} =\tfrac13+\tfrac1{15} =\tfrac25,\\ \mu_1(3) &=\tfrac12\cdot\tfrac16+\tfrac13\cdot\tfrac14+\tfrac16\cdot\tfrac35 =\tfrac1{12}+\tfrac1{12}+\tfrac1{10} =\tfrac16+\tfrac1{10} =\tfrac4{15}. \end{aligned} $$ Thus $\mu_1=(\tfrac13,\tfrac25,\tfrac4{15})$. Check: the result sums to $\tfrac13+\tfrac25+\tfrac4{15}=\tfrac5{15}+\tfrac6{15}+\tfrac4{15}=1$. Each coordinate also matches its column calculation above, so the matrix product has been checked coordinate by coordinate.

Fixed Starting States and Event Probabilities

A fixed starting state is a special case of an initial distribution. If $X_0=i$ with probability $1$, then $\mu_0$ has a $1$ in coordinate $i$ and $0$ elsewhere. Multiplying this row vector by $P$ selects row $i$, so the next-time distribution is exactly the transition probabilities out of $i$. This is also why the product uses the initial distribution on the left: its entries weight the rows of the transition matrix.

Worked Example: Starting in a Known State

Use the three-state transition matrix from the previous example, but now start in state $2$ with probability $1$. The initial distribution is $\mu_0=(0,1,0)$. The transition rows still sum to $1$: $\tfrac12+\tfrac13+\tfrac16=1$, $\tfrac14+\tfrac12+\tfrac14=1$, and $0+\tfrac25+\tfrac35=1$.

Multiplication selects the second row: $$ \mu_1=(0,1,0)P=(\tfrac14,\tfrac12,\tfrac14). $$ In particular, for $A=\{1,3\}$, the probability of being in $A$ at time $1$ is $\mathbb{P}(X_1\in A)=\mu_1(1)+\mu_1(3)=\tfrac14+\tfrac14=\tfrac12$. Check: the selected row sums to $\tfrac14+\tfrac12+\tfrac14=1$, and the event probability is also the sum of the transitions from state $2$ into $A$, $p_{21}+p_{23}=\tfrac14+\tfrac14=\tfrac12$.

The event formula can be useful when the full distribution is not needed. For example, to find the probability of entering a particular group of states, add the transition probabilities into that group for each current state, then weight those sums by the initial probabilities. The theorem and corollary show that this shortcut gives the same answer as first computing all coordinates of $\mu_1$ and then adding the relevant ones.

Common Mistake: Reversing the Multiplication

With the row-vector convention, the prediction is $\mu_0P$, not $P\mu_0$. The order matters: $\mu_0$ records weights on current states, and the rows of $P$ give the next-state distributions for those states. A transposed calculation may even produce numbers that do not sum to $1$.

For the two-state example, incorrectly treating $\mu_0$ as a column and calculating $P\mu_0$ gives first coordinate $\tfrac34\cdot\tfrac25+\tfrac14\cdot\tfrac35=\tfrac3{10}+\tfrac3{20}=\tfrac9{20}$, and second coordinate $\tfrac13\cdot\tfrac25+\tfrac23\cdot\tfrac35=\tfrac2{15}+\tfrac25=\tfrac8{15}$. Their sum is $\tfrac9{20}+\tfrac8{15}=\tfrac{27}{60}+\tfrac{32}{60}=\tfrac{59}{60}$, not $1$. The correction is to use the row product: $\mu_0P=(\tfrac12,\tfrac12)$, as computed above. A sum other than $1$ is a warning to check the vector convention and multiplication order.

One-step prediction does not require that the chain start in a particular state, nor does it require that the initial probabilities be equal. It requires the initial law, a row-stochastic transition matrix in the stated state order, and the one-step Markov transition assumption. When these are aligned, each predicted coordinate is a weighted sum of a column, and the full row-vector product gives the distribution at the next time.

Check Your Understanding

For each question, keep the row-vector convention and verify that any proposed distribution sums to $1$.

If $\mu_0=(\tfrac13,\tfrac23)$ and $P=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac14&\tfrac34\end{bmatrix}$, what is $\mu_1$? Check both row sums before multiplying.
For a chain starting at state $i$ with probability $1$, explain why the distribution at time $1$ is row $i$ of $P$.
For a subset $A\subseteq S$, express $\mathbb{P}(X_1\in A)$ directly in terms of $\mu_0$ and the entries of $P$.
Why does $\mu_0P$ have nonnegative entries that sum to $1$ when $\mu_0$ is a probability distribution and $P$ is row-stochastic?
In the two-state example, what does a result whose coordinates sum to $\tfrac{59}{60}$ indicate about the calculation?

One-Step Prediction with a Transition Matrix

What You'll Learn