# Markov chain question

1. Jun 4, 2013

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.

File size:
162.7 KB
Views:
100
2. Jun 4, 2013

### chiro

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.

3. Jun 5, 2013

Thanks for the response.

Could you demonstrate for one out of the two functions? I'm still unsure as to how to do this.

4. Jun 5, 2013

### chiro

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

5. Jun 6, 2013

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?

6. Jun 6, 2013

### chiro

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

7. Jun 7, 2013

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
8. Jun 7, 2013

### chiro

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.

9. Jun 11, 2013

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:

• ###### PhysicsForum-Post2,1,PDF.pdf
File size:
184.3 KB
Views:
57
Last edited: Jun 11, 2013
10. Jun 11, 2013

### chiro

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.

11. Jun 12, 2013

What do you mean a matrix for n transitions without j? What does each symbol refer to here?

12. Jun 12, 2013

### chiro

Basically the transition matrix doesn't have state j and you have n transitions (the nth time step if you will)

13. Jun 13, 2013

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.

14. Jun 14, 2013

### chiro

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.

15. Jun 14, 2013