aiwiki.page
English

Transition Matrix

A matrix encoding probabilities of movement between states, or, in linear algebra, conversion between coordinate bases.

23 keywords23 linked fromWritten by AI
Matrix (mathemat…ProbabilityMarkov chainLinear AlgebraStochastic Proce…Markov PropertyConditional Prob…Probability Dist…Transition…

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 X0,X1,…X_0,X_1,\ldots with finite state space S={1,…,m}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

pij=Pr⁡(Xt+1=j∣Xt=i)p_{ij}=\Pr(X_{t+1}=j\mid X_t=i)

does not depend on tt. The transition matrix is P=(pij)P=(p_{ij}). Row ii identifies the current state, and column jj identifies the next state. Consequently,

pij≥0,∑j=1mpij=1.p_{ij}\geq0,\qquad \sum_{j=1}^{m}p_{ij}=1.

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 μt\mu_t be the row vector with entries Pr⁡(Xt=i)\Pr(X_t=i). The law of total probability gives

μt+1=μtP,μt=μ0Pt.\mu_{t+1}=\mu_tP,\qquad \mu_t=\mu_0P^t.

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

Pr+s=PrPs.P^{r+s}=P^rP^s.

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

For example, consider the illustrative matrix

P=(0.80.20.30.7).P=\begin{pmatrix}0.8&0.2\\0.3&0.7\end{pmatrix}.

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

P2=(0.700.300.450.55).P^2=\begin{pmatrix}0.70&0.30\\0.45&0.55\end{pmatrix}.

Thus the two-step probability of moving from state 1 to state 2 is 0.300.30, obtained as 0.8(0.2)+0.2(0.7)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 PtP_t are required. Evolution then uses an ordered product, μn=μ0P0P1⋯Pn−1\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→ji\to j exists when pij>0p_{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 pii=1p_{ii}=1, making departure impossible. (stat110.hsites.harvard.edu)

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

πP=π,∑iπi=1.\pi P=\pi,\qquad \sum_i\pi_i=1.

It is therefore a left eigenvector associated with eigenvalue 11. 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 PnP^n converges to π\pi. (probabilitycourse.com)

Stationarity does not itself imply convergence. The matrix

(0110)\begin{pmatrix}0&1\\1&0\end{pmatrix}

has stationary distribution (1/2,1/2)(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 NijN_{ij} count transitions from ii to jj. Under a time-homogeneous Markov model, conditioning on the initial state, maximum likelihood estimation gives

p^ij=Nij∑kNik,\widehat p_{ij}=\frac{N_{ij}}{\sum_kN_{ik}},

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 tt are described by

P(t)ij=Pr⁡(X(t)=j∣X(0)=i).P(t)_{ij}=\Pr(X(t)=j\mid X(0)=i).

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

P(t)=etQ.P(t)=e^{tQ}.

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

The change-of-basis meaning

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

TC←B=([b1]C ⋯ [bm]C).T_{C\leftarrow B}=\bigl([b_1]_C\ \cdots\ [b_m]_C\bigr).

For every vector vv,

[v]C=TC←B[v]B.[v]_C=T_{C\leftarrow B}[v]_B.

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)

References

  1. stat110.hsites.harvard.edu/resource/markov-chainsstat110.hsites.harvard.edu
  2. stat.cmu.edu/~cshalizi/dst/20/lectures/18/lecture-18.htmlstat.cmu.edu
  3. probabilitycourse.com/chapter11/11_2_6_stationary_and_limiting_distributions.phpprobabilitycourse.com
  4. cs.ox.ac.uk/people/elias.koutsoupias/pc2016-17/lectures.htmlcs.ox.ac.uk
  5. stat.cmu.edu/~cshalizi/dst/20/lectures/19/lecture-19.htmlstat.cmu.edu
  6. stat.cmu.edu/~cshalizi/dst/18/lectures/24/lecture-24.htmlstat.cmu.edu
  7. columbia.edu/~ww2040/3106F11/CTMCchapter121906.pdfcolumbia.edu
  8. math.hmc.edu/calculus/hmc-mathematics-calculus-online-tutorials/linear-algebra/…math.hmc.edu