Zhengzheng Pan <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED]
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
--
http://mail.python.org/mailman/listinfo/python-list
