Tree shaped Markov Chain stationary distribution

101 Views Asked by At

I am working with a tree shaped DT Markov Chain transition matrix. I mean that there is no cycle in the associated graph and as in a tree you can only go down further the graph as time passes. I looked around and, from the definitions I found here: it seems to be that this kind of transition matrix is reducible.

Therefore, there are several solutions to the stationary distribution of said matrix. I found a way to compute the stationnary distribution in python but I get some negative values in the answer array.

Here is how this is done but maybe I messed up the maths:

def solveStationary( A ):
    """ x = xA where x is the answer
    x - xA = 0
    x( I - A ) = 0 and sum(x) = 1
    """
    n = A.shape[0]
    a = np.eye( n ) - A
    a = np.vstack( (a.T, np.ones( n )) )
    b = np.matrix( [0] * n + [ 1 ] ).T
    return numpy.linalg.lstsq( a, b )[0]

Unfortunately, I cannot produce a sample matrix as my minimal examples are already $100\times 100$ish matrixes.

Therefore, I have two questions: What can I do with the "Tree Matrix" to reduce it ? Can I affect the stationary vector with negative values so I can make said values positive ?

Thank you in advance !