Re: Re: Limiting powers of stochastic and zero-one matrices
- To: mathgroup at smc.vnet.net
- Subject: [mg38867] Re: [mg38835] Re: [mg38818] Limiting powers of stochastic and zero-one matrices
- From: Dr Bob <majort at cox-internet.com>
- Date: Thu, 16 Jan 2003 03:21:19 -0500 (EST)
- References: <200301141111.GAA26294@smc.vnet.net> <200301150720.CAA23434@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
If a Markov chain is aperiodic and all states communicate with each other
(a graph-theoretic property somewhat difficult to cast in matrix terms),
then the limiting transition matrix has all its rows equal to one another --
- the same steady-state probabilities are reached no matter what the
initial state is. In matrix terms, A^inf has all its rows equal to one
another, so it has rank one. Daniel's condition that all transition
probabilities are non-zero is the trivial case of this type, with a
saturated graph.
If the chain is periodic, the limit doesn't exist. If it's aperiodic but
has transient states, that will cause zeroes to appear down the
corresponding columns of the limiting probability matrix.
Kumar's original question was whether which elements of the limiting
steady-state are non-zero is fully determined by which elements of the
transition matrix are non-zero. Again, that's graph theory, and matrix
algebra isn't necessarily the best way to get there.
The answer is yes, when the limit exists, and I believe it's still yes (in
a way) when it doesn't.
It isn't easily proven from matrix algebra alone.
Bobby
On Wed, 15 Jan 2003 02:20:17 -0500 (EST), Daniel Lichtblau
<danl at wolfram.com> wrote:
> Kumar Chellapilla wrote:
>>
>> Hi,
>>
>> I am interested in determining where the zero and non-zero entries
>> occur in the powers of stochastic matrices in the limit as the power ->
>> infinity.
>>
>> If A = {a_ij} and B = {b_ij} are stochastic matrices
>> i.e., all non-negative (zero or positive) entries, rows sum to 1.0, max
>> eig
>> value = 1.0,
>> all other eigen values have abs(eigval) < 1, which gives us
>> A^\inf and B^\inf are both rank-1 matrices
>>
>> (where A^\inf = lim_{n -> \inf}{A^n})
>>
>> Let I(A) and I(B) be the indicator matrices ( (0,1) matrices) of A, and
>> B,
>> resp.
>> where I(A) = {I_ij}, with
>> I_ij = 1, if a_ij > 0 and
>> I_ij = 0, if a_ij = 0
>>
>> Now suppose I(A) = I(B),
>> which gives us I(A^n) = I(B^n),
>> Can we show that
>> I(A^inf) = I(B^inf) - Eqn (1)
>>
>> Note that Eqn (1) is NOT TRUE in general (for non-stochastic matrices):
>> E.g.
>> A = [0.1 0.1; 0.1 0.1]
>> B = [0.3 0.7; 0.3 0.7]
>>
>> I(A) = I(B) = [1 1; 1 1]
>>
>> A^inf = [0 0; 0 0]
>> B^inf = B
>>
>> I(A^inf) = [0 0; 0 0]
>> I(B^inf) = [1 1; 1 1]
>>
>> Thus I(A^inf) is not equal to I(B^inf)
>>
>> Thank you,
>> Kumar
>
> I don't have a general answer offhand but I'll note that your rank-1
> claim only holds generically. For (counter)example, if you take A to be
> the identity matrix of whatever dimension, it is stochastic and A^inf ==
> A has full rank. If you take, say, A = {{0,1},{1,0}} then A^inf does not
> even exist.
>
> For the (generic) regular case, i.e. all entries nonzero, you do have a
> rank 1 infinite power. It is given as the matrix whose rows are
> normalized null vectors of Transpose[(A - IdentityMatrix[Length[A]]];
> the null vector is unique up to scaling and so you scale to have row sum
> equal to one (since A^inf is stochastic).
>
> In this case it is easy to show that no value is zero. Say the first
> element in the null vector were zero. Then it's dot product with the
> first column of A-IdentityMatrix cannot be zero because that column only
> has a negative in the first element and all other elements are strictly
> positive. Same argument shows no element in the null vector is zero. To
> cast this in your terminology, if A is stochastic and I(A) consists
> entirely of 1's, then A^inf has rank equal to 1 and all nonzero
> elements.
>
> When the matrix A has zero elements it may be a different matter. I
> imagine this is well understood, but not by me.
>
>
> Daniel Lichtblau
> Wolfram Research
>
>
--
majort at cox-internet.com
Bobby R. Treat
- References:
- Limiting powers of stochastic and zero-one matrices
- From: "Kumar Chellapilla" <kumarc@microsoft.com>
- Re: Limiting powers of stochastic and zero-one matrices
- From: Daniel Lichtblau <danl@wolfram.com>
- Limiting powers of stochastic and zero-one matrices