Markov Chain - Finite State Space - Convergence Speed To The Stationary Distribution

Convergence Speed To The Stationary Distribution

As stated earlier, from the equation, (if exists) the stationary (or steady state) distribution π is a left eigenvector of row stochastic matrix P. Let U be the matrix of eigenvectors (each normalized to having an L2 norm equal to 1) where each column is a left eigenvector of P and let Σ be the diagonal matrix of left eigenvalues of P, i.e. Σ = diag(λ₁,λ₂,λ₃,...,λ_n). Then by eigendecomposition

Let the eigenvalues be enumerated such that 1=|λ₁|>|λ₂|≥|λ₃|≥...≥|λ_n|. Since P is a row stochastic matrix, its largest left eigenvalue is 1. If there is a unique stationary distribution, then the largest eigenvalue and the corresponding eigenvector is unique too (because there is no other π which solves the stationary distribution equation above). Let u_i be the ith column of U matrix, i.e. u_i is the left eigenvector of P corresponding to λ_i. Also let x be an arbitrary length n row vector in the span of the eigenvectors u_i, that is

for some set of a_i∈ℝ. If we start multiplying P with x from left and continue this operation with the results, in the end we get the stationary distribution π. In other words π = u_i ← xPPP...P = xPk as k goes to infinity. That means

since UU-1 = I the identity matrix and power of a diagonal matrix is also a diagonal matrix where each entry is taken to that power.

since the eigenvectors are orthonormal. Then

Since π = u₁, π(k) approaches to π as k goes to infinity with a speed in the order of λ₂/λ₁ exponentially. This follows because |λ₂|≥|λ₃|≥...≥|λ_n|, hence λ₂/λ₁ is the dominant term.