5
$\begingroup$

I would like to find an algorithm for obtaining all ergodic components of a finite Markov chain with discrete time defined by its transition matrix (i.e. ergodic subchains into which the given chain is being decomposed).

Certainly, the task can easily be solved by calculation of adjacency matrix of the digraph corresponding to the chain and consequent calculation of reachability matrix of this digraph. But this way is computationally very cost. Maybe, does there exist more efficient algorithm?

$\endgroup$
  • $\begingroup$ Please clarify "ergodic component". Is the state space finite, time discrete? $\endgroup$ – Thomas Aug 25 '15 at 7:33
  • $\begingroup$ Clarified! The chain can contain states of any sort -- absorbing, transitional, ergodic. $\endgroup$ – Konstantin Aug 25 '15 at 7:50
  • 3
    $\begingroup$ I still don't understand the question: For irreducible Markov chains on a finite state space we have the ergodic theorem (this is basic stuff in any book on finite state space Markov chains). So the question is equivalent to computing the strong connected components which can be done in linear time: en.wikipedia.org/wiki/Strongly_connected_component ? $\endgroup$ – Thomas Aug 25 '15 at 8:08
  • $\begingroup$ Thomas, my question in fact is very simple (question, not answer). If Markov chain is irreducible, there is no problem, as you wrote. But the chain can be reducible. In such a case an ergodic decomposition is possible (see. e.g. en.wikipedia.org/wiki/Ergodicity). So in other words I need an algorithm for ergodic decomposition. $\endgroup$ – Konstantin Aug 25 '15 at 9:37
1
$\begingroup$

Let me give an answer in a different direction: Your problem is to find the terminal strongly connected components. The complexity of this problem is not bad for any sense of bad used in computer science, but I understand that you want the most efficient algorithm. Try to look into computer science literature, in particular search on graphs.

I'm not an expert on this kind of complexity theory, and the distinctions can be subtle, but I think you will have to live with something akin to linear in the size of the state space.

$\endgroup$
  • $\begingroup$ Absolutely exactly: terminal (absorbing) SCCs! Regards $\endgroup$ – Konstantin Aug 25 '15 at 11:52
0
$\begingroup$

This is an explanation of Thomas's comment, but too long for a comment:

Each strongly connected component of the transition graph that has no exit edges supports a unique stationary distribution which is ergodic. On the other hand, every stationary distribution is supported on the union of such strongly connected components (transient components have no stationary weight), and conditioning a stationary distribution on being in a single component again gives a stationary distribution. So, every stationary distribution can be written as a convex combination of the ergodic distributions supported at strongly connected components with no exit edges.

Therefore, you only need to find the strongly connected components, and for each component the unique stationary distribution supported at that component.

$\endgroup$
  • $\begingroup$ Thank you for comment, but all these facts are well-known. It is not sufficient to find all SCCs, because from a SCC can walk an arc (which goes, e.g., to a digraph sink, which in this case is an absorbing state). So one has to calculate all SCCs, which have no departures! I would like to find more elegant algorithm, if the later exists. $\endgroup$ – Konstantin Aug 25 '15 at 10:09
  • $\begingroup$ Thank you, I explained my motivation. If there is no something better, I'll work with SCCs. $\endgroup$ – Konstantin Aug 25 '15 at 10:26
  • $\begingroup$ Yes, you are right. You need the strongly connected components with no exit edges. My mistake. $\endgroup$ – Blackbird Aug 25 '15 at 10:31
  • $\begingroup$ Alternatively, you may find the extremal points of the convex polytope $\{x: xP=x, \sum_i x_i=1, x\geq 0\}$. $\endgroup$ – Blackbird Aug 25 '15 at 10:39
0
$\begingroup$

I am developing an algorithm to do this for the soft/fuzzy case, see https://arxiv.org/abs/1502.00727

It can work even when there are not multiple zero eigenvalues or spectral gaps. Let me know if you want to try it sometime!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.