Solving Markov Chain Question: Closed Form Expression for f(n)ij | PDF Attached

In summary: A^n = P*D^n*P^(-1).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#EigendecompositionThank you, I see what has to be done now.
  • #1
Big-Daddy
343
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.
 

Attachments

  • Markov Chains in Risk Revisited - Osborne, 2006.pdf
    162.7 KB · Views: 293
Physics news on Phys.org
  • #2
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.
 
  • #3
chiro said:
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.

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
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
chiro said:
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).

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
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
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:
  • #8
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
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?
 

Attachments

  • PhysicsForum-Post2,1,PDF.pdf
    184.3 KB · Views: 204
Last edited:
  • #10
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
What do you mean a matrix for n transitions without j? What does each symbol refer to here?
 
  • #12
Basically the transition matrix doesn't have state j and you have n transitions (the nth time step if you will)
 
  • #13
chiro said:
Basically the transition matrix doesn't have state j and you have n transitions (the nth time step if you will)

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
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
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?
 

1. What is a Markov chain?

A Markov chain is a mathematical model used to describe a sequence of events where the probability of each event depends only on the state of the previous event. It is a type of stochastic process, meaning that the outcome of each event is based on random chance.

2. How is a Markov chain used in science?

Markov chains are commonly used in various scientific fields such as biology, physics, economics, and computer science. They can be used to model processes that involve randomness or uncertainty, such as the movement of molecules in a chemical reaction or the fluctuations of stock prices.

3. What are some real-life applications of Markov chains?

Markov chains have many practical applications, including speech recognition, text prediction, weather forecasting, and DNA sequence analysis. They are also used in machine learning and artificial intelligence algorithms.

4. What are the limitations of Markov chains?

One limitation of Markov chains is that they assume that the future state only depends on the current state, not on any previous states. This may not always be true in real-world systems. Additionally, Markov chains can only model discrete events, not continuous ones.

5. How do you create a Markov chain model?

To create a Markov chain model, you need to define the states of the system, the probabilities of transitioning between states, and the initial state. This information can be obtained through observation or from experimental data. Once the model is created, it can be used to make predictions about future events based on the current state.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Electrical Engineering
Replies
15
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
Back
Top