Lesson 6

• Uniqueness.  It is possible to construct a graph that admits multiple stationary distributions. For example, consider a graph consisting of two isolated self-loops.

  

  It is easy to see that any probability distribution over these two vertices is stationary.
  However, there is an important class of graphs for which the stationary distribution is unique. To describe them, decompose the graph into its strongly connected components (SCCs) and form the corresponding component graph, which is always a directed acyclic graph. If this component graph contains more than one sink component, then, as in the two-vertex example above, we can assign arbitrary weights to each sink component. In that case, the overall stationary distribution is any linear combination of the stationary distributions of each sink SCC summing to \(1\). (You may also notice that every vertex outside the sink SCCs must have weight \(0\) in any stationary distribution. Indeed, from any non-sink component there is a non-zero probability of leaving it, but once you leave, you can never return, therefore no stationary mass can accumulate there.) Graphs whose component graph has exactly one sink SCC are called irreducible. For such graphs, the stationary distribution exists and is unique.


• Convergence.  It is also not true that any initial distribution will necessarily converge to the stationary distribution.

  

  As a simple example, consider a bipartite graph. In such a graph, the probability mass alternates between the two partitions at each step, so the stationary distribution is never actually reached. The class of graphs in which such cyclic behavior does not occur is called aperiodic. Formally, a graph is aperiodic if, for every vertex, the greatest common divisor (GCD) of the lengths of all cycles containing that vertex is \(1\). (As in the previous discussion, vertices that lie outside the sink strongly connected components may not satisfy this condition. For such vertices, the stationary distribution still assigns a weight of \(0\).)

The Ergodic Theorem states that for any irreducible and aperiodic graph, there exists a unique stationary distribution, and any initial distribution will exponentially converge to it under a random walk.