How to prove following random walk's stationary distribution in directed graph proportional to out-links' number

Question

For example, given a directed graph as following:

The adjacency matrix is

A = 
[[0, 1, 1, 1],
 [1, 0, 1, 0],
 [0, 1, 0, 1],
 [1, 0, 0, 0]]

There is a random walk:

Step1: go along out-link from node 0 with equal probability, e.g. node 1 with 1/3, 2 with 1/3, 3 with 1/3.

Step2: go along in-link with equal probability, e.g. in node 3, go to 0 with probability 1/2 and 2 with probability 1/2.

Then iteratively use these two steps.

Prove that if the Markov chains are finite, irreducible and aperiodic (hence have a unique stationary distribution), then final distribution is proportional to the number of out-links of this node.

In this example,

# U is A with every row normalized
U = 
[[0, 1/3, 1/3, 1/3],
 [1/2, 0, 1/2, 0],
 [1/2, 1/2, 0, 0],
 [1/2, 0, 1/2, 0]]

# V is A.T with every row normalized
V = 
[[0,   1/2, 0,   1/2],
 [1/2, 0,   1/2, 0],
 [1/2, 1/2, 0,   0],
 [1/2, 0,   1/2, 0]]

W = MatrixPower[U.V, 100] = 
[[0.375, 0.25, 0.25, 0.125],
 [0.375, 0.25, 0.25, 0.125],
 [0.375, 0.25, 0.25, 0.125],
 [0.375, 0.25, 0.25, 0.125]]

As we can see, stationary distribution is [0.375, 0.25, 0.25, 0.125] proportional to outlinks' number in each node, i.e. [3, 2, 2, 1].

Answer 1

Hint: prove the following claims, in order, assuming you start by sampling a node with probability proportional to the number of out-links.

1. At the beginning of step 1, we are equally likely to be traveling along any link.
2. At the end of step 1, we arrive at a node with probability proportional to the number of in-links it has.
3. At the beginning of step 2, we are equally likely to be traveling backwards along any link.
4. At the end of step 2, we arrive at a node with probability proportional to the number of out-links it has.

This proves that the distribution we start and end with is stationary.

We can make this more concrete: the constant of proportionality in all cases is $\frac1m$, where $m$ is the total number of links. So in the distribution we're talking about, a node $v$ has probability $\frac{\deg^+(v)}{m}$, where $\deg^+(v)$ is the number of out-links $v$ has. At the end of step 1, we arrive at a node $w$ with probability $\frac{\deg^-(w)}{m}$, where $\deg^-(w)$ is the number of in-links $w$ has. Whenever we travel along links, each link has probability $\frac1m$.