Matrix convergence

[Mark Dickinson]

On Sep 30, 3:10 pm, Zhengzheng Pan <panzhengzh... at gmail.com> wrote:
> I'm trying to check whether a (stochastic/transition) matrix
> converges, i.e. a function/method that will return True if the input
> matrix sequence shows convergence and False otherwise. The background
> is a Markov progress, so the special thing about the transition matrix
> is the values of elements in each row add up to be 1. Fail to find any
> relevant build-in methods in Python...

I'm not sure exactly what you want here.  Do you have a single
transition matrix, or a `matrix sequence'?  Can I assume that you're
working with a time-homogeneous Markov chain with a finite state
space?  And that the function should take the transition matrix, and
should return True if and only if there's a unique limiting
distribution for the Markov process, independent of starting state?
Or have I misunderstood?

What's the typical number of states?  Thousands?  Millions?

Can you explain why you're unable to implement detection of
periodicity and connectivity (is this the same as irreducibility)?
Are there technical problems, or just conceptual problems?

Detecting irreducibility ought to be straightforward: form the
directed graph corresponding to the transition matrix (one vertex per
state, an edge from i to j iff the corresponding entry in the
transition matrix is nonzero) and apply Tarjan's algorithm (google
it!), which detects strongly connected components:  if there's a
single strongly connected component consisting of the entire graph
then the Markov process is irreducible.  Figuring out the period
shouldn't be too hard either---I have a feeling that it ought to be
possible to adapt Tarjan's algorithm to detect the period: label the
vertices of the graph by depth (Tarjan's algorithm is essentially a
depth-first traversal of the graph), and every time Tarjan's algorithm
detects a cycle, comparing depths will give you a multiple of the
period;  taking the gcd of all these multiples should give the period
itself.

An alternative, quick and dirty way (quick for the human, not the
computer!) would be just to compute some large power of the transition
matrix and eyeball it to see if all columns are identical.  If so, the
process converges.

> Thx!

Ur wlcm!

Mark