Homework Help: How to calculate the state vector after n-transitions?

1. Dec 12, 2015

1. The problem statement, all variables and given/known data
Given an initial distribution state vector that represents the probability of the system to be in one of its states. Also given a Markov transition matrix. How to calculate the state vector of the system after n-transition?

2. Relevant equations
Assuming the initial state vector is a column vector x0, in literature it is considered as a row vector x0T. The state vector after the first transition will be: $$P x_0=x_1$$
where P is the Markov transitional matrix. After n-transitions, $$P^n x_0=x_n$$
3. The attempt at a solution
I tried to decompose P for an easier calculation using singular value decomposition, assuming that it is asymmetric matrix. $$P=UΣV^T$$.
$$P^n=(UΣV^T)^n=(U)^n (Σ)^n (V^T)^n$$.
I know that Σn is a diagonal matrix. Also I know that Un=I. But, I do not know the behavior of (VT)n.

Last edited: Dec 12, 2015
2. Dec 12, 2015

Ray Vickson

Which convention are you adopting for $P$? I have the strong impression that most modern treatments take $p_{ij} = P(X_{t+1}=j|X_t=i)$, so that the rows of $P$ sum to 1; every book I now own or have ever owned uses that convention. However, the alternative of having the columns summing to 1 is also used, but not as widely.

Anyway, if the rows of $P$ sum to 1 then $x_n = x_0 P^n$, with row-vectors $x_0, x_1, x_2, \ldots$. If, instead, the columns of $P$ sum to 1 and you still want row-vector $x_i$, then you have $x_n^T = P^n x_0^T$, where $\{\cdot\}^T$ = transpose.

If all you want are numerical results, it is straightforward: $x_1 = x_0 P$, $x_2 = x_1 P$, $\ldots$, $x_n = x_{n-1} P$. You can compute $x_1, x_2, \ldots$ sequentially, and you only need to keep track of $x_k$ in order to compute $x_{k+1}$. On the other hand, if you want an "analytical" expression for $x_n$, the easiest way is, perhaps, to obtain an analytical expression for $P^n$, then do a vector-matrix multiplication. Usually we need to use the eigenvalues (and sometimes the eigenvectors) of $P$ to complete the computations, and it can make a difference whether the eigenvalues are all distinct or not. I am reluctant to say more at this point, because it can become lengthy; but I can tell you more if you really want to know.

Note added in edit: I see that you seem to be adopting the convention that columns sum to 1, and where you write $x^T$ I write $x$.

3. Dec 12, 2015

In this post, I adopted the convention of column vector instead of row because it is more conventional for me.
Yes, I am looking for a closed analytic expression for $x_n$. This is important especially if n is larger.

4. Dec 12, 2015

Ray Vickson

You still have not really answered my question: do the rows of $P$ sum to 1, or do the columns sum to 1?

Also, how big can the matrix become (that is, what is the number of states)? If you have, for example, a $100 \times 100$ matrix $P$, you can probably forget about finding any reasonable analytical formula for $P^n$.

5. Dec 13, 2015

The entries in column sums to 1.
The matrix is 5x5 for example.

6. Dec 13, 2015

Ray Vickson

That is small enough to be practical (although the results may still be complicated). Many computer algebra systems can handle the problem automatically, but you can also do it manually if you know the eigenvalues. Do a Google search on "Matrix Functions" to see some methods.