[Python] Matrix convergence

[Robert Israel]

Zhengzheng Pan <panzhengzheng at gmail.com> writes:

> 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              israel at math.MyUniversitysInitials.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            Vancouver, BC, Canada