Steady-state analysis

We seek to understand the asymptotic behavior of a homogeneous Markov chain. That is the limit of the transition probabilities Qn(i,j) when n becomes very large.

Why ?

We seek to answer the question « What is the probability that after n steps, the Markov chain is in a given state? « . Consider the following transition matrix P:

proba9.png

Suppose that none of the machines are down on the first day. Then we have as initial vector (1, 0), to calculate the following distribution we multiply the initial vector by P, etc. Which gives the following results:

proba10

This means that after 10 iterations, if we consider that we start from state 0, we have 99% to be in state 0 and 1% in state 1. This can also be interpreted in the way following: on a starting population, considering the initial distribution by the vector (1,0), then 99% of the population will be in state 0 and 1% in state 1.

We notice that the fourth and tenth iterations have similar results (here identical to 4 significant digits). This is called convergence law, and this law does not depend on the original distribution.

 

Periodicity

Take the example of the following matrix P = {0, 1; 1, 0}. We find that P² = Id which implies the following relation: ∀n∈Ν, P2n+1=P.

Such a chain does not converge, it is said to be 2-periodic or of period 2.

A chain is called k-periodic iff: ∀ (n, k) ∈Ν², Pkn+1=P. The states of a class all have the same period.
A state x is called aperiodic if Pn(x,x)>0. If P is irreducible and has at least one aperiodic state, then all states are aperiodic.

Before calculating the invariant law of a Markov chain, it must be verified that the latter is irreducible and aperiodic (also called ergodic).

A chain is ergodic if any state is attainable from any other state and for a power Pk all elements are strictly positive. It is therefore possible to go from one state to another in at most k stages, regardless of the starting and finishing points. An ergodic chain has an invariant law (be careful, it is also possible to calculate the stationary distribution of the other chains, the interpretation is then not the same).

 

Invariant law

One says that a measure of probability π is invariant or stationary if for a transition matrix P we have πP = π. Note that since π is a measure then the sum of these terms is equal to 1.

Let (Xn) define a Markov chain homogeneous with P an irreducible and aperiodic transition matrix with an invariant measure π. So :

  • P(Xn = x) → π(x) when n → ∞ for each x
  • pn(x, y) → π(y) when n → ∞ for each x, y

The speed of convergence towards the stationary law is of the order of |ζ|n where ζ is the eigenvalue of P different from 1 and greater modulus (which is strictly smaller than 1).

If the chain is ergodic (irreducible and aperiodic) then all states are attainable from any other state. Such a chain has an invariant law.

How to calculate it ?

Take the definition μP = μ knowing that μ is stochastic (and yes I changed the name of the initial distribution!). This gives the following linear system:

A measure μ on E is invariant (for P) if μ = μP, that is: for all y ∈ Emarkov1

 

Given the relation µn+1 = µnP, we see immediately that, if μ is an invariant law and X0 ∼ µ, then Xn ∼ µ for all n. We also note that μ does not depend on the initial distribution.

For example, consider a three-state Markov chain whose transition matrix is as follows:

proba11

We notice at once that the matrix forms an irreducible and aperiodic chain, since all the states communicate and that pii >0. We seek to solve the system μP = μ with for solution µ*= (p, q, r) such that p + q + r = 1 and 0 <p, q, r <1 which gives the following equations:

proba12

The solution is µ*=(2/53, 10/53, 41/53).

 

Non ergodic cases

Consider the following Markov chain:

proba13

We find that state 1 forms a transient class, state 2 forms an absorbing class, and states 3, 4 form a recursive class. Let’s analyze the asymptotic behavior by not taking into account its non-ergotic nature (no guarantee of convergence).

proba14

The system does not admit a single solution. Let α be between 0 and 1, then we find a solution by admitting that α is a solution of π2:

proba15

We notice in the class {3,4} that the probabilities are equal on a frequency of 2k, we deduce that the class as a periodic behavior over a period of 2 (that we could have calculated by power of the matrix). The class {2} is absorbing, there is no period. The class {1} is transient, so there is no population after a time k.

In the case of a non-periodic chain, it is possible to deduce from the asymptotic behavior the classes of the states as well as the periodicity of the classes and the chain.

 

Publicités