1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to calculate the state vector after n-transitions?

  1. Dec 12, 2015 #1
    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. jcsd
  3. Dec 12, 2015 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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##.
     
  4. Dec 12, 2015 #3
    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.
     
  5. Dec 12, 2015 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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##.
     
  6. Dec 13, 2015 #5
    The entries in column sums to 1.
    The matrix is 5x5 for example.
     
  7. Dec 13, 2015 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to calculate the state vector after n-transitions?
  1. State Vectors (Replies: 0)

Loading...