Random Walk on a Graph
Level 5●●●○○ Medium~6 min
Problem
A token performs a random walk on a connected undirected graph: at each step it moves to a uniformly random neighbour of its current vertex. What is the stationary distribution? Using it, what is the expected return time to a vertex of degree in a graph with edges?