Transition Semigroups for Finite-State Chains

Transition Probabilities at a Fixed Time

A continuous-time Markov chain is described not only by its jump rates but also by the probabilities of its state at a specified later time. These probabilities answer questions such as: if the chain starts in state $i$, what is the chance it is in state $j$ after $t$ time units? Organizing all such probabilities into a matrix makes the effect of elapsed time explicit and reveals a consistency rule across different time intervals.

Let $(X_t)_{t\ge0}$ be a time-homogeneous continuous-time Markov chain on a finite state space $S=\{1,\ldots,d\}$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Use the natural filtration $\mathcal{F}_t=\sigma(X_u:0\le u\le t)$. Write $\mathbb{P}_i$ for the law of the chain started at $i$, so $X_0=i$ with probability one. The Markov property says that, given the present state, the conditional distribution of the future does not depend on the past; time homogeneity says that this conditional transition law depends on the time interval, not on its starting time.

Definition: For $t\ge0$ and states $i,j\in S$, the transition probability from $i$ to $j$ over time $t$ is $p_{ij}(t)=\mathbb{P}_i(X_t=j)$. The transition matrix is $P(t)=(p_{ij}(t))_{i,j\in S}$. Its row indexed by $i$ gives the distribution at time $t$ when the chain starts at $i$.

Every entry is nonnegative, and for a fixed initial state $i$, the events $\{X_t=j\}$, as $j$ ranges over $S$, are disjoint and together exhaust all possibilities. Therefore $\sum_{j\in S}p_{ij}(t)=1$. Thus $P(t)$ is row-stochastic. At time zero the chain is still in its initial state, so $P(0)=\mathbf{I}$, the identity matrix.

If the initial distribution is the row vector $\mu$, where $\mu_i=\mathbb{P}(X_0=i)$, then the distribution at time $t$ is $\mu P(t)$. Indeed, for each state $j$, conditioning on the initial state gives $\mathbb{P}(X_t=j)=\sum_i\mu_i p_{ij}(t)$. This row convention will also determine the order of matrix multiplication when time intervals are combined.

The Semigroup Property

The transition matrices over successive intervals fit together by matrix multiplication. The result is called the semigroup property. It expresses a consistency condition: evolving for $s$ time units and then for $t$ more time units gives the same transition probabilities as evolving for $s+t$ time units. The finite state space ensures that the sum over intermediate states is finite.

Theorem (Semigroup property): For a time-homogeneous Markov chain on a finite state space, $P(0)=\mathbf{I}$, every $P(t)$ is row-stochastic, and for all $s,t\ge0$, $$ P(s+t)=P(s)P(t). $$

Proof. The identity at time zero and the row-stochastic property follow from the definitions and the fact that the chain occupies exactly one state at every time. To prove the multiplication rule, fix states $i,j$ and times $s,t\ge0$. Partition the event $\{X_{s+t}=j\}$ according to the value $k$ of $X_s$. By the Markov property and time homogeneity, conditional on $X_s=k$, the probability of being in $j$ after a further interval $t$ is $p_{kj}(t)$. Consequently, $$ \mathbb{P}_i(X_{s+t}=j) =\sum_{k\in S}\mathbb{P}_i(X_s=k)\,p_{kj}(t) =\sum_{k\in S}p_{ik}(s)p_{kj}(t). $$ The left side is $p_{ij}(s+t)$, and the last expression is the $(i,j)$ entry of $P(s)P(t)$. This holds for every $i,j$, so the matrices are equal. $\square$

The order of the factors has a direct interpretation: $P(s)$ carries the chain from its initial state to the intermediate state, and $P(t)$ carries it from that intermediate state to the final state. In general, do not reverse the factors. Also, the one-parameter semigroup notation $P(t)$ depends on time homogeneity. A time-inhomogeneous chain instead has transition matrices indexed by both endpoints of an interval.

Worked Example: One State Can Be Left, but Not Re-entered

Consider $S=\{0,1\}$, with state $0$ left at rate $1$ and state $1$ absorbing. Starting from $0$, the holding time before the jump is exponential with rate $1$. Thus the probability of still being in $0$ at time $t$ is $e^{-t}$, and the probability of having entered state $1$ is $1-e^{-t}$. Starting from $1$, the chain remains there.

At $t=\ln 2$, these probabilities give $e^{-\ln 2}=\tfrac12$ and $1-e^{-\ln 2}=1-\tfrac12=\tfrac12$. In the state order $0,1$,

P(\ln 2)= \begin{bmatrix} \tfrac12&\tfrac12\\ 0&1 \end{bmatrix}.

Check: the first row sums to $\tfrac12+\tfrac12=1$, and the second row sums to $0+1=1$. The entry $p_{01}(\ln 2)=\tfrac12$ is the probability of having made the transition by time $\ln 2$, not the probability of making a jump exactly at that time.

Worked Example: Competing Exits to Two Absorbing States

Let $S=\{0,1,2\}$. From state $0$, the chain jumps to state $1$ at rate $1$ or to state $2$ at rate $1$; states $1$ and $2$ are absorbing. The total rate of leaving $0$ is $2$, so the probability of still being in $0$ at time $t$ is $e^{-2t}$. The density of a jump from $0$ to either specified destination at time $u$ is $e^{-2u}$: the chain must remain in $0$ until $u$, then make that particular rate-$1$ jump.

Therefore, for either destination, the probability of having jumped there by time $t$ is $\int_0^t e^{-2u}\,du=\tfrac12(1-e^{-2t})$. At $t=\ln 2$, $e^{-2t}=e^{-\ln 4}=\tfrac14$, so each destination has probability $\tfrac12(1-\tfrac14)=\tfrac38$. Hence

P(\ln 2)= \begin{bmatrix} \tfrac14&\tfrac38&\tfrac38\\ 0&1&0\\ 0&0&1 \end{bmatrix}.

Check: the first row sums to $\tfrac14+\tfrac38+\tfrac38=1$; the other rows each sum to $1$ because their states are absorbing. The probabilities of the two destinations are equal, and their sum $\tfrac38+\tfrac38=\tfrac34$ is the probability of having left state $0$, namely $1-\tfrac14=\tfrac34$.

Reading a Matrix as a Distribution Update

The row indexed by the current state describes a full probability distribution over the state space at the later time. If the initial state is not known but has distribution $\mu$, the rows are mixed according to their initial probabilities. This is why distributions are row vectors under the convention used here.

Worked Example: Evolving an Initial Distribution

Use the one-way chain from the first example at time $t=\ln 2$, with initial distribution $\mu=(\tfrac34,\tfrac14)$ in state order $0,1$. The transition matrix is row-stochastic: its rows are $(\tfrac12,\tfrac12)$ and $(0,1)$, each summing to $1$. Multiply the row vector by the matrix:

\mu P(\ln 2) = \begin{bmatrix}\tfrac34&\tfrac14\end{bmatrix} \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} = \begin{bmatrix} \tfrac34\cdot\tfrac12+\tfrac14\cdot0& \tfrac34\cdot\tfrac12+\tfrac14\cdot1 \end{bmatrix} = \begin{bmatrix}\tfrac38&\tfrac58\end{bmatrix}.

Check: the resulting probabilities sum to $\tfrac38+\tfrac58=1$. Directly, state $0$ at time $\ln 2$ requires starting in $0$ and remaining there, with probability $\tfrac34\cdot\tfrac12=\tfrac38$. State $1$ has the remaining probability, $\tfrac14+\tfrac34\cdot\tfrac12=\tfrac14+\tfrac38=\tfrac58$.

The semigroup property also supplies an important consistency check on a proposed family of transition matrices. For the one-way chain, let $s=t=\ln 2$. The two-interval matrix product is

P(\ln 2)P(\ln 2) = \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} = \begin{bmatrix}\tfrac14&\tfrac34\\0&1\end{bmatrix}.

Over the combined interval $2\ln 2=\ln 4$, the probability of still being in state $0$, starting from $0$, is $e^{-\ln 4}=\tfrac14$; the probability of being in state $1$ is $1-\tfrac14=\tfrac34$. Starting from state $1$ still gives probability $1$ of remaining there. Thus the directly computed $P(\ln 4)$ equals the product. Its rows sum to $\tfrac14+\tfrac34=1$ and $0+1=1$, as required.

Common Pitfall: Mixing Up Row and Column Conventions

Suppose the initial state in the one-way example is $0$, so the initial row distribution is $(1,0)$. The correct update is $$ \begin{bmatrix}1&0\end{bmatrix}P(\ln 2) = \begin{bmatrix}\tfrac12&\tfrac12\end{bmatrix}. $$ A common incorrect calculation treats the initial distribution as a column vector but still multiplies it on the left by $P(\ln 2)$. That gives $$ \begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix} \begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}\tfrac12\\0\end{bmatrix}, $$ whose entries sum to $\tfrac12$, not $1$. It is not a probability distribution. With the row-stochastic convention, distributions multiply on the left as row vectors. If a column representation is preferred, it must instead be updated using $P(t)^{\mathsf T}$ on the left: $P(\ln 2)^{\mathsf T}(1,0)^{\mathsf T}=(\tfrac12,\tfrac12)^{\mathsf T}$.

Keep three features in view when interpreting transition semigroups: each row is a distribution from one starting state, the entry $p_{ij}(t)$ refers to a time interval of length $t$, and successive intervals compose in chronological order as $P(s)P(t)$. These conventions make the semigroup law a direct expression of the Markov property, rather than merely a matrix identity.

Check Your Understanding

Use the row-stochastic convention throughout, and check that any proposed distribution has nonnegative entries summing to one.

For a finite-state chain, explain why $\sum_j p_{ij}(t)=1$ for each fixed state $i$ and time $t$.
In the one-way chain with rate $1$, what does $p_{01}(\ln 2)$ mean? Why is it not the probability of a jump at the exact time $\ln 2$?
For the competing-exits example, verify that the probability of having left state $0$ by time $\ln 2$ equals the sum of the probabilities of reaching states $1$ and $2$.
If the initial distribution is a row vector $\mu$, write the formula for the distribution at time $t$ and explain the role of its $j$th entry.
State the semigroup property and identify the Markov and time-homogeneity facts used to prove it.

Transition Semigroups for Finite-State Chains

What You'll Learn