Project: PageRank Algorithm · Stationary Distributions

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Problem. Test your intuition. Which of the following statements about stationary distributions are true?

5 points

  1. A stationary distribution exists for any graph.

  2. A stationary distribution exists for any graph without sinks.

  3. The stationary distribution is unique for any graph.

  4. Any initial distribution converges to the stationary distribution under a random walk, namely there exists a unique stationary distribution \(\mathbf{r}\) such that \(\mathbf{T}\mathbf{r}= \mathbf{r}\), and for any initial distribution vector \(\mathbf{r}\), the sequence of distributions \(\mathbf{T}^{k} \mathbf{r}\) converges to \(\mathbf{r}\) as \(k\) tends to infinity.

  5. Source nodes always have weight \(0\) in the stationary distribution.