Random Walk Stationary Distribution

Problem

For a simple random walk on an undirected graph given by adjacency matrix A, return its stationary distribution.

It is proportional to the degree of each vertex: pi[i] = deg(i) / sum(deg). Return None if every degree is 0.

Hint

Detailed balance holds because each edge is traversed equally in both directions.

case 1

in: [[[0,1],[1,0]]]

expected: [0.5,0.5]

case 2

in: [[[0,1,1],[1,0,0],[1,0,0]]]

expected: [0.5,0.25,0.25]

case 3

in: [[[0,1,0],[1,0,1],[0,1,0]]]

expected: [0.25,0.5,0.25]

case 4

in: [[[0,0],[0,0]]]

expected: null

Starter codePython

def random_walk_stationary(A):
    # Your code here
    pass

4 test cases · run your code against them in the editor