I think alpha is the stationary state distribution of Markov matrix P after n steps. You can just keep increasing n to get the stationary distribution.

Qamar Abbas Thank you so much for pointing out to the stationary state distribution. I referred to a few videos online as well. It helped! I was unaware of this concept.

Hi Mritunjay,

One of the properties of Markov chains, is that if approximated properly the state transition matrix becomes stationary. i.e. In the limit, the State Transition Probability Matrix (P) tends to a stationary matrix (A) which does not change as a function of time. This A is essentially the "GLOBAL State Transition Matrix" while P is a "LOCAL" version of the same.

This can be explained as, for a starting probability vector of states (Pi_0), you get the subsequent probability vector as; Pi_1 = Pi_0*P,. Similarly, Pi_2 = Pi_0*P*P, and Pi_n = Pi_0*P^n.= Pi_0*A = Alpha.

Now for any subsequent state, Pi_(n+1) = Pi_0*P^n*P. We have, the last 2 terms (=P^n*P=P^(n+1)) = A as that is the limit. This Pi_(n+1) = Pi_0*A = Pi_n in the limit.

Explaining equation 3.2, Alpha*P = Pi_0*P^n*P = Pi_0*P^(n+1) = Pi_0*A = Alpha.

Mathematically, in the example shown, the values of a_1,....,a_n are computed analytically. In a true situation, this is not done. Instead, taking sufficient data (length) when modelling P ensures a sort-off statistical stationarity, i.e. the P is actually A (with very small variations).

Hopefully this helps, and you can follow the subsequent discussion.

You can read my paper, " Online Discovery and Classification of Operational Regimes from an Ensemble of Time Series Data" which has a description on how Markov modelling is actually used for real data.

Cheers

@Thank you Chandrachur Bhattacharya, for such a beautiful explanation. It helped! I have another query related to computing the Alpha. For example, in the images given, I computed the Alpha scores for Eq. 4.4 through R and my results vary a bit with respect to equation 4.6 (alpha scores presented by the researchers in the paper). Is it ok or am I doing something wrong here?

That's how I calculated the basic algebraic multiplication in excel following these steps and the code:- https://stephens999.github.io/fiveMinuteStats/stationary_distribution.html

Thanks

Hi Mritunjay,

The way this formulation is, the diagonal elements need to be of a certain sign and the off diagonals are of the opposite sign. The Github site makes the diagonal elements negative (in fact there is an error in the A*Pi = b eqn), while you make them positive. That is fine. But the constraints remain that the non-diagonals need to be of opposite signs and the row sum of the final 'A' matrix should be 0 (before transposing and augmenting).

In Step 2 of you attached Excel screenshot, you have that. All diagonal elements are -ve and off diagonal are positive with row sum = 0 (before transposing and augmenting). In Step 3 there is an error Row2, Col1 should read -0.2, not 0.2. That is throwing you off. Recalculating after correcting that should make it fine.

Also, as I am sure you have figured out, an easy way to arrive at the Matrix in Step 2 is just subtract a Identity Matrix of same dimensions from the original State Transition Matrix.

FYI, for a State Transition Matrix, the row sum must be 1 (It is a sum of probabilities of going to that next state, the sum of which must be 1). The example you sent doesn't row sum to 1 for Rows 4, 7 & 8, so it is technically not a correct STM, but either way correcting that -ve sign will work.

Cheers

Chandrachur Bhattacharya I am really thankful to you for taking your time and responding to my queries proactively. I agree that the STM in eq 4.4 itself does not sum up to 1 (4, 7 & 8). But yes, I got the point. Thank you once again, brother.... the world needs people like you......:) :) _/\_

Mritunjay Kumar, most welcome, it was no problem at all! Good luck with your work!

I think the previous answers gave you what you needed but I would just like to elaborate a little bit on this topic which I believe helps in the computation of alpha.

Since the probabilities encoded in the Markov chain matrix P represent the probabilities that you transition from one state to any other, one can think of the vector alpha as the "average time" a random walker in the chain would spend in each state. This offers a different interpretation as the ones given before.

Given that matrix P has all columns (or rows depending on whether we set the vector alpha as a column or row vector) sum to one. Given the Perron Frobenius theorem, we can calculate alpha in the following (equivalent) ways:

1) we raise P to a very large number (say 1000) and multiply by any vector

2) we compute the eigenvalues and eigenvectors. Given the theorem, all of them will have modulus smaller than one except for a single eigenvalue equal to one. The left and right eigenvectors associated with this eigenvalue will be alpha and the vector of ones.

A last remark is that since we are taking the powers of P and all the eigenvalues have magnitude smaller than one, the projections of x0 on this coordinates will vanish at a speed dependent on the eigenvalues raised to the power of t. Thus, the rate of convergence of a Markov chain to its steady state distribution is given by the largest module eigenvalue that is smaller than one.

Daniel Silvestre Thank you for pointing out some crucial dimensions required to understand the Markov's Chains in depth. After your post, I read about computing the eigenvalues and eigenvectors. It is really interesting to witness different aspects of Markov's chains and their properties. For now, I just need to calculate the alpha and report my inferences for my research. Thank you once again.