I Markov matrix query

  • Thread starter Mentz114
  • Start date

Mentz114

Gold Member
5,308
242
I refer to the transition matrix for a Markov process and I have two questions

1. How can one tell if a Markov process is reversible ?
2. Can it have two (or more) eigenvalues equal to 1 ?

My definition of the matrix is that it should have all rows(or columns) sum to 1.

Thanks.
 

Math_QED

Science Advisor
Homework Helper
1,052
338
Please define reversible Markov process.

For (2), the identity matrix says that the answer is yes.
 

Mentz114

Gold Member
5,308
242
Please define reversible Markov process.

For (2), the identity matrix says that the answer is yes.
I guess reversible here means there is a way into and out of every node. This eliminates the identity matrix.
 

Math_QED

Science Advisor
Homework Helper
1,052
338
I guess reversible here means there is a way into and out of every node. This eliminates the identity matrix.
You mean concretely that for every two states ##x,y##, we have ##x \to y?##

Also, why is the identity matrix a counterexample? You never said that (1) and (2) must hold at the same time?
 

Mentz114

Gold Member
5,308
242

StoneTemplePython

Science Advisor
Gold Member
1,026
494
A few things:

The standard reference on reversible chains is from Kelly, freely available here:
http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html

I'd suggest going through chapter 1 in particular.

Your question about multiplicity of eigenvalues = 1 really has nothing to do with time reversibility and everything to do with irreducibility. (Note the identity matrix is the most extreme form of reduciblity.)

To be clear you are talking about a time homogenous discrete time markov chain (or the underlying 'jump chain' for a markov process).

Consider the transition matrix

##\begin{bmatrix}
0 & 1&0&0\\
1 & 0 &0&0\\
0 & 0&0&1 \\
0 & 0&1&0\\
\end{bmatrix}##

This is time reversible and does satisfy the detailed balance conditions. The reason it has 2 eigenvalues = 1 is because it is reducible -- which is a graph idea (and in finite states its nicely developed in Peron Frobenius Theory).
 

Mentz114

Gold Member
5,308
242
A few things:

The standard reference on reversible chains is from Kelly, freely available here:
http://www.statslab.cam.ac.uk/~frank/BOOKS/kelly_book.html

I'd suggest going through chapter 1 in particular.

Your question about multiplicity of eigenvalues = 1 really has nothing to do with time reversibility and everything to do with irreducibility. (Note the identity matrix is the most extreme form of reduciblity.)

To be clear you are talking about a time homogenous discrete time markov chain (or the underlying 'jump chain' for a markov process).

Consider the transition matrix

##\begin{bmatrix}
0 & 1&0&0\\
1 & 0 &0&0\\
0 & 0&0&1 \\
0 & 0&1&0\\
\end{bmatrix}##

This is time reversible and does satisfy the detailed balance conditions. The reason it has 2 eigenvalues = 1 is because it is reducible -- which is a graph idea (and in finite states its nicely developed in Peron Frobenius Theory).
That is very helpful, thank you. I will look at irreducibility.
 

Mentz114

Gold Member
5,308
242

StoneTemplePython

Science Advisor
Gold Member
1,026
494
I'm not sure what being a tree has to do with it -- reducibility comes down to communicating classes.

what are e-vectors? Eigenvectors?

What are 'irreversible equilibrium states'? There's a lot of standard terminology that should be used here like transient states vs recurrent states, etc. If you don't have prior familiarity with markov chains, maybe this page can help:

 

Mentz114

Gold Member
5,308
242
I'm not sure what being a tree has to do with it -- reducibility comes down to communicating classes.

what are e-vectors? Eigenvectors?

What are 'irreversible equilibrium states'? There's a lot of standard terminology that should be used here like transient states vs recurrent states, etc. If you don't have prior familiarity with markov chains, maybe this page can help:

I'm familiar enough to understand the book you linked to.
I use the word 'equilibrium ' incorrectly from thermodynamics.

I understand a tree as a kind of graph. See lemma 1.5, page 9 of the book.
 

StoneTemplePython

Science Advisor
Gold Member
1,026
494
I understand a tree as a kind of graph. See lemma 1.5, page 9 of the book.
So I too know what a tree is... but what you wrote is

I have found that the process I'm studying is not a tree because it has a reflector at each end (edge?) and therefore reducible.
lemma 1.5 gives a sufficient condition for being reversible but it states this is no means necessary. So there isn't a converse here that you can call on for being "not a tree" for reversibility. Nor for that matter is there a converse for a non-tree and reducibility.

I'm scratching my head here.

This stuff gets complicated very quickly. Pinning down the vocabularly is vital.
 

Mentz114

Gold Member
5,308
242
Yes, it does. I'm misreading things now. Time to stop. Lemma 1.4 refers to the 'equilibrium equations' and those are just the detailed balance conditions.

Thanks for your help. I need to read some more to find out what reducibility is and why it is relevant. So I'll stop bothering you.
 

StoneTemplePython

Science Advisor
Gold Member
1,026
494
Yes, it does. I'm misreading things now. Time to stop. Lemma 1.4 refers to the 'equilibrium equations' and those are just the detailed balance conditions.

Thanks for your help. I need to read some more to find out what reducibility is and why it is relevant. So I'll stop bothering you.
For finite state chains, you can get the bulk of the results you want via Peron Frobenius Theory. The discussion in Meyer's Matrix Analysis is very hard to beat in this regard. The author used to make a watermarked copy freely available on the internet, though not anymore. Reading the wikipedia page on Peron Frobenius and following links in the Notes can pay dividends though....

The big idea is:
-- reversible chains have detailed balance equations so we can get closed form solutions that frequently would be too nasty when just dealing with global balance equations
-- as mentioned in kelly, the transition matrix for a time reversible chain is similar to a symmetric one (this has very nice spectral properties finite dimensions)
-- there's some other insights you can get by running a process backwards that are hard to come by (there's a criterion from Kolmogorov in chapter 1 of Kelly that helps interpret this)
-- an irreducible chain is the simplest form, if something is reducible, then it can be decomposed into simpler parts, and simple is good.
- - - - -
Once you've had time to digest, feel free to revert.
 

Want to reply to this thread?

"Markov matrix query" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top