[Python] Matrix convergence

[Zhengzheng Pan]

Hi all,

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...

Currently the standard theorem on convergence in Markov chain
literature is involved with the properties of aperiodic and
connectivity, which I'm not able to implement with Python either...
Therefore I'm actually also looking for alternative conditions to
check for convergence, and am willing to sacrifice a little bit of
precision.

If you have any ideas/suggestions on how to examine the convergence of
a matrix in general or specifically about this kind of matrices, and
are willing to share, that'd be really great.

Thx!

Zz

[Mark Dickinson]

On Sep 30, 3:10 pm, Zhengzheng Pan <[e-mail]:

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

[Robert Israel]

Zhengzheng Pan <pa***********@gmail.comwrites:

Hi all,

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...

Currently the standard theorem on convergence in Markov chain
literature is involved with the properties of aperiodic and
connectivity, which I'm not able to implement with Python either...
Therefore I'm actually also looking for alternative conditions to
check for convergence, and am willing to sacrifice a little bit of
precision.

If you have any ideas/suggestions on how to examine the convergence of
a matrix in general or specifically about this kind of matrices, and
are willing to share, that'd be really great.

Do you mean you have an n x n stochastic matrix T and you're trying to find
out whether the sequence T^j converges?

Let A = (I + T)^(n-1) and B = T^((n-1)^2+1). Powers of matrices are easy
to compute using repeated squaring.

i and j are in the same class iff A_{ij} 0 and A_{ji} 0. A class
containing state i is recurrent iff A_{ij} = 0 for all j not in the class.

A recurrent class containing state i is aperiodic iff
B_{ij} 0 for all j in the class.

T^j converges iff all recurrent classes are aperiodic. Thus the test
can be written as follows:
For each i, either there is some j for which A_{ij} 0 but A_{ji} = 0,
or there is no j for which A_{ij} 0 but B_{ij} = 0.
--
Robert Israel is****@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada