Stationary Distribution of a Markov Chain

Find the stationary distribution of a Markov chain.

A Markov chain moves between n states. P[i, j] is the probability of moving from state i to state j in one step, so each row of P sums to 1. If you run the chain for a long time, the fraction of time it spends in each state settles to a fixed vector pi. That vector does not change after one more step:

pi @ P = pi,    sum(pi) = 1,    pi >= 0

So pi is a left eigenvector of P with eigenvalue 1, which is an ordinary eigenvector of P.T. PageRank and MCMC samplers both rest on this idea.

Function signature

def stationary_distribution(P):

Example

Input

P = np.array([[0.9, 0.1],
              [0.5, 0.5]])
stationary_distribution(P)

Output

array([0.83333333, 0.16666667])

Reasoning

In the long run, the flow out of state 0 must equal the flow into it: 0.1 * pi_0 = 0.5 * pi_1. Together with pi_0 + pi_1 = 1, this gives pi_0 = 5/6 and pi_1 = 1/6.

Constraints and notes

• The chain is irreducible and aperiodic, so pi is unique.
• An eigenvector solver can return the vector with a negative sign or with a small imaginary part. Take the real part and scale it to sum to 1.