On Sep 30, 3:10 pm, Zhengzheng Pan <panzhengzh...@gmail.comwrote:

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