Markov Process: How to Tell Reversibility & Eigenvalues=1

[Mentz114]

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.

 

[member 587159]

Please define reversible Markov process.

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

 

[Mentz114]

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.

 

[member 587159]

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]

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?

I found what I needed here. It is the same as detailed balance and I do know how to calculate if that is maintained.

https://www.math.ucdavis.edu/~gravner/MAT135B/materials/ch16.pdf
Thanks.

 

[StoneTemplePython]

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]

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]

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
[]

Excellent book. 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.
The e-vectors are concentrated at the end states giving two possible irreversible eqilibrium states. Or is that inference wrong ?

 

[StoneTemplePython]

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:

http://www.randomservices.org/random/markov/Discrete.html

 

[Mentz114]

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:

http://www.randomservices.org/random/markov/Discrete.html

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]

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]

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]

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.