[Solved]: Markov Chain w/ non-stochastic matrix

Problem Detail: 

I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum to 1. However,the probabilities on edges entering the node do sum to 1. Therefore the transpose of the transition matrix IS stochastic.

I've built up a model in excel and noticed a few properties of this "transpose markovian process":

1. all nodes reach the same steady state value.
2. the steady state *is* dependent on the initial state (unlike a markov process).
3. the steady state value can be computed as S₀ x M^T (the initial state vector times the transpose of the markovian steady state vector... obtained by transposing the transition matrix and solving as a markov process).

My question is this: Is there a name for such a process? In searching for it I've found it to be beyond obscure, so my hope is some well-informed human can catalyze me with some search terms.

Asked By : Andrew

Answered By : D.W.

No, there's no standard name for a process where the transpose of the transition matrix is stochastic (at least, to my knowledge).

However, this process is the time-reversal of a Markov process. That's a remarkable and descriptive property that just about completely characterizes this process. In particular, it seems likely that many things we'd want to know about such a process can be derived from the fact that it's the time-reversal of a Markov process, plus known facts about Markov processes.

Anyway, if you need to describe the process, "time-reversal of a Markov process process" is probably about as good as you're going to get.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40464

3.2K people like this

 Download Related Notes/Documents