Transition Matrix

A transition matrix is a matrix that represents movement between states or coordinate descriptions. In probability theory, it records the probabilities of transitions in a Markov chain. In linear algebra, the same term can denote a change-of-basis matrix, which converts coordinates between two bases of a vector space. These meanings require different assumptions: a probability transition matrix has nonnegative entries and normalized rows or columns, whereas a change-of-basis matrix must be invertible. (stat110.hsites.harvard.edu)

Definition for a Markov chain

Consider a discrete-time stochastic process $X_0,X_1,\ldots$ with finite state space $S=\{1,\ldots,m\}$. Its Markov property means that, conditional on the current state, the next state does not depend on earlier states. For a time-homogeneous chain, the conditional probability

does not depend on $t$. The transition matrix is $P=(p_{ij})$. Row $i$ identifies the current state, and column $j$ identifies the next state. Consequently,

A matrix satisfying these conditions is called a row-stochastic matrix. Each row is a probability distribution over possible destinations, including the possibility of remaining in the same state. (stat110.hsites.harvard.edu)

Some authors instead use column-stochastic matrices, whose columns sum to one. The two conventions are related by matrix transposition. The convention must be specified because it determines which side of the matrix a probability vector multiplies. A transition matrix describes conditional movement, not the initial distribution; both are needed to specify the chain's probabilistic evolution. (stat.cmu.edu)

Evolution and multiple-step transitions

Under the row-stochastic convention, let $\mu_t$ be the row vector with entries $\Pr(X_t=i)$. The law of total probability gives

The entry $(P^n)_{ij}$ is the probability of reaching state $j$ after $n$ steps when starting at $i$. Matrix multiplication sums the probabilities of paths through intermediate states. This yields the Chapman–Kolmogorov equations,

Here $P^0=I$, the identity matrix, representing zero elapsed steps. (stat.cmu.edu)

For example, consider the illustrative matrix

Starting in state 1 gives $\mu_0=(1,0)$, hence $\mu_1=(0.8,0.2)$. Direct multiplication gives

Thus the two-step probability of moving from state 1 to state 2 is $0.30$, obtained as $0.8(0.2)+0.2(0.7)$. These are calculations for a hypothetical chain, not empirical measurements.

If transition probabilities vary with time, separate matrices $P_t$ are required. Evolution then uses an ordered product, $\mu_n=\mu_0P_0P_1\cdots P_{n-1}$, rather than a power of one fixed matrix. (stat.cmu.edu)

Structure and long-run behavior

A transition matrix can be represented by a weighted directed graph: states are vertices, and an edge $i\to j$ exists when $p_{ij}>0$. The chain is irreducible if every state can reach every other state with positive probability in some number of steps. A state is absorbing if $p_{ii}=1$, making departure impossible. (stat110.hsites.harvard.edu)

A stationary distribution is a probability row vector $\pi$ satisfying

It is therefore a left eigenvector associated with eigenvalue $1$. For a finite irreducible chain, the stationary distribution is unique. If the chain is also aperiodic, every initial distribution converges to it, and every row of $P^n$ converges to $\pi$. (probabilitycourse.com)

Stationarity does not itself imply convergence. The matrix

has stationary distribution $(1/2,1/2)$, but a chain starting in one state alternates indefinitely. This distinction separates an invariant distribution from a limiting distribution. (cs.ox.ac.uk)

Estimation from observations

For observed state sequences, let $N_{ij}$ count transitions from $i$ to $j$. Under a time-homogeneous Markov model, conditioning on the initial state, maximum likelihood estimation gives

provided the denominator is positive. Transition counts are sufficient statistics for this conditional likelihood. If no departure from a state is observed, its transition row cannot be estimated uniquely by this formula. (stat.cmu.edu)

In a hidden Markov model, states are latent rather than directly observed. Estimation therefore uses inferred, probability-weighted transition counts, commonly within the expectation–maximization algorithm, together with a model of the observations emitted by each state. (stat.cmu.edu)

Continuous-time transition matrices

For a finite, time-homogeneous continuous-time Markov chain, transitions over elapsed time $t$ are described by

These matrices satisfy $P(0)=I$ and $P(s+t)=P(s)P(t)$. Their infinitesimal generator $Q$ has nonnegative off-diagonal entries and rows summing to zero. Finite-time probabilities are obtained through the matrix exponential,

The generator contains transition rates, not probabilities; its diagonal entries are nonpositive. It must therefore be distinguished from $P(t)$. (columbia.edu)

The change-of-basis meaning

Let $B=(b_1,\ldots,b_m)$ and $C$ be ordered bases of the same finite-dimensional vector space. The transition matrix from $B$-coordinates to $C$-coordinates has columns

For every vector $v$,

Its inverse performs the reverse conversion. Unlike a probability transition matrix, it need not have nonnegative entries or normalized rows. The underlying vector remains unchanged; only its coordinate description changes. (math.hmc.edu)