Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Markov chain question

  1. Jun 4, 2013 #1
    This is slightly applied stuff. Please look at the PDF attached.

    How do we express the function f(n)ij, found at the bottom of page 4, in closed form, in terms of the values of n, i and j? If we can figure this out, then, as noted half-way down page 5, fij is simply the sum of f(n)ij from n=1 to n=∞. And then, at the bottom of page 5, we perform a summation across all values of j. i=A*D apparently, or perhaps I am interpreting that wrong; it seems strange that a transition probability will be the same for the 4v5 case as for the 10v2 case.
     

    Attached Files:

  2. jcsd
  3. Jun 4, 2013 #2

    chiro

    User Avatar
    Science Advisor

    Hey Big-Daddy.

    You might want to try using the spectral decomposition of a new transition matrix that factors out the possibility of getting j for k = 1 to n and use that. Your initial vector will of course have a 1 in the ith position of the vector and 0's everywhere else.

    With spectral decomposition you can get a closed form solution in terms of n (the number of multiplications) and it should be good if you adjust your transition matrix to not go into state j for k = 1 to n.
     
  4. Jun 5, 2013 #3
    Thanks for the response.

    Could you demonstrate for one out of the two functions? I'm still unsure as to how to do this.
     
  5. Jun 5, 2013 #4

    chiro

    User Avatar
    Science Advisor

    I'm not sure what you mean about one of the two functions. The spectral decomposition is just writing a matrix in terms of its eigenvalues (on the diagonal matrix) and eigenvectors if it actually exists.

    The transition matrix is just a new matrix that forces a state of X_k != j for all k = 1 to n which means that the probability transition matrix will have 0's for all transitions to state j for appropriate k. In this scenario you need to re-normalize the other probabilities so they add up to 1.

    To get a closed form solution of multiplying a matrix n times, you use the spectral decomposition and A^n = P*D^n*P^(-1) for diagonal matrix D and appropriate matrices P and P inverse.

    Exponentiating a diagonal matrix is easy: just exponentiate all diagonal elements individually (if its a diagonal matrix).
     
  6. Jun 6, 2013 #5
    Thanks. Evidently I don't have enough experience of much of matrices to do this myself. Could you either suggest some links where I can learn the techniques you speak of (spectral decomposition, re-normalizing the probabilities to add up to 1 from the matrix, and exponentiating) or simply show an example method for the case in the PDF?
     
  7. Jun 6, 2013 #6

    chiro

    User Avatar
    Science Advisor

    Do you know how to calculate eigen-vectors and eigen-values? If you do then you can do spectral decomposition.

    If you don't you need to pick up a linear algebra textbook and you can search this website for recommendations or wait for a recommendation by another member.

    If you know how to get eigen-vectors and eigen-values just follow the construction given in Wikipedia:

    http://en.wikipedia.org/wiki/Matrix_decomposition#Eigendecomposition
     
  8. Jun 7, 2013 #7
    Thank you, I see what has to be done now.

    But before I can find the eigenvectors or eigenvalues for the matrix, I will need to be able to draw out the correct matrix and numerically fill it in (or algebraically, perhaps, if we want a function of n, i, j and the pi constants). How do I do that, for the specific case in the PDF?

    I will then proceed to find the eigenvectors and eigenvalues for the matrix you suggest and then attempt to eigendecompose it. This would yield a closed-form solution for fnij in terms of n, i, j and the pi constants which represent transition probabilities.
     
    Last edited: Jun 7, 2013
  9. Jun 7, 2013 #8

    chiro

    User Avatar
    Science Advisor

    If you can't go to state j, then the probability of p_ij will be zero for all values of i. If this is the case you need to re-normalize the other probabilities and eliminate this row.

    As an example re-normalizaton if I have four events at 0.25 0.25 0.25 0.25 and I remove one, the new probabilities will be 1/3 1/3 1/3 or 0.25/(0.25+0.25+0.25) for all three events.

    You will then have to construct a final matrix that allows you to go to state j and then merge this transformation with the previous one (through matrix multiplication) to get the final closed form solution.
     
  10. Jun 11, 2013 #9
    Thanks, but it doesn't seem to me that simply brainstorming states is the most efficient way of writing the matrix. Then if we try and cover a general system (D,A), we get something which starts a bit like in the PDF attached (to this post). I outline the beginning of a possible transition matrix in the PDF, but it seems to me that it cannot be an efficient method, partly because it is long and not all of the cells can be specified, and partly because even the transition probabilities can take different values depending on the initial values of D and A.

    Now you have seen some of my effort, can you suggest a more streamlined matrix I could take to then eigendecompose?
     

    Attached Files:

    Last edited: Jun 11, 2013
  11. Jun 11, 2013 #10

    chiro

    User Avatar
    Science Advisor

    I have no idea what that PDF is trying to say.

    If you want to take my advice try constructing a matrix for n transitions (without j) and then a new transition with j and compose the two systems.

    Can you specify a matrix without the j state first? Once you do that you can perform the diagonal decomposition.
     
  12. Jun 12, 2013 #11
    What do you mean a matrix for n transitions without j? What does each symbol refer to here?
     
  13. Jun 12, 2013 #12

    chiro

    User Avatar
    Science Advisor

    Basically the transition matrix doesn't have state j and you have n transitions (the nth time step if you will)
     
  14. Jun 13, 2013 #13
    In order to undergo eigendecomposition, a specific matrix - with numerical values or known constants inside for each transition between each state - needs to be specified, no?

    By doesn't have state j, I don't know what you mean. What states does it have then? I don't know what j is, nor what n is. It is not specified earlier in the PDF as far as I can tell.
     
  15. Jun 14, 2013 #14

    chiro

    User Avatar
    Science Advisor

    You will need some kind of specifics. If you don't specify an initial transition matrix, then the whole thing will just be way too general to be useful.
     
  16. Jun 14, 2013 #15
    That's the transition matrix I was trying to write up in the PDF above (without filling in the individual transition probability values). But I realized we cannot in general have a (D,A) matrix written like that. So there must be a more efficient way of finding the initial transition matrix for this problem?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook