Chapter 8 The Eigenvalue Problem: Exercises - Linear Algebra with Python

Markov Chains and PageRank¶

Eigenvalue theory is not merely an abstract mathematical tool; it is a core engine of modern computation and network science. Through two classic applications—weather prediction and web page ranking—we show how eigenvalues describe the long-term behavior of random systems.

A Markov chain describes random transitions between states: the state of the system at the next moment depends only on the current state and not on any earlier history. (In machine learning we often find that the current state is indeed the most important factor influencing the next moment.) This “memorylessness” allows the whole dynamic process to be described completely by a transition matrix $\mathbf{P}$ , where $P_{ij}$ is the probability of moving from state $i$ to state $j$ ; hence the entries of each row sum to 1.

The most important eigenvalue property of a transition matrix is that $\mathbf{P}$ always has the eigenvalue $\lambda = 1$ ; the corresponding eigenvector is called the stationary distribution $\boldsymbol{\pi}$ and satisfies

\mathbf{P}^\top \boldsymbol{\pi} = \boldsymbol{\pi}, \qquad \sum_i \pi_i = 1

(1)

Under suitable conditions of irreducibility and aperiodicity, no matter which initial state the system starts from, after a long enough time it converges to this unique stationary distribution. Intuitively, $\pi_i$ can be read as the average fraction of time the system spends visiting state $i$ in the long run.

The two exercises below explore two levels of this theory: the first builds intuition from a concrete weather model; the second follows the design of Google’s PageRank to make clear how the stationary distribution becomes the mathematical basis for measuring “importance.”

Three ways to read the stationary distribution

The stationary equation $\mathbf{P}^\top\boldsymbol{\pi} = \boldsymbol{\pi}$ has three complementary interpretations in different settings:

Probabilistic interpretation: consider a large number of independent individuals moving through the state space at the same time; $\pi_i$ is the fraction of individuals in state $i$ in the long run (weather prediction, queueing theory).
Single-walker interpretation: consider a single individual performing a random walk for a long time; $\pi_i$ is the long-run fraction of time it spends visiting state $i$ —if the same individual walks long enough, it naturally “samples” the whole stationary distribution.
Resource-allocation interpretation: $\pi_i$ is the fraction of resources that should be allocated to state $i$ at equilibrium (traffic in PageRank, inventory in a supply chain).

All three readings share the same convergence conclusion: as long as the transition matrix is irreducible and aperiodic (the system can get from any state to any state and does not cycle regularly), it converges to the unique $\boldsymbol{\pi}$ no matter which initial state or initial configuration it starts from. If the chain is reducible or periodic, there may be several stationary distributions or persistent oscillation, and convergence must be checked separately.

Exercise 1 (The Stationary Distribution of a Weather Model)

Consider a weather model with only “sunny” (state 0) and “rainy” (state 1), whose transition matrix is

\mathbf{P} = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}

(2)

where $P_{ij}$ is the probability of moving from state $i$ to state $j$ .

Verify that the entries of each row of $\mathbf{P}$ sum to 1, and explain the probabilistic meaning of this condition.
Explain why $\lambda = 1$ must be an eigenvalue of $\mathbf{P}$ . (Hint. Consider the relationship between the all-ones vector $\mathbf{1}$ and $\mathbf{P}$ .)
Find the stationary distribution $\boldsymbol{\pi}$ , that is, the probability vector satisfying

\mathbf{P}^\top \boldsymbol{\pi} = \boldsymbol{\pi}, \qquad \pi_0 + \pi_1 = 1

(3)

Exercise 2 (An Upper Bound on the Spectral Radius of a Stochastic Matrix)

Let $\mathbf{P}$ be an $n \times n$ row-stochastic matrix, that is, the entries of each row are nonnegative and sum to 1. Since a matrix and its transpose have the same eigenvalues, we prove the same conclusion along the following two paths, each starting from a different vector norm: every eigenvalue $\lambda$ of $\mathbf{P}$ satisfies $|\lambda| \leq 1$ .

Path 1: the $\ell^\infty$ norm (largest component)

Let $\mathbf{P}\mathbf{x} = \lambda\mathbf{x}$ with $\mathbf{x} \neq \mathbf{0}$ . Take the component $x_{i^*}$ of largest absolute value, so that $|x_{i^*}| = \|\mathbf{x}\|_\infty$ . Write out the expansion of $(\mathbf{P}\mathbf{x})_{i^*} = \lambda x_{i^*}$ and take absolute values.
Using the triangle inequality and the fact that each row sums to 1, prove that $|\lambda|\,\|\mathbf{x}\|_\infty \leq \|\mathbf{x}\|_\infty$ , and hence $|\lambda| \leq 1$ .

Path 2: the $\ell^1$ norm (sum of the absolute values of the components)

Let $\mathbf{P}^\top \mathbf{v} = \lambda\mathbf{v}$ with $\mathbf{v} \neq \mathbf{0}$ . Expand $\|\mathbf{P}^\top \mathbf{v}\|_1$ along the skeleton below, fill in the missing step, and complete the proof:

\|\mathbf{P}^\top \mathbf{v}\|_1 = \sum_{i} \left|\sum_{j} P_{ji}\, v_j\right| \leq \sum_{i}\sum_{j} P_{ji}\,|v_j| = \sum_{j} |v_j| \sum_{i} P_{ji} = \;?

(6)

From $\mathbf{P}^\top \mathbf{v} = \lambda\mathbf{v}$ and the inequality above, deduce that $|\lambda| \leq 1$ .

Summary

Path 1 corresponds to the $\ell^\infty$ operator norm, and Path 2 to the $\ell^1$ operator norm. Write out the definitions behind $\|\mathbf{P}\|_\infty \leq 1$ and $\|\mathbf{P}^\top\|_1 \leq 1$ , and explain why both inequalities hold naturally for a row-stochastic matrix. Which aspect of “conservation of probability” does each correspond to?
Explain why $\lambda = 1$ is actually attained, so that the upper bound is tight.
Let $\mathbf{P}$ be an irreducible, aperiodic row-stochastic matrix. Explain why the remaining eigenvalues $\lambda_1, \ldots, \lambda_{n-1}$ satisfy $|\lambda_i| < 1$ (strictly less), and give an intuitive argument.

Exercise 3 (The PageRank Algorithm)

The stationary distribution $\pi_i$ of the previous exercise is the long-run frequency with which the system visits state $i$ . The core insight of Google’s PageRank is this: if web pages are regarded as the states of a Markov chain and hyperlinks as transitions, then the stationary distribution reflects exactly the relative importance of the web pages—the more frequently a page is visited, the more important it is.

Consider a network of 4 web pages $\{0, 1, 2, 3\}$ with the following links:

page 0 links to $\{1, 2\}$
page 1 links to $\{0\}$
page 2 links to $\{0, 3\}$
page 3 links to $\{2\}$

Part 1: Building the transition matrix

Write down the link matrix $\mathbf{L}$ , where $L_{ij} = 1$ means that page $i$ has a link to page $j$ .
Divide each row of $\mathbf{L}$ by the number of outlinks of that page to obtain the transition matrix $\mathbf{P}$ , where $P_{ij}$ is the probability of jumping from page $i$ to page $j$ when all outlinks are equally likely.

Part 2: Computing PageRank

Solve the basic PageRank equation (without a damping factor):

\mathbf{P}^\top \mathbf{r} = \mathbf{r}, \qquad \sum_i r_i = 1

(15)

Introduce the damping factor $d = 0.85$ ; the PageRank equation becomes

\mathbf{r} = d\,\mathbf{P}^\top \mathbf{r} + \frac{1-d}{n}\mathbf{1}

(16)

Rewrite it as the linear system $(\mathbf{I} - d\,\mathbf{P}^\top)\mathbf{r} = \frac{1-d}{n}\mathbf{1}$ , solve it, and compare with the result of part 2.

Part 3: Power iteration

Starting from $\mathbf{r}^{(0)} = \frac{1}{4}\mathbf{1}$ , use the power iteration

\mathbf{r}^{(k+1)} = d\,\mathbf{P}^\top \mathbf{r}^{(k)} + \frac{1-d}{n}\mathbf{1}

(17)

to compute the first 3 steps, and observe the trend of convergence.

Based on your results, rank the four web pages by importance, and explain why page 0 ranks higher than page 3.

Solution to Exercise 3

0. The link matrix:

\mathbf{L} = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}

(18)

1. The numbers of outlinks of the rows are $2, 1, 2, 1$ , and the transition matrix is

\mathbf{P} = \begin{bmatrix} 0 & 1/2 & 1/2 & 0 \\ 1 & 0 & 0 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 1 & 0 \end{bmatrix}

(19)

2. Solving $(\mathbf{P}^\top - \mathbf{I})\mathbf{r} = \mathbf{0}$ together with the normalization condition gives

\mathbf{r} = \begin{bmatrix} 1/3 \\ 1/6 \\ 1/3 \\ 1/6 \end{bmatrix} \approx \begin{bmatrix} 0.333 \\ 0.167 \\ 0.333 \\ 0.167 \end{bmatrix}

(20)

Ranking: page $0 = 2 > 1 = 3$ (pages 0 and 2 tie, as do pages 1 and 3).

3. The system with the damping factor, $(\mathbf{I} - 0.85\,\mathbf{P}^\top)\mathbf{r} = 0.0375\,\mathbf{1}$ , has the solution

\mathbf{r} \approx \begin{bmatrix} 0.325 \\ 0.175 \\ 0.325 \\ 0.175 \end{bmatrix}

(21)

The damping factor makes the distribution more uniform, and the scores of low-ranked pages rise slightly.

4. Results of the power iteration:

\mathbf{r}^{(0)} = \begin{bmatrix}0.25\\0.25\\0.25\\0.25\end{bmatrix}, \quad \mathbf{r}^{(1)} \approx \begin{bmatrix}0.356\\0.144\\0.356\\0.144\end{bmatrix}, \quad \mathbf{r}^{(2)} \approx \begin{bmatrix}0.311\\0.189\\0.311\\0.189\end{bmatrix}, \quad \mathbf{r}^{(3)} \approx \begin{bmatrix}0.330\\0.170\\0.330\\0.170\end{bmatrix}

(22)

A clear trend of convergence is already visible.

5. Page 0 ranks higher than page 3 because importance is determined not by the number of outlinks but by the importance of the sources of the inlinks. Page 0 is pointed to by both page 1 and page 2, and page 2 itself ranks high; page 3 is pointed to only by page 2, and page 2’s other outlink points to page 0, which dilutes the importance passed on to page 3.

\underline{\text{PageRank is essentially the stationary distribution of a random walk: a recommendation from an important page is worth more.}}

(23)