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(λ1,λ2,λ3,...,λn). Then by eigendecomposition
Let the eigenvalues be enumerated such that 1=|λ1|>|λ2|≥|λ3|≥...≥|λ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 ui be the ith column of U matrix, i.e. ui 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 ui, that is
for some set of ai∈ℝ. 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 π = ui ← 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 π = u1, π(k) approaches to π as k goes to infinity with a speed in the order of λ2/λ1 exponentially. This follows because |λ2|≥|λ3|≥...≥|λn|, hence λ2/λ1 is the dominant term.
Read more about this topic: Markov Chain, Finite State Space
Famous quotes containing the words speed, stationary and/or distribution:
“It was undoubtedly the feeling of exile—that sensation of a void within which never left us, that irrational longing to hark back to the past or else to speed up the march of time, and those keen shafts of memory that stung like fire.”
—Albert Camus (1913–1960)
“It is the dissenter, the theorist, the aspirant, who is quitting this ancient domain to embark on seas of adventure, who engages our interest. Omitting then for the present all notice of the stationary class, we shall find that the movement party divides itself into two classes, the actors, and the students.”
—Ralph Waldo Emerson (1803–1882)
“The question for the country now is how to secure a more equal distribution of property among the people. There can be no republican institutions with vast masses of property permanently in a few hands, and large masses of voters without property.... Let no man get by inheritance, or by will, more than will produce at four per cent interest an income ... of fifteen thousand dollars] per year, or an estate of five hundred thousand dollars.”
—Rutherford Birchard Hayes (1822–1893)