How to calculate the state vector after n-transitions?

[Adel Makram]

Homework Statement

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?

Homework Equations

Assuming the initial state vector is a column vector x₀, in literature it is considered as a row vector x₀^T. 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$$

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 Σⁿ is a diagonal matrix. Also I know that Uⁿ=I. But, I do not know the behavior of (V^T)ⁿ.

 

[Ray Vickson]

Homework Statement

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?

Homework Equations

Assuming the initial state vector is a column vector x₀, in literature it is considered as a row vector x₀^T. 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$$

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 Σⁿ is a diagonal matrix. Also I know that Uⁿ=I. But, I do not know the behavior of (V^T)ⁿ.

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$.

 

[Adel Makram]

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$.

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.

 

[Ray Vickson]

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.

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$.

 

[Adel Makram]

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$.

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

 

[Ray Vickson]

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

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.