Markov Chain

A Markov chain is a stochastic process {X_t}_t∈T evolving over a countable or continuous state space S that satisfies the Markov property (memorylessness): conditioned on the present state X_t, the probability distribution of any future state X_t+s (for s > 0) is statistically independent of all past states X_u (for u < t). Introduced in 1906 by the Russian mathematician Andrey Andreyevich Markov to prove that the law of large numbers and central limit theorem hold for dependent random variables—famously demonstrated by analyzing the alternation of vowels and consonants in Alexander Pushkin's verse novel Eugene Onegin—Markov chains provide the mathematical foundation for equilibrium statistical mechanics, queuing theory, Bayesian inference via Markov chain Monte Carlo (MCMC), and molecular evolution models in maximum-likelihood phylogenetics.

Depending on the index set T, a Markov chain is classified as a discrete-time Markov chain (DTMC) when transitions occur at integer steps T = {0, 1, 2, ...} governed by a stochastic transition matrix P, or a continuous-time Markov chain (CTMC) when transitions occur at arbitrary real times T = 0, ∞) governed by an infinitesimal rate generator matrix Q. In bioinformatics and genomics, discrete-time chains and Hidden Markov Models (HMMs) power profile [sequence alignment, CpG island detection, and eukaryotic gene prediction, whereas continuous-time Markov chains parameterize nucleotide, amino-acid, and codon substitution models evaluated along evolutionary trees via Felsenstein's tree-pruning algorithm.

Discrete-Time Transition Matrices and Chapman-Kolmogorov Equations

For a discrete-time Markov chain {X_n}_n≥0 on a finite state space S = {1, 2, ..., A}, the first-order Markov property states that for any sequence of states i₀, i₁, ..., i_n−1, i, j ∈ S:

P(X_n+1 = j | X_n = i, X_n−1 = i_n−1, ..., X₀ = i₀) = P(X_n+1 = j | X_n = i)

When these one-step transition probabilities are invariant with respect to step index n, the chain is time-homogeneous, and its dynamics are completely specified by the A × A row-stochastic transition matrix P = (P_ij), where P_ij = P(X_n+1 = j | X_n = i) satisfies non-negativity (P_ij ≥ 0 for all i, j) and row conservation (∑_j=1^A P_ij = 1 for every row i). If the initial state distribution at n = 0 is the row vector μ⁽⁰⁾ = [μ₁⁽⁰⁾, ..., μ_A⁽⁰⁾], the distribution after n steps is obtained by vector-matrix multiplication μ⁽ⁿ⁾ = μ⁽⁰⁾ Pⁿ.

Summing over all possible intermediate states k ∈ S at step m between 0 and m + n yields the Chapman-Kolmogorov equations for multi-step transition probabilities P_ij^(m+n) = P(X_m+n = j | X₀ = i):

P_ij^(m+n) = ∑_k=1^A P_ik^(m) P_kj⁽ⁿ⁾ ⟺ P^(m+n) = P^(m) P⁽ⁿ⁾

Thus, multi-step transition matrices form a multiplicative semigroup generated by matrix powers Pⁿ.

Continuous-Time Rate Generators (Q) and the Matrix Exponential exp(Qt)

In molecular evolution and chemical kinetics, state transitions occur continuously over branch length or physical time t ∈ [0, ∞). A time-homogeneous continuous-time Markov chain (CTMC) {X(t)}_t≥0 is defined by a family of transition probability matrices P(t) satisfying the continuous Chapman-Kolmogorov semigroup identity P(t + s) = P(t)P(s) with P(0) = I. Differentiating P(t) at t = 0 defines the A × A infinitesimal generator (instantaneous rate) matrix Q = P′(0):

• For off-diagonal pairs i ≠ j, q_ij ≥ 0 is the instantaneous rate of jumping from state i to state j: P_ij(Δt) = q_ij Δt + o(Δt) as Δt → 0.
• For diagonal entries, q_ii = −∑_j≠i q_ij ≤ 0 so that every row of Q sums to zero (∑_j=1^A q_ij = 0), and the waiting time in state i before jumping to any other state follows an exponential distribution with rate parameter λ_i = −q_ii and density f(t) = λ_i exp(−λ_i t).

Differentiating P(t + Δt) = P(t)P(Δt) and P(Δt + t) = P(Δt)P(t) yields Kolmogorov's forward equation dP(t)/dt = P(t)Q and backward equation dP(t)/dt = QP(t), whose unique solution for t ≥ 0 is the matrix exponential:

P(t) = exp(Qt) = ∑_m=0^∞ (Qt)^m / m!

When Q is diagonalizable as Q = U Λ U⁻¹ with eigenvalues λ₁, ..., λ_A, the transition matrix for any branch length t is computed in O(A³) setup operations via spectral decomposition P(t) = U diag(e^λ₁t, ..., e^λ_At) U⁻¹.

Irreducibility, Aperiodicity, and the Perron-Frobenius Ergodic Theorem

The long-run asymptotic behavior of a Markov chain depends on the structural connectivity of its transition graph:

• Irreducibility: A Markov chain is irreducible if every state j ∈ S can be reached from every state i ∈ S in a finite number of steps (for every pair (i, j), there exists n ≥ 1 such that P_ij⁽ⁿ⁾ > 0). In an irreducible finite chain, all states belong to a single communicating class and are positive recurrent.
• Aperiodicity: The period d(i) of state i is the greatest common divisor of all return step counts {n ≥ 1 : P_ii⁽ⁿ⁾ > 0}. A state with d(i) = 1 is aperiodic (guaranteed whenever P_ii > 0, i.e., a self-loop exists). An irreducible finite Markov chain that is also aperiodic is called ergodic.

By the Perron-Frobenius theorem for primitive non-negative matrices, an ergodic transition matrix P has a simple dominant eigenvalue λ₁ = 1, while all remaining eigenvalues satisfy |λ_k| < 1 for k = 2, ..., A. Consequently, there exists a unique strictly positive stationary probability distribution π = (π₁, ..., π_A) with ∑_i=1^A π_i = 1 satisfying the global balance equation:

π P = π (for DTMC) or π Q = 0 (for CTMC)

Regardless of the starting state i, the n-step transition probabilities converge geometrically to π at an exponential decay rate governed by the spectral gap γ = 1 − |λ₂|: lim_n→∞ P_ij⁽ⁿ⁾ = π_j. Moreover, the ergodic theorem guarantees that empirical time averages along a single simulated trajectory converge with probability 1 to ensemble expectations under π, which justifies estimating posterior expectations from a single MCMC run in Bayesian inference.

Detailed Balance (Time-Reversibility) and Biological Applications

A stationary distribution π requires only global balance—that the total probability flux entering state i from all states equals the total probability flux leaving state i (∑_j≠i π_j P_ji = ∑_j≠i π_i P_ij). A stronger condition is detailed balance (time-reversibility), which requires pairwise flux equality between every individual pair of states i and j:

π_i P_ij = π_j P_ji (for DTMC) and π_i q_ij = π_j q_ji (for CTMC)

Summing either detailed balance identity over i ∈ S immediately yields ∑_i π_i P_ij = π_j ∑_i P_ji = π_j, confirming that any distribution π satisfying detailed balance is automatically the stationary distribution of the chain. Detailed balance implies that D^1/2 Q D^−1/2 (where D = diag(π₁, ..., π_A)) is a real symmetric matrix, ensuring strictly real eigenvalues and real orthogonal eigenvectors for stable numerical diagonalization of nucleotide (GTR) and empirical amino-acid substitution matrices.

In computational biology, Markov chains operate across three primary modeling scales:

1. Phylogenetic Substitution Models: In the 4 × 4 General Time-Reversible (GTR) DNA model and 61 × 61 Goldman-Yang codon substitution models, Q is parameterized as q_ij = s_ij π_j so that detailed balance holds by construction and branch lengths are normalized to −∑_i π_i q_ii = 1 expected substitution per unit t.
2. Markov Chain Monte Carlo (MCMC): The Metropolis-Hastings acceptance ratio in Bayesian inference explicitly enforces detailed balance π(ψ) P(ψ → ψ′) = π(ψ′) P(ψ′ → ψ) with respect to the posterior distribution π(ψ) = p(ψ | D).
3. Hidden Markov Models (HMMs): When the underlying Markov chain {Z_n} (representing hidden structural states such as Match, Insertion, Deletion in profile sequence alignment, or Exon, Intron, Intergenic in gene prediction) is unobserved and emits observed sequence tokens X_n with emission probabilities e_k(x), the Forward-Backward and Viterbi dynamic-programming algorithms infer state paths in O(L · A²) time.

What is the difference between global balance and detailed balance in a Markov chain?

Global balance (πP = π) requires that the net probability flow entering any state i from the entire state space equals the total flow leaving state i, which allows net cyclic probability currents (such as 1 → 2 → 3 → 1). Detailed balance (π_i P_ij = π_j P_ji) requires that the flow from i to j equals the reverse flow from j to i for every individual pair, eliminating net probability cycles and making a movie of the stationary chain indistinguishable when played forward or backward in time.

How does the second-largest eigenvalue modulus |λ₂| control Markov chain mixing time?

When an ergodic transition matrix P is decomposed spectrally, the n-step deviation from stationarity scales as |P_ij⁽ⁿ⁾ − π_j| ≤ C |λ₂|ⁿ = C exp(−n ln(1/|λ₂|)), where |λ₂| < 1 is the second-largest eigenvalue modulus. The quantity γ = 1 − |λ₂| is the spectral gap; a small spectral gap (|λ₂| close to 1) indicates a bottleneck between weakly connected regions of state space and causes slow mixing in MCMC simulations.

Why are phylogenetic rate matrices Q normalized so that −∑_i π_i q_ii = 1?

In a continuous-time Markov substitution model P(t) = exp(Qt), only the product Qt is identifiable from sequence comparisons; scaling Q by a constant c and dividing branch length t by c leaves P(t) unchanged. Normalizing the generator matrix so that the stationary average rate of leaving the current state equals unity (−∑_i=1^A π_i q_ii = 1) fixes the units of branch length t to be the expected number of substitutions per site.

1. Markov, A. A. (1906). "Extension of the law of large numbers to dependent quantities." Izvestiya Fiziko-Matematicheskogo Obshchestva pri Kazanskom Universitete, Series 2, 15, 135–156. https://doi.org/10.1007/978-1-4612-4240-6_3
2. Rabiner, L. R. (1989). "A tutorial on hidden Markov models and selected applications in speech recognition." Proceedings of the IEEE, 77(2), 257–286. https://doi.org/10.1109/5.18626
3. Norris, J. R. (1997). Markov Chains. Cambridge University Press. https://doi.org/10.1017/CBO9780511810633
4. Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press. https://doi.org/10.1017/CBO9780511790492