2.11 Markov chains and PageRank

A random walker who moves by fixed probabilities is described by a matrix whose columns add to 1. Its long-run behaviour is an eigenvector with eigenvalue 1, and Google ranked the web by computing that eigenvector.

In Lecture 1, Spagnolie said that real systems can have “30 billion equations and 30 billion variables (Google PageRank!)” and asked “how can you even compute?!”. He called it “the $25 bil eigenvector”. This chapter shows what that eigenvector is. A person clicking links at random wanders over the web. The pages where they spend the most time are, plausibly, the important ones. The matrix that describes the wandering has an eigenvector with eigenvalue 1, and that eigenvector is the ranking.

Before you start

2.8: eigenvalues and eigenvectors, and diagonalization. 2.7: the determinant of a transpose. 2.5: matrix times vector and the transpose. In this chapter probabilities are numbers from $0$ to $1$ , and the only probability rule used is that the chances of all the possible outcomes add to $1$ .

Quick checkIf

Ax = 3x

for a non-zero vector

x

, what is

x

Quick checkA square matrix

A

and its transpose

A^{\mathsf T}

have...

Quick checkThe matrix with rows

(0, 1)

and

(1, 0)

multiplies the column vector

(3, 5)

. What is the result?

The picture

Four web pages, and arrows for the links between them. Page 1 links to pages 2, 3 and 4, page 2 links to pages 3 and 4, page 3 links only to page 1, and page 4 links to pages 1 and 3. A surfer starts on page 1 and, at every step, clicks one of the links on the current page, each link equally likely. The bars show the chance of finding the surfer on each page. Press Next. After one step the surfer is on page 2, 3 or 4 with chance $1/3$ each. After many steps the bars stop changing: that final set of heights is the ranking.

Two things to watch. The bars always add up to 1, because the surfer is always somewhere. And the heights settle down to the same values wherever the surfer starts. Both facts need a proof, and the proofs use eigenvalues.

The idea, in words

Number the pages $1, \dots, n$ . Let $P_{ij}$ be the chance that a surfer on page $j$ goes next to page $i$ . The convention is “column $j$ describes what happens from page $j$ ”. With the four pages above, column 1 is $(0, \tfrac13, \tfrac13, \tfrac13)$ because page 1 has three links, and column 3 is $(1, 0, 0, 0)$ because page 3 has one link, to page 1. So

P = \begin{bmatrix} 0 & 0 & 1 & \tfrac12 \\ \tfrac13 & 0 & 0 & 0 \\ \tfrac13 & \tfrac12 & 0 & \tfrac12 \\ \tfrac13 & \tfrac12 & 0 & 0 \end{bmatrix}.

Every column adds to 1, because from any page the surfer goes somewhere.

Let $x_k$ be the list of chances: $(x_k)_i$ is the chance the surfer is on page $i$ after $k$ steps. To land on page $i$ at the next step, the surfer must be on some page $j$ now and choose the link $j \to i$ . Add up over all $j$ :

(x_{k+1})_i = \sum_j P_{ij}\,(x_k)_j, \qquad\text{that is}\qquad x_{k+1} = P\,x_k .

So the whole story of the surfer is a matrix applied again and again. Chapter 2.8 showed what that means: write the starting vector in eigenvectors, and applying $P$ multiplies each part by its eigenvalue. The part with the biggest eigenvalue wins, and the others fade.

Why· Why an eigenvector with eigenvalue 1 is the ranking

If the surfer’s chances ever reach a vector $\pi$ that one more step does not change, then $P\pi = \pi$ . That is the equation of an eigenvector with eigenvalue $1$ . Pages with larger entries of $\pi$ are the ones where the surfer spends more time. A page gets a high entry when many pages send surfers to it, and more when the pages sending them have high entries themselves. That is the idea of PageRank: a link from an important page is worth more than a link from an obscure one.

Where this came from· Markov and Eugene Onegin

Andrey Markov introduced these chains around 1906 in an argument about probability. Pavel Nekrasov had claimed that averages settle down (the law of large numbers) only for independent events. Markov showed that sequences in which each step depends on the previous state also settle, and he proved it using transition chances like the ones in this chapter. In 1913 he tried the idea on literature: he took the first 20,000 letters of Pushkin’s poem Eugene Onegin, classified each as a vowel or a consonant, and studied how a vowel or consonant follows the one before. That is a two-state chain like our weather example, and its stationary distribution is the long-run share of vowels. The mathematics came first and the web came ninety years later.

The chapter answers five questions, in order. (1) Why does $Px$ stay a list of chances? (2) Why is $1$ always an eigenvalue? (3) Why is it the largest? (4) When do the bars settle on one answer, and how fast? (5) What goes wrong on the real web, and what did Google do about it?

Definitions and theorems

Definition B

Markov chain

A Markov chain has a list of states $1, \dots, n$ and fixed numbers $P_{ij} \ge 0$ , where $P_{ij}$ is the chance of moving to state $i$ from state $j$ in one step. The defining rule (the Markov property) is that this chance depends only on the current state, not on how the process got there. In the web example the states are pages and the surfer’s past clicks do not matter.

In one lineA process that moves among states, where the chance of the next state depends only on the current state and is given by fixed numbers $P_{ij}$ .

Why it existsIt is the simplest model of change over time with randomness, and it turns a probability question into a matrix question.

A warning on conventions. Probability courses (including MATH 431) usually put “from” on the row: $p_{ji}$ is the chance of moving from $j$ to $i$ , rows add to 1, and the chances are a row vector multiplied on the left. This book, Spagnolie and the PageRank papers put “from” on the column, so columns add to 1 and the chances are a column vector multiplied on the right. The two are transposes of each other. Nothing in the mathematics changes.

Definition B

Stochastic matrix

A list $x = (x_1, \dots, x_n)$ is a probability vector if every $x_i \ge 0$ and $x_1 + \dots + x_n = 1$ . A square matrix $P$ is stochastic (more precisely, column-stochastic) if every entry is non-negative and every column is a probability vector, that is, every column adds to 1. Write $\mathbf 1 = (1, 1, \dots, 1)$ . Then “every column adds to 1” is the single equation $\mathbf 1^{\mathsf T}P = \mathbf 1^{\mathsf T}$ , because entry $j$ of $\mathbf 1^{\mathsf T}P$ is the sum of column $j$ .

In one lineA square matrix with no negative entries in which every column adds to 1. Its columns are probability vectors.

Why it existsIt is exactly the shape of a matrix of transition chances, because from every state the process goes somewhere.

Worked example

A surfer on three pages: page 1 links to pages 2 and 3, page 2 links to page 3, and page 3 links to page 1. Write the matrix

P

, check it is stochastic, and find the surfer's chances after one and two steps if she starts on page 1.

Solution.

Write the columns from the links. Column $j$ lists where page $j$ sends the surfer, equally split among its links. Page 1 has two links: column 1 is $(0, \tfrac12, \tfrac12)$ . Page 2 has one link, to page 3: column 2 is $(0, 0, 1)$ . Page 3 has one link, to page 1: column 3 is $(1, 0, 0)$ . Each link out of page $j$ is equally likely, so with $\ell$ links each gets chance $1/\ell$ .
Assemble the matrix. $P = \begin{bmatrix} 0 & 0 & 1 \\ \tfrac12 & 0 & 0 \\ \tfrac12 & 1 & 0 \end{bmatrix}$ . Columns side by side.
Check it. All entries are at least $0$ and the columns add to $\tfrac12 + \tfrac12 = 1$ , $1$ and $1$ . That is the definition of stochastic.
One step. Start at $x_0 = (1, 0, 0)$ . Then $x_1 = Px_0 = (0, \tfrac12, \tfrac12)$ . $Px_0$ with $x_0 = e_1$ picks out column 1.
Two steps. $x_2 = Px_1 = \tfrac12\,(\text{column }2) + \tfrac12\,(\text{column }3) = (\tfrac12, 0, \tfrac12)$ . $Px = x_1 \cdot \text{column } 1 + x_2 \cdot \text{column } 2 + \dots$ , a combination of the columns with the entries of $x$ as weights.

Answer. After one step the surfer is on page 2 or page 3 with chance $\tfrac12$ each. After two steps she is on page 1 or page 3 with chance $\tfrac12$ each. Both lists add to $1$ .

Theorem B Strang 10.3; Bryan and Leise, section 3

A stochastic matrix keeps probability vectors

Let $P$ be stochastic and $x$ a probability vector. Then $Px$ is a probability vector. If $P$ and $Q$ are both stochastic $n \times n$ matrices, so is $PQ$ . In particular $P^k$ is stochastic for every $k$ , and $P^kx_0$ is a probability vector for every $k$ .

In one lineIf $P$ is stochastic and $x$ is a probability vector, then $Px$ is a probability vector. Also a product of stochastic matrices is stochastic.

Why it is trueProbability is never lost or created. It is moved around, and each column says how it moves.

ProofBryan and Leise section 3

The idea: Entries: sums of products of non-negative numbers. Total: swap the order of summation and use that each column adds to 1.

Every entry of

Px

is non-negative.

Entry

i

Px

\sum_j P_{ij}x_j

. Every

P_{ij} \ge 0

and every

x_j \ge 0

, so every term is at least

0

\displaystyle \sum_i (Px)_i = \sum_i \sum_j P_{ij}x_j

Add up all the entries of

Px

and write each as its sum over

j

\displaystyle = \sum_j x_j \Big( \sum_i P_{ij} \Big)

A finite double sum can be added in either order. We add over

i

first, because that is the sum of a column of

P

\displaystyle = \sum_j x_j \cdot 1 = 1

. So

Px

is a probability vector.

Each column adds to 1. Then the entries of

x

add to 1.

For products: column

j

PQ

P

times column

j

Q

The columns of

PQ

are

P

times the columns of

Q

(2.5). Each column of

Q

is a probability vector, so by the first part each column of

PQ

is one, hence

PQ

is stochastic.

P^k

is stochastic for all

k

, and so

P^kx_0

is a probability vector.

Induction on

k

P^{k+1} = P \cdot P^k

Quick check

P

is stochastic and

x = (0.2, 0.3, 0.5)

. What do the entries of

Px

add up to?

Worked example

Prove that the product

PQ

of two stochastic matrices is stochastic, and check it by squaring the weather matrix (columns

(0.8, 0.2)

and

(0.4, 0.6)

Solution.

Entries. $(PQ)_{ij} = \sum_k P_{ik}Q_{kj}$ is a sum of products of non-negative numbers, so it is at least $0$ . Products and sums of non-negative numbers are non-negative.
Column sum. $\sum_i (PQ)_{ij} = \sum_i \sum_k P_{ik}Q_{kj} = \sum_k Q_{kj}\sum_i P_{ik}$ . Swap the two finite sums, and pull $Q_{kj}$ out of the sum over $i$ because it does not depend on $i$ .
Use that $P$ is stochastic. $\sum_i P_{ik} = 1$ for every $k$ , so the column sum is $\sum_k Q_{kj} = 1$ . First $P$ ‘s columns add to 1, then $Q$ ‘s column does.
Numerical check. $P^2 = \begin{bmatrix} 0.72 & 0.56 \\ 0.28 & 0.44 \end{bmatrix}$ and the columns add to $0.72 + 0.28 = 1$ and $0.56 + 0.44 = 1$ . An independent check on the formula.

Answer. The product is stochastic. Interpretation: $P^2$ gives the chances of two steps, and two steps is still a chain that goes somewhere.

Staying put: stationary distributions

Definition B

Stationary distribution

A probability vector $\pi$ is a stationary distribution of the stochastic matrix $P$ if $P\pi = \pi$ . In the language of chapter 2.8, it is a probability vector that is an eigenvector of $P$ with eigenvalue $1$ .

In one lineA probability vector $\pi$ with $P\pi = \pi$ : the chances do not change when the surfer takes another step.

Why it existsIt is the long-run answer. If the chances settle down at all, they settle at a stationary distribution, and it is the PageRank vector.

Theorem B Bryan and Leise, Prop. 1

One is always an eigenvalue of a stochastic matrix

Every stochastic matrix $P$ has $1$ as an eigenvalue. So there is a non-zero real vector $v$ with $Pv = v$ .

In one lineEvery stochastic matrix has eigenvalue 1.

Why it is trueThe all-ones row vector is a left eigenvector with eigenvalue 1 because the columns add to 1. A matrix and its transpose share eigenvalues, so the matrix itself has eigenvalue 1 too.

ProofBryan and Leise

The idea: Find the eigenvector of the transpose, which is easy (all ones), then move the eigenvalue back to P because P and its transpose have the same characteristic polynomial.

P^{\mathsf T}\mathbf 1 = \mathbf 1

Entry

j

P^{\mathsf T}\mathbf 1

is the sum of column

j

P

, which is 1. (The columns of

P

are the rows of

P^{\mathsf T}

1

is an eigenvalue of

P^{\mathsf T}

\mathbf 1

is not the zero vector, so by the definition in 2.8 it is an eigenvector of

P^{\mathsf T}

with eigenvalue 1.

\det(\lambda I - P^{\mathsf T}) = \det\big((\lambda I - P)^{\mathsf T}\big) = \det(\lambda I - P)

The determinant of a transpose equals the determinant (2.7), and

(\lambda I - P)^{\mathsf T} = \lambda I - P^{\mathsf T}

P

and

P^{\mathsf T}

have the same eigenvalues, so

1

is an eigenvalue of

P

The eigenvalues are the roots of the characteristic polynomial (2.8). Equal polynomials have equal roots.

A non-zero real

v

with

Pv = v

exists.

P - I

is a real matrix with determinant

0

, so it is not invertible and its null space contains a non-zero vector. That vector can be taken real, since the system

(P - I)v = O

has real coefficients.

Why· The picture behind the proof

In the visualizer, the left eigenvector $\mathbf 1$ says “add up the bars”. The statement $\mathbf 1^{\mathsf T}P = \mathbf 1^{\mathsf T}$ is the fact that the total height of the bars is the same before and after a step: the bars are rearranged, not created. A quantity that every step leaves unchanged is exactly what an eigenvalue of 1 means. The matrix $P$ itself has a different eigenvector for eigenvalue 1 (the stationary bars), and that one is not all ones.

Worked example

Let M be a square matrix whose rows (not columns) each add to 1. Prove that 1 is an eigenvalue of M, and say how this differs from the case of a column-stochastic P.

Solution.

Compute $M\mathbf 1$ . Entry $i$ of $M\mathbf 1$ is row $i$ of $M$ dotted with $(1, \dots, 1)$ , which is the sum of row $i$ . Multiplying by the all-ones vector adds up each row.
Use the hypothesis. Every row adds to $1$ , so $M\mathbf 1 = \mathbf 1$ . This is the definition of the matrix.
Name the eigenvector. $\mathbf 1 \ne O$ , so $1$ is an eigenvalue of $M$ with eigenvector $\mathbf 1$ . An eigenvector is a non-zero vector with $Mv = \lambda v$ .
Compare with columns. For a column-stochastic $P$ the same computation gives $P^{\mathsf T}\mathbf 1 = \mathbf 1$ , an eigenvector of the transpose. Columns of $P$ are rows of $P^{\mathsf T}$ . Then $P$ itself gets the eigenvalue $1$ because $P$ and $P^{\mathsf T}$ have the same characteristic polynomial, but its eigenvector is a different vector, the stationary distribution.

Answer. $M\mathbf 1 = \mathbf 1$ , so $1$ is an eigenvalue and $\mathbf 1$ is its eigenvector. This is the row-stochastic convention of probability books. In this book the all-ones vector belongs to $P^{\mathsf T}$ , not to $P$ .

So there is an eigenvector. Is it a probability vector, and is it unique? The answers wait for the next sections. First, the size of the other eigenvalues.

Theorem B Bryan and Leise, Prop. 2

Eigenvalues of a stochastic matrix have size at most one

Let $P$ be stochastic and $Pv = \lambda v$ with $v \ne O$ (complex numbers allowed). Then $|\lambda| \le 1$ .

In one lineEvery eigenvalue $\lambda$ of a stochastic matrix, real or complex, satisfies $|\lambda| \le 1$ .

Why it is trueA step never increases the total size of a vector, measured by adding the absolute values of its entries. An eigenvector that grew by more than 1 per step would contradict that.

Here $|\lambda|$ is the size of $\lambda$ : for a complex number $a + bi$ it is $\sqrt{a^2 + b^2}$ , its distance from $0$ in the complex plane. For a vector $x$ (real or complex), let $\lVert x \rVert_1 = |x_1| + \dots + |x_n|$ be the 1-norm: add the sizes of the entries. It measures size in a different way from the length $\sqrt{x \cdot x}$ used in 2.9. We use only two of its properties: it is $0$ only for $O$ , and $\lVert cx \rVert_1 = |c|\,\lVert x \rVert_1$ .

ProofBryan and Leise

The idea: Show that P never makes the 1-norm bigger. Then an eigenvector with eigenvalue lambda has its norm multiplied by |lambda|, which therefore cannot exceed 1.

\displaystyle |(Px)_i| \le \sum_j P_{ij}\,|x_j|

Entry

i

Px

\sum_j P_{ij}x_j

. The absolute value of a sum is at most the sum of the absolute values (the triangle inequality), and

|P_{ij}x_j| = P_{ij}|x_j|

because

P_{ij} \ge 0

\displaystyle \lVert Px \rVert_1 \le \sum_i \sum_j P_{ij}|x_j|

Add this up over

i

\displaystyle = \sum_j |x_j| \Big( \sum_i P_{ij} \Big) = \sum_j |x_j| = \lVert x \rVert_1

Swap the sums, as in the previous proof, and use that every column of

P

adds to 1.

|\lambda|\,\lVert v \rVert_1 \le \lVert v \rVert_1

For an eigenvector,

Pv = \lambda v

, so

\lVert Pv \rVert_1 = |\lambda|\,\lVert v \rVert_1

|\lambda| \le 1

v \ne O

, so

\lVert v \rVert_1 > 0

, and we can divide.

Proof workshopRebuild the proof that no eigenvalue of a stochastic matrix is bigger than 1

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

The proof gives more than the statement. For every vector, $\lVert Px \rVert_1 \le \lVert x \rVert_1$ , and equality holds for non-negative $x$ (then no absolute values change). The triangle inequality is where mass can be lost: if the entries $P_{ij}x_j$ in a row have mixed signs, they partly cancel. We will use that.

Quick checkCan a stochastic matrix have the eigenvalue 2?

Worked example

Prove that for a stochastic matrix P and a vector x with all entries at least 0, the 1-norm of Px equals the 1-norm of x. Say where the inequality of the earlier proof becomes an equality.

Solution.

Sign of the entries. Every entry of $Px$ is $\sum_jP_{ij}x_j$ , a sum of products of non-negative numbers, so it is at least $0$ . Both $P_{ij}$ and $x_j$ are non-negative.
Drop the absolute values. So $\lVert Px \rVert_1 = \sum_i (Px)_i$ and $\lVert x \rVert_1 = \sum_j x_j$ . The 1-norm adds absolute values, and absolute values of non-negative numbers change nothing.
Add up the entries of $Px$ . $\sum_i\sum_jP_{ij}x_j = \sum_jx_j\sum_iP_{ij} = \sum_jx_j$ . Swap the finite sums, then each column of $P$ adds to $1$ .
Find the equality. In the earlier proof the only inequality was the triangle inequality $\big|\sum_jP_{ij}x_j\big| \le \sum_jP_{ij}|x_j|$ . For $x \ge 0$ the terms $P_{ij}x_j$ are all non-negative, so the left side equals the right side. The triangle inequality is an equality exactly when no terms cancel, and non-negative numbers cannot cancel.

Answer. $\lVert Px \rVert_1 = \lVert x \rVert_1$ for $x \ge 0$ . A vector with mixed signs can lose norm, because its positive and negative parts partly cancel. That cancellation is the “wobble” that shrinks as the chain settles.

Lemma B Bryan and Leise, Lemma

Other eigenvectors have entries adding to zero

Let $P$ be stochastic and $Pv = \lambda v$ with $\lambda \ne 1$ . Then $\mathbf 1^{\mathsf T}v = 0$ .

In one lineIf $Pv = \lambda v$ with $\lambda \ne 1$ , the entries of $v$ add to $0$ .

Why it is trueThe total of the entries is conserved by $P$ . A vector that gets multiplied by a number other than 1 and also keeps its total must have total zero.

ProofBryan and Leise

The idea: Compute the total of the entries of Pv in two ways.

\mathbf 1^{\mathsf T}(Pv) = \mathbf 1^{\mathsf T}v

\mathbf 1^{\mathsf T}P = \mathbf 1^{\mathsf T}

because the columns add to 1.

\mathbf 1^{\mathsf T}(Pv) = \lambda\,\mathbf 1^{\mathsf T}v

Pv = \lambda v

(\lambda - 1)\,\mathbf 1^{\mathsf T}v = 0

Subtract the two lines.

\mathbf 1^{\mathsf T}v = 0

\lambda \ne 1

, so the first factor is not zero and can be divided out.

Worked example

Find the stationary distribution of the weather chain: a sunny day is followed by a sunny day with chance 0.8 and a rainy day with chance 0.2; a rainy day is followed by a sunny day with chance 0.4 and a rainy day with chance 0.6. Also find the eigenvalues, and the chances

k

days after a sunny day.

Solution.

Write the matrix. $P = \begin{bmatrix} 0.8 & 0.4 \\ 0.2 & 0.6 \end{bmatrix}$ , with the sunny state first. Column 1 describes what follows a sunny day, column 2 what follows a rainy one. Each column adds to 1.
Write $P\pi = \pi$ as a homogeneous system. $(P - I)\pi = O$ gives $-0.2\pi_1 + 0.4\pi_2 = 0$ and $0.2\pi_1 - 0.4\pi_2 = 0$ . Moving $\pi$ to the left side makes it a null-space problem, as in 2.8.
Solve. Both equations say $\pi_1 = 2\pi_2$ . A basis of the null space is $(2, 1)$ . The two equations are multiples of each other, because $P - I$ is singular, as the theorem on eigenvalue 1 promised.
Scale to a probability vector. Divide by the sum $3$ : $\pi = (\tfrac23, \tfrac13)$ . A stationary distribution must be a probability vector, with entries adding to 1.
Find the other eigenvalue. The trace of $P$ is $1.4$ and it equals the sum of the eigenvalues (2.8), so the other eigenvalue is $0.4$ . Its eigenvector is $(-1, 1)$ , the vector with entries adding to $0$ , as the lemma says. Check: $P(-1, 1) = (-0.8 + 0.4,\ -0.2 + 0.6) = (-0.4, 0.4) = 0.4\,(-1, 1)$ .
Chances after a sunny day. Write $x_0 = (1, 0) = \pi + \tfrac13(1, -1)$ . Applying $P$ $k$ times multiplies each eigen-part by its eigenvalue: $x_k = \pi + \tfrac13(0.4)^k(1, -1)$ , that is $\big(\tfrac23 + \tfrac13(0.4)^k,\ \tfrac13 - \tfrac13(0.4)^k\big)$ . $P\pi = \pi$ and $P(1, -1) = 0.4\,(1, -1)$ .
Check $k = 1$ . $x_1 = (\tfrac23 + 0.1333, \tfrac13 - 0.1333) = (0.8, 0.2)$ , the first column of $P$ . An independent check of the formula.

Answer. Long-run, two days in three are sunny. The chances approach $(\tfrac23, \tfrac13)$ geometrically, with the error shrinking by a factor $0.4$ each day.

Quick checkSolving

(P - I)\pi = O

for a

2\times2

stochastic matrix gives the null-space vector

(3, 4)

. What is the stationary distribution?

Your answerA weather chain has

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

. What fraction of days are sunny in the long run (the first entry of

\pi

Your answerA

2\times2

stochastic matrix has

P = \begin{bmatrix} 0.75 & 0.5 \\ 0.25 & 0.5 \end{bmatrix}

. What is its other eigenvalue (besides 1)?

Worked example Bryan and Leise's example; the visualizer above

Find the stationary distribution of the four-page web (page 1 links to 2, 3, 4; page 2 to 3, 4; page 3 to 1; page 4 to 1, 3).

Solution.

Write $P\pi = \pi$ row by row, using the matrix in the chapter’s introduction. $\pi_1 = \pi_3 + \tfrac12\pi_4$ , $\ \pi_2 = \tfrac13\pi_1$ , $\ \pi_3 = \tfrac13\pi_1 + \tfrac12\pi_2 + \tfrac12\pi_4$ , $\ \pi_4 = \tfrac13\pi_1 + \tfrac12\pi_2$ . Each equation says “page $i$ gets the same share after a step as before”. Row $i$ lists the pages that link to $i$ and how much of their share they send.
Choose a parameter. Put $\pi_1 = 3t$ . Then $\pi_2 = t$ . Equation 2 gives $\pi_2$ in terms of $\pi_1$ ; choosing $\pi_1 = 3t$ avoids fractions. One equation is redundant because $P - I$ is singular, so one free parameter is expected.
Find $\pi_4$ and $\pi_3$ . $\pi_4 = \tfrac13(3t) + \tfrac12 t = \tfrac32 t$ . Then $3t = \pi_3 + \tfrac34 t$ gives $\pi_3 = \tfrac94 t$ . Equation 4 gives $\pi_4$ . Equation 1 gives $\pi_3$ .
Check the unused equation. Equation 3: $\tfrac94 t \overset{?}{=} t + \tfrac12 t + \tfrac34 t = \tfrac94 t$ . Yes. It was not used, so it checks the arithmetic independently.
Scale. The entries are $3t, t, \tfrac94 t, \tfrac32 t$ , which add to $\tfrac{31}{4}t$ . Setting this to 1 gives $t = \tfrac4{31}$ and $\pi = (12, 4, 9, 6)/31$ . A probability vector must add to 1.

Answer. $\pi = (12, 4, 9, 6)/31 \approx (0.387, 0.129, 0.290, 0.194)$ , the heights the visualizer settles on. Page 1 ranks first, although page 3 has the most links in. Page 3 gives its entire share to page 1.

Does it settle? Convergence and the power method

Eigenvalue 1 exists and the others have size at most 1. If every other eigenvalue has size strictly less than 1, repeated multiplication kills their parts and leaves only the eigenvalue-1 part. This is the “apply it 100 times” idea of chapter 2.8.

Theorem B Strang 10.3; Bryan and Leise, section 4

Convergence for a diagonalizable chain with a simple eigenvalue 1

Suppose $P$ is stochastic and diagonalizable, with eigenvalues $1, \lambda_2, \dots, \lambda_n$ where $|\lambda_i| < 1$ for $i \ge 2$ . Then there is exactly one stationary distribution $\pi$ , and for every probability vector $x_0$ ,

P^kx_0 \to \pi \quad\text{as } k \to \infty, \qquad\text{with error of size about } |\lambda_2|^k,

where $\lambda_2$ is the eigenvalue of largest size among the others.

In one lineLet $P$ be stochastic and diagonalizable. If $1$ is an eigenvalue with a one-dimensional eigenspace and every other eigenvalue has size less than 1, then $P^kx_0$ approaches the same stationary distribution $\pi$ from every starting probability vector $x_0$ .

Why it is trueWrite $x_0$ in the eigenvectors. Applying $P$ $k$ times multiplies the part along each eigenvector by $\lambda^k$ . The parts with $|\lambda|$ less than 1 die away, and only the part along $\pi$ is left.

ProofStrang 10.3

The idea: Expand x0 in an eigenbasis. The coefficient of the eigenvalue-1 part is forced to be 1 by the fact that probability is conserved (the lemma). Every other part is multiplied by lambda to the k, which goes to 0.

Let

v_1, \dots, v_n

be an eigenbasis,

\lambda_1 = 1

P

is diagonalizable (2.8), so there is a basis of eigenvectors

v_1, \dots, v_n

\mathbb C^n

with

Pv_i = \lambda_iv_i

. We take

\lambda_1 = 1

, with eigenvector

v_1

. The eigenvalues are complex numbers in general.

The entries of

v_i

add to

0

for

i \ge 2

By the lemma,

\mathbf 1^{\mathsf T}v_i = 0

for

i \ge 2

, because

\lambda_i \ne 1

\mathbf 1^{\mathsf T}v_1 \ne 0

. Rescale

v_1

(dividing by the number

\mathbf 1^{\mathsf T}v_1

) so that its entries add to 1, and call it

\pi

. We show in the last step that

\pi

is real.

If also

\mathbf 1^{\mathsf T}v_1 = 0

, then

\mathbf 1^{\mathsf T}

would vanish on a whole basis, hence on every vector. But

\mathbf 1^{\mathsf T}\mathbf 1 = n \ne 0

.This is the quiet step that makes the proof work.

x_0 = c_1\pi + c_2v_2 + \dots + c_nv_n

Every vector is a combination of a basis (2.2).

1 = c_1

Apply

\mathbf 1^{\mathsf T}

. The left side is

1

(probability vector). On the right, the terms with

i \ge 2

vanish, and

\mathbf 1^{\mathsf T}\pi = 1

P^kx_0 = \pi + c_2\lambda_2^kv_2 + \dots + c_n\lambda_n^kv_n

Apply

P

k

times;

P^kv_i = \lambda_i^kv_i

because each application multiplies by

\lambda_i

k \to \infty

, every term after the first goes to

O

, so

P^kx_0 \to \pi

|\lambda_i| < 1

for

i \ge 2

, so

\lambda_i^k \to 0

(a geometric sequence with ratio of size less than 1). The error is dominated by the largest

|\lambda_i|

\pi

is a stationary distribution, and it is the only one.

Every

P^kx_0

is a real probability vector (the first theorem of this chapter), and a limit of such vectors is real, has entries at least

0

and adds to 1. So

\pi

is a probability vector. Applying

P

to both sides of

P^kx_0 \to \pi

gives

P\pi = \pi

. Uniqueness: any stationary distribution

\pi'

satisfies

P^k\pi' = \pi'

, so by the above it also tends to

\pi

Why· The picture behind the proof

Press Next in the first visualizer again and watch the bars. The starting bars are one tall bar on page 1. Each step keeps the total height and removes a little more of the “wobble”, the part along the other eigenvectors, which has total height zero (it has bars above and below the stationary heights). The wobble shrinks by a factor of $|\lambda_2| \approx 0.55$ at each step for this web, which is why about eight to ten steps leave bars that look still. The numbers are in the power-method example below.

Definition B

Power method

The power method for a matrix $A$ chooses a starting vector $x_0$ and computes $x_{k+1} = Ax_k$ (in general, rescaling each result to keep its size under control). If the eigenvalue of largest size is unique and the starting vector has a component along its eigenvector, the iterates line up with that eigenvector, at the rate $|\lambda_2/\lambda_1|^k$ . For a stochastic matrix and a probability vector no rescaling is needed, since $Px$ is again a probability vector, and the eigenvalue of largest size is $1$ .

In one lineFind the dominant eigenvector by starting anywhere and applying the matrix again and again.

Why it existsIt computes the eigenvector using only matrix-times-vector, which is cheap even when the matrix is enormous and never written down in full.

Worked example Bryan and Leise's example; the visualizer above

Run the power method on the four-page web from

x_0 = (1, 0, 0, 0)

, and watch the error shrink.

Solution.

Start. $x_0 = (1, 0, 0, 0)$ , so the surfer is on page 1. The 1-norm distance to $\pi = (12, 4, 9, 6)/31$ is about $1.226$ . We measure the error as $\lVert x_k - \pi \rVert_1$ , the sum of the absolute differences of the entries.
Apply $P$ once. $x_1 = Px_0 = (0, \tfrac13, \tfrac13, \tfrac13)$ , error $\approx 0.774$ . Applying $P$ to $e_1$ picks out column 1: page 1 sends a third of the surfer to each of pages 2, 3, 4.
Apply $P$ again. $x_2 = (\tfrac12, 0, \tfrac13, \tfrac16)$ , error $\approx 0.312$ . Page 1 receives all of page 3’s $\tfrac13$ and half of page 4’s $\tfrac13$ , which is $\tfrac13 + \tfrac16 = \tfrac12$ . Page 2 receives nothing, since only page 1 links to it and page 1 is empty.
Keep going. $x_3 = (\tfrac5{12}, \tfrac16, \tfrac14, \tfrac16)$ with error $\approx 0.134$ , and $x_4 = (\tfrac13, \tfrac5{36}, \tfrac{11}{36}, \tfrac29)$ with error $\approx 0.108$ . The entries rise and fall around the final values, because two of the other three eigenvalues of $P$ are complex and make their part of the error rotate as it shrinks.
Read the rate. $x_7 = (\tfrac{55}{144}, \tfrac{55}{432}, \tfrac{127}{432}, \tfrac{85}{432})$ has error $\approx 0.0137$ , and $x_{12} \approx (0.3866, 0.1292, 0.2904, 0.1938)$ has error $\approx 0.00095$ . Over steps 4 to 7 the error shrinks by about $0.5$ per step, close to $|\lambda_2| \approx 0.547$ . The eigenvalues other than $1$ are the roots of $12\lambda^3 + 12\lambda^2 + 6\lambda + 1$ , about $-0.279$ and $-0.361 \pm 0.411i$ .
Verify the limit exactly. $P\pi = \tfrac1{31}(9 + 3,\ 4,\ 4 + 2 + 3,\ 4 + 2) = \tfrac1{31}(12, 4, 9, 6) = \pi$ . One application of $P$ to $\pi$ in exact arithmetic leaves it unchanged, so $\pi$ is stationary.

The step-through below shows the same iteration with the exact fractions.

Answer. The iterates approach $(12, 4, 9, 6)/31$ . A web of billions of pages needs the same steps; what changes is that each application of $P$ costs about one operation per link, not one per pair of pages.

Python labThe power method on the four-page web, and the Google matrix

import numpy as np

# Column j lists where a surfer on page j goes next (Bryan and Leise's web).
P = np.array([[0,   0,   1, 1/2],
              [1/3, 0,   0, 0  ],
              [1/3, 1/2, 0, 1/2],
              [1/3, 1/2, 0, 0  ]])
exact = np.array([12, 4, 9, 6]) / 31

x = np.array([1.0, 0, 0, 0])            # start on page 1
for k in range(0, 31, 5):
    print(f"step {k:2d}: x = {np.round(x, 4)}   error = {np.abs(x - exact).sum():.2e}")
    for _ in range(5):
        x = P @ x

vals = np.linalg.eigvals(P)
print("eigenvalue sizes:", np.round(sorted(abs(vals), reverse=True), 4))

d, n = 0.85, 4                          # the Google matrix: follow a link with probability d
G = d * P + (1 - d) / n * np.ones((n, n))
x = np.ones(n) / n
for _ in range(100):
    x = G @ x
print("PageRank with d = 0.85:", np.round(x, 4))

Try this. The error shrinks by a factor of about $0.0485$ every five steps. Check that this is $0.5468^5$ , where $0.5468$ is the second largest eigenvalue size printed at the end: the rate $|\lambda_2/\lambda_1|^k$ from the text. Then change d to $0.5$ and see the ranking move toward equal shares, and add a fifth page that links only to page 1.

Your answerIn the four-page web, a surfer has the chances

x = (\tfrac12, 0, \tfrac13, \tfrac16)

. What is entry 3 of

Px

, the chance of being on page 3 one step later?

Worked example

A walker moves on the graph with vertices 1, 2, 3, 4 and edges 12, 23, 34, 41, 13, each step to a uniformly random neighbour. Write P, find the stationary distribution, and say whether the walker's chances settle.

Solution.

List the neighbours. Vertex 1 has neighbours 2, 3, 4. Vertex 2 has 1, 3. Vertex 3 has 2, 4, 1. Vertex 4 has 3, 1. Read each vertex’s edges from the list.
Write the columns. Column $j$ puts $1/\deg j$ on each neighbour of $j$ : column 1 is $(0, \tfrac13, \tfrac13, \tfrac13)$ , column 2 is $(\tfrac12, 0, \tfrac12, 0)$ , column 3 is $(\tfrac13, \tfrac13, 0, \tfrac13)$ , column 4 is $(\tfrac12, 0, \tfrac12, 0)$ . From a vertex with $\ell$ neighbours each neighbour has chance $1/\ell$ . Each column adds to $1$ .
Use the degree rule. The degrees are $3, 2, 3, 2$ , adding to $10 = 2 \times 5$ edges. So $\pi = (3, 2, 3, 2)/10$ . On an undirected graph the walker visits each vertex in proportion to its degree (proved in the “Where it is used” section).
Check it. Row 1 of $P\pi$ is $\tfrac12\pi_2 + \tfrac13\pi_3 + \tfrac12\pi_4 = \tfrac1{10} + \tfrac1{10} + \tfrac1{10} = \tfrac3{10}$ . Row 2 is $\tfrac13\pi_1 + \tfrac13\pi_3 = \tfrac2{10}$ . Multiplying back is the check that does not depend on the rule being remembered correctly.
Decide about settling. The graph has triangles ( $1, 2, 3$ and $1, 3, 4$ ), so the walker can return in 2 or 3 steps, and the chain is not stuck in a lockstep cycle. The eigenvalues are $1$ , $-\tfrac13$ , $-\tfrac23$ and $0$ , all other than $1$ of size less than $1$ . Contrast with the path $1 - 2 - 3$ , where the walker alternates between the middle and the ends and the eigenvalue $-1$ never fades.

Answer. $\pi = (3, 2, 3, 2)/10$ , and $P^kx_0 \to \pi$ from every start, at the rate $(\tfrac23)^k$ .

Your answerA walker on an undirected graph with 5 edges has stationary distribution

\pi_v = \deg(v)/10

. What is

\pi_v

for a vertex of degree 3?

Now the theorem that says when the hypotheses hold. It is the major result of this area, and we state it without proof.

Theorem B Perron 1907, Frobenius 1912; Bryan and Leise, section 4 (proof not given here)

Perron–Frobenius theorem for regular chains

Call a stochastic matrix regular if some power $P^m$ has every entry strictly positive (every state can reach every state in exactly $m$ steps). For a regular $P$ , there is exactly one stationary distribution $\pi$ , all of its entries are positive, every eigenvalue other than $1$ has size less than $1$ , and $P^kx_0 \to \pi$ for every probability vector $x_0$ .

In one lineIf some power of the stochastic matrix $P$ has all entries strictly positive (a regular chain), then $1$ is a simple eigenvalue with a positive eigenvector, every other eigenvalue has size less than 1, and $P^kx_0 \to \pi$ for every probability vector $x_0$ .

Why it is truePositive entries mean every state can reach every other, and in a way that mixes time well enough to forget the start. That removes the ways the conclusion can fail.

We do not prove this theorem. It is a result of Perron (1907) for positive matrices, extended by Frobenius (1912). Diagonalizability is not needed. The proof without it uses the Jordan form, which is beyond this chapter. For positive matrices there is a short idea behind the size claim, and it reuses the proof that $|\lambda| \le 1$ .

Beyond the course: for understanding· Why positive entries push the other eigenvalues strictly inside (a sketch)

In the proof that $\lVert Px \rVert_1 \le \lVert x \rVert_1$ , equality needs equality in every triangle inequality $\big|\sum_j P_{ij}x_j\big| \le \sum_j P_{ij}|x_j|$ . For complex numbers, this holds only if all the non-zero terms $P_{ij}x_j$ point in the same direction in the complex plane. If every $P_{ij}$ is positive, that means all entries $x_j$ of the vector point in the same direction. Rotate the vector so they are all real and at least $0$ . Then $Px$ is also real and non-negative, so $Px = \lambda x$ forces $\lambda \ge 0$ , and the equality of norms forces $\lambda = 1$ . So an eigenvalue of size exactly 1 must be $1$ itself, and its eigenvector can be taken positive. An eigenvector with mixed signs loses norm at every step: that is the “wobble” shrinking in the picture. For a regular chain, apply the same argument to the positive matrix $P^m$ . It shows that an eigenvalue $\lambda$ of $P$ with $|\lambda| = 1$ has $\lambda^m = 1$ . To get $\lambda = 1$ one more fact is needed, that $1$ is a simple eigenvalue. This is a sketch of the main idea. It leaves out why $1$ is a simple eigenvalue, that last step, and the case without diagonalizability.

Quick check

P

is the stochastic matrix that swaps the two entries of a vector (columns

(0, 1)

and

(1, 0)

), and the surfer starts at

x_0 = (1, 0)

. What happens to

P^kx_0

What goes wrong on the real web

Where this came from· Page, Brin and the random surfer

In 1996 Larry Page and Sergey Brin, then students at Stanford, began work on ranking web pages by importance, as well as by whether they contained the search words. They borrowed an idea from scholarly citations: a page is important if important pages link to it. That sentence is circular. The way out was the surfer who follows links at random, so that importance becomes a stationary distribution. Brin and Page’s 1998 paper on the Google search engine gives $d = 0.85$ as the usual damping factor, and the Stanford technical report of the same year by Page, Brin, Rajeev Motwani and Terry Winograd describes the ranking itself. The patent, granted in 2001 with Page as inventor, belongs to Stanford, and Google, founded in 1998, held an exclusive licence.

The picture works for the four-page web. The real web has features that break the hypotheses, and each is shown below with a small example. One idea fixes all of them.

Dead ends (dangling pages). A page with no links has a zero column, so $P$ is not stochastic. A surfer reaching it vanishes: for pages $1 \to 2$ and a dead-end page 2, $x_k \to (0, 0)$ . Probability leaks out.
Cycles in lockstep (periodicity). Pages $1 \leftrightarrow 2$ swap the surfer forever. The eigenvalue $-1$ never fades, and the chances never settle.
Disconnected pieces. If pages $\{1, 2\}$ link only to each other and $\{3, 4\}$ link only to each other, then every mixture of the two pieces’ stationary vectors is stationary. The ranking is not unique.
Spider traps. A page that links only to itself (or a small group that only links to itself) absorbs the surfer for good. With pages $1 \to 2, 3$ ; $2 \to 1$ ; $3 \to 3$ , the only stationary distribution is $(0, 0, 1)$ : page 3 gets all the rank and the others get nothing.

Google’s fix is to make the surfer occasionally bored. This is the matrix.

Definition B

Google matrix

Let $P$ be stochastic (first replace every zero column, from a dead-end page, by the column $(\tfrac1n, \dots, \tfrac1n)$ : a stuck surfer jumps to a random page). Choose a damping factor $d$ with $0 \le d < 1$ . The Google matrix is

G = d\,P + \frac{1 - d}{n}\,\mathbf 1\mathbf 1^{\mathsf T},

where $\mathbf 1\mathbf 1^{\mathsf T}$ is the $n \times n$ matrix with every entry $1$ . So $G_{ij} = dP_{ij} + \tfrac{1-d}{n}$ . Page and Brin’s papers use $d = 0.85$ : the surfer follows a link 85 times in 100 and teleports 15 times in 100.

In one line $G = dP + \tfrac{1-d}{n}\mathbf 1\mathbf 1^{\mathsf T}$ : with chance $d$ the surfer follows a link, and with chance $1 - d$ jumps to a page chosen uniformly at random.

Why it existsThe random jumps connect every page to every page, so none of the failures above can happen, and a unique ranking always exists.

Each column of $G$ adds to $d \cdot 1 + n \cdot \tfrac{1-d}{n} = 1$ , so $G$ is stochastic. Every entry is at least $\tfrac{1-d}{n} > 0$ , so $G$ is regular (already $G^1$ is positive). By Perron–Frobenius, which we did not prove, $G$ has a unique stationary distribution. For this matrix we can prove everything we need directly, and get a speed guarantee at the same time.

Theorem B Haveliwala and Kamvar (2003) for the rate; Bryan and Leise, section 5

The Google matrix has a unique stationary distribution

Let $P$ be stochastic, $0 \le d < 1$ , and $G = dP + \tfrac{1-d}{n}\mathbf 1\mathbf 1^{\mathsf T}$ . Then:

$G$ is stochastic with every entry at least $\tfrac{1-d}{n}$ .
$G$ has a stationary distribution $\pi$ , and every entry of $\pi$ is at least $\tfrac{1-d}{n}$ .
For every probability vector $x_0$ and every $k$ , $\lVert G^kx_0 - \pi \rVert_1 \le 2d^k$ . In particular $\pi$ is the only stationary distribution.
Every eigenvalue $\lambda \ne 1$ of $G$ has $|\lambda| \le d$ .

In one lineFor $0 \le d < 1$ , $G$ has exactly one stationary distribution $\pi$ , all its entries are at least $\tfrac{1-d}{n}$ , and from any starting probability vector $\lVert G^kx_0 - \pi \rVert_1 \le 2d^k$ . Every eigenvalue other than $1$ has size at most $d$ .

Why it is trueOn vectors whose entries add to zero, the teleport part of $G$ vanishes and $G$ acts as $d$ times $P$ . So the wobble shrinks by at least a factor $d$ per step, whatever the web looks like.

ProofBryan and Leise section 5; Haveliwala and Kamvar

The idea: Existence: the eigenvalue-1 theorem plus a sign argument. Convergence: the difference of two probability vectors adds to zero, and on such vectors G is d times P, which never increases the 1-norm.

G

is stochastic with all entries positive.

Part 1. Each column of

G

adds to

d \cdot 1 + n \cdot \tfrac{1-d}{n} = 1

, and each entry is

dP_{ij} + \tfrac{1-d}{n} \ge \tfrac{1-d}{n}

Take a real

v \ne O

with

Gv = v

Part 2. By the eigenvalue-1 theorem

G

has a non-zero real

v

with

Gv = v

Suppose

v

has entries of both signs. Then

|v_i| = |(Gv)_i| < \sum_j G_{ij}|v_j|

for every

i

Suppose, for contradiction, that

v

has an entry above

0

and an entry below

0

. In every row

i

, the term with the negative entry

v_k

satisfies

G_{ik}v_k < G_{ik}|v_k|

because

G_{ik} > 0

(strictly). So

\big|\sum_j G_{ij}v_j\big| < \sum_j G_{ij}|v_j|

in every row: the positive and negative terms cancel a little.

Then

\lVert v \rVert_1 < \sum_j |v_j|\sum_i G_{ij} = \lVert v \rVert_1

, which is absurd.

Add over

i

, swap the sums, and use that the columns of

G

add to 1 (the computation from the 1-norm theorem, now with strict inequality).

v

can be taken non-negative, and rescaled to a stationary distribution

\pi

So all entries of

v

have the same sign (some may be zero). Replace

v

-v

if needed, so that

v \ge 0

with

v \ne O

. Then its entries add to a positive number, and dividing by it gives a probability vector

\pi

with

G\pi = \pi

Every

\pi_i \ge \tfrac{1-d}{n} > 0

Since

G\pi = \pi

and

\pi

adds to 1, each entry is

\pi_i = (G\pi)_i = \sum_j G_{ij}\pi_j \ge \tfrac{1-d}{n}\sum_j\pi_j

Gy = dPy

Part 3. Let

y

be any vector whose entries add to

0

. Then

\mathbf 1\mathbf 1^{\mathsf T}y = \mathbf 1\,(\mathbf 1^{\mathsf T}y) = O

, the teleport part sees nothing.This is the heart of the proof: the damping splits G into 'follow a link' (scaled by d) and 'teleport', and the difference of two probability vectors is invisible to teleporting.

G^ky = d^kP^ky

, and

\lVert G^ky \rVert_1 \le d^k\lVert y \rVert_1

\mathbf 1^{\mathsf T}(Py) = \mathbf 1^{\mathsf T}y = 0

, so

Py

also adds to

0

. Repeating the step

k

times, and using

\lVert Pz \rVert_1 \le \lVert z \rVert_1

each time, gives the bound.

\lVert G^kx_0 - \pi \rVert_1 = \lVert G^k(x_0 - \pi) \rVert_1 \le 2d^k

y = x_0 - \pi

adds to

1 - 1 = 0

, and

G^k\pi = \pi

. The triangle inequality gives

\lVert x_0 - \pi \rVert_1 \le \lVert x_0 \rVert_1 + \lVert \pi \rVert_1 = 2

The stationary distribution is unique.

\pi'

is also stationary, then

G^k\pi' = \pi'

, so

\lVert \pi' - \pi \rVert_1 \le 2d^k

for every

k

. This tends to

0

, so

\pi' = \pi

|\lambda|\,\lVert v \rVert_1 = d\,\lVert Pv \rVert_1 \le d\,\lVert v \rVert_1

, so

|\lambda| \le d

Part 4. If

Gv = \lambda v

with

\lambda \ne 1

, then

\mathbf 1^{\mathsf T}v = 0

by the lemma, so

\lambda v = Gv = dPv

. Take 1-norms and use the bound

\lVert Pv \rVert_1 \le \lVert v \rVert_1

Proof workshopRebuild the speed bound: the Google chain forgets its start at least as fast as d to the k

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Why· The picture behind the proof

Turn on the damping slider in the visualizer below. At $d = 1$ you get the undamped web. Lower $d$ and the stationary bars flatten toward equal heights, because more of the surfer’s time is spent teleporting. At $d = 0.85$ the bars become $(0.368, 0.142, 0.288, 0.202)$ instead of $(0.387, 0.129, 0.290, 0.194)$ : pages ranked low gain a little, high-ranked pages lose a little. Step through with the slider at a small $d$ and the bars settle in very few steps; at $d$ near $1$ they take longer. That is the bound $2d^k$ in motion: damping is the price paid for speed and uniqueness.

Quick checkWhy does the damping factor guarantee a unique ranking and fast convergence?

How fast is $2d^k$ for $d = 0.85$ ? $0.85^{50} \approx 3.0 \times 10^{-4}$ and $0.85^{100} \approx 8.7 \times 10^{-8}$ . The bound does not depend on the number of pages. This is the answer to Spagnolie’s “how can you even compute?!”. Page, Brin, Motwani and Winograd (1998) report that for a web of 322 million links, the iteration converged to a tolerable limit in about 52 steps. Two facts make each step cheap. First, $P$ is sparse: a page has maybe tens of links, so $Px$ costs about one operation per link, not $n^2$ . Second, one never builds the dense matrix $G$ : for a probability vector $x$ ,

Gx = d\,Px + \frac{1-d}{n}\,\mathbf 1\,(\mathbf 1^{\mathsf T}x) = d\,Px + \frac{1-d}{n}\,\mathbf 1 ,

so a step of the damped chain is a step of the sparse chain, scaled by $d$ , plus the same small number added to every page.

Worked example

Let G = dP + ((1 − d)/n)·1·1ᵀ with P stochastic. Prove that for every probability vector x, Gx = dPx + ((1 − d)/n)·1, and that Gx is a probability vector.

Solution.

Split the product. $Gx = dPx + \tfrac{1-d}{n}\mathbf 1(\mathbf 1^{\mathsf T}x)$ . Matrix multiplication distributes over the sum, and we group $\mathbf 1\mathbf 1^{\mathsf T}x$ as $\mathbf 1(\mathbf 1^{\mathsf T}x)$ , which is allowed because matrix multiplication is associative.
Evaluate the bracket. $\mathbf 1^{\mathsf T}x$ is the sum of the entries of $x$ , which is $1$ . $x$ is a probability vector.
Conclude the formula. $Gx = dPx + \tfrac{1-d}{n}\mathbf 1$ . Replace the bracket by $1$ . The dense matrix $G$ never needs to be written down.
Entries are non-negative. $Px$ has entries at least $0$ and $0 \le d < 1$ , and the added number $\tfrac{1-d}{n}$ is positive. Sums and products of non-negative numbers are non-negative.
Entries add to 1. The entries of $dPx$ add to $d\cdot1$ because $Px$ is a probability vector. The added vector contributes $n\cdot\tfrac{1-d}{n} = 1 - d$ . The total is $d + (1 - d) = 1$ . This is the stochastic-matrix theorem for $P$ , plus counting $n$ equal entries.

Answer. $Gx = dPx + \tfrac{1-d}{n}\mathbf 1$ , and $Gx$ is a probability vector.

Your answerThe Google matrix for

n = 4

pages with

d = 0.85

has

G_{ij} = 0.85\,P_{ij} + \tfrac{0.15}{4}

. If

P_{21} = \tfrac13

, what is

G_{21}

(to 4 decimal places is plenty)?

Your answerFor the Google matrix with

d = 0.9

, the bound

\lVert G^kx_0 - \pi \rVert_1 \le 2d^k

holds. What is the smallest whole number

k

for which the bound is below

0.01

Worked example

Find the PageRank vector of the three-page web (1 links to 2 and 3; 2 links to 3; 3 links to 1) with damping factor

d = \tfrac34

Solution.

State what to solve. $G\pi = \pi$ with $\mathbf 1^{\mathsf T}\pi = 1$ . Since $G\pi = d\,P\pi + \tfrac{1-d}{n}\mathbf 1$ for a probability vector, this is $(I - dP)\pi = \tfrac{1-d}{n}\mathbf 1 = \tfrac1{12}\mathbf 1$ . Using the shortcut for $Gx$ avoids writing the full $G$ . Here $n = 3$ and $1 - d = \tfrac14$ .
Write the three equations, with $P$ from the first example: $\pi_1 - \tfrac34\pi_3 = \tfrac1{12}$ , $\ \pi_2 - \tfrac38\pi_1 = \tfrac1{12}$ , $\ \pi_3 - \tfrac38\pi_1 - \tfrac34\pi_2 = \tfrac1{12}$ . Row $i$ of $P$ lists which pages send surfers to page $i$ . Page 1 receives all of page 3; page 2 receives half of page 1; page 3 receives half of page 1 and all of page 2.
Express $\pi_1$ and $\pi_2$ in terms of $\pi_3$ . $\pi_1 = \tfrac1{12} + \tfrac34\pi_3$ . Then $\pi_2 = \tfrac1{12} + \tfrac38\pi_1 = \tfrac{11}{96} + \tfrac9{32}\pi_3$ . Equations 1 and 2 solve for the first two unknowns directly.
Substitute into equation 3. $\pi_3 = \tfrac1{12} + \tfrac38\big(\tfrac1{12} + \tfrac34\pi_3\big) + \tfrac34\big(\tfrac{11}{96} + \tfrac9{32}\pi_3\big)$ . The constants add to $\tfrac1{12} + \tfrac1{32} + \tfrac{11}{128} = \tfrac{77}{384}$ , and the $\pi_3$ terms to $\tfrac9{32}\pi_3 + \tfrac{27}{128}\pi_3 = \tfrac{63}{128}\pi_3$ . Common denominator $384$ for the constants: $32 + 12 + 33 = 77$ .
Solve for $\pi_3$ . $\big(1 - \tfrac{63}{128}\big)\pi_3 = \tfrac{77}{384}$ , so $\tfrac{65}{128}\pi_3 = \tfrac{77}{384}$ and $\pi_3 = \tfrac{77}{195}$ . Multiply both sides by $\tfrac{128}{65}$ .
Back-substitute. $\pi_1 = \tfrac1{12} + \tfrac34 \cdot \tfrac{77}{195} = \tfrac{74}{195}$ and $\pi_2 = \tfrac{11}{96} + \tfrac9{32} \cdot \tfrac{77}{195} = \tfrac{44}{195}$ . Plug $\pi_3$ into the formulas of step 3.
Check. $\tfrac{74 + 44 + 77}{195} = 1$ , and every entry is at least $\tfrac{1-d}{n} = \tfrac1{12} \approx 0.083$ . The theorem promises a probability vector with entries at least $\tfrac{1-d}{n}$ .

Answer. $\pi = (74, 44, 77)/195 \approx (0.379, 0.226, 0.395)$ . Compare the undamped ranking $(2, 1, 2)/5 = (0.4, 0.2, 0.4)$ : damping pulls the answer toward equal shares. (The undamped matrix has eigenvalues $1$ and $\tfrac{-1 \pm i}{2}$ , which have size $0.707$ .)

Worked example

A spider trap: page 1 links to 2 and 3, page 2 links to 1, page 3 links only to itself. Find the undamped stationary distribution and the PageRank with

d = 0.85

Solution.

Write $P$ . $P = \begin{bmatrix} 0 & 1 & 0 \\ \tfrac12 & 0 & 0 \\ \tfrac12 & 0 & 1 \end{bmatrix}$ . Column 3 is $(0, 0, 1)$ because page 3 sends the surfer back to itself.
Undamped stationary vectors. $P\pi = \pi$ : the first equation is $\pi_1 = \pi_2$ , the second is $\pi_2 = \tfrac12\pi_1$ . Together, $\pi_1 = \pi_2 = 0$ . The third equation then holds for any $\pi_3$ , and $\pi_3 = 1$ . Page 1 and 2 keep losing half their chance to page 3, which never returns it.
Read the meaning. $\pi = (0, 0, 1)$ : page 3 gets all the rank. Starting anywhere, the surfer ends in the trap. The trap is a set of pages with no links out, which breaks the “every page can reach every page” requirement.
Damp it. Solve $(I - 0.85P)\pi = \tfrac{0.15}{3}\mathbf 1$ exactly. The solution is $\pi = (74, 57, 380)/511 \approx (0.145, 0.112, 0.744)$ . The same method as the previous example, with $d = 17/20$ ; the unique solution is guaranteed by the theorem. Check: $74 + 57 + 380 = 511$ and every entry exceeds $0.05$ .

Answer. Undamped: $(0, 0, 1)$ . Damped with $d = 0.85$ : about $(0.145, 0.112, 0.744)$ . Damping lets the other pages keep a share. The trap still takes about three quarters of the rank. Real search engines had to deal with exactly this: people built groups of pages that link only to each other to inflate their rank, which is why ranking involves much more than this one matrix.

Examples and non-examples

The worked examples sit beside the ideas they practise, above. A few more.

A non-example: a vector that is stationary but not reached. For $P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ , the vector $(\tfrac12, \tfrac12)$ is stationary, and it is a probability vector. But $P^kx_0$ does not approach it from $x_0 = (1, 0)$ , because the eigenvalue $-1$ does not fade. “Stationary exists” and “the chain converges to it” are different statements.

A non-example: a matrix that is not stochastic. $\begin{bmatrix} 0.5 & 0.2 \\ 0.5 & 0.7 \end{bmatrix}$ has columns adding to $1$ and $0.9$ . After many steps the total chance leaks away, and the eigenvalues are not $1$ and a smaller number: the eigenvalue-1 theorem needs every column sum to be exactly $1$ .

Convergence is about the matrix, not the starting point. For the four-page web every starting probability vector leads to the same $\pi$ , because the hypotheses hold. The visualizer starts at page 1. Starting at page 3 changes the path and leaves the limit the same.

Where it is used

Used inside maths· Inside maths: random walks on graphs, and the stationary distribution given by the degrees

On an undirected graph, let a walker at a vertex move to a uniformly random neighbour. Take the graph with four vertices $A, B, C, D$ and edges $AB$ , $BC$ , $CA$ , $CD$ (a triangle with a tail). The degrees (numbers of edges at each vertex) are $2, 2, 3, 1$ , adding to $8$ , which is twice the number of edges. Claim: $\pi_v = \deg(v)/8$ , that is $\pi = (2, 2, 3, 1)/8$ , is stationary.

Proof for any such graph, with $m$ edges. The chance of going from $u$ to $v$ is $1/\deg(u)$ when $u, v$ are neighbours. So $(P\pi)_v = \sum_{u \sim v}\frac{1}{\deg u}\cdot\frac{\deg u}{2m} = \frac{\#\{u : u \sim v\}}{2m} = \frac{\deg v}{2m} = \pi_v$ . The factor $\deg u$ cancels, and the sum counts the neighbours of $v$ . So a walker visits a vertex in proportion to its degree. Check on the triangle with a tail: the second entry of $P\pi$ is $\tfrac12\cdot\tfrac28 + \tfrac13\cdot\tfrac38 = \tfrac18 + \tfrac18 = \tfrac28$ . This is the idea of the CS 240 graph chapters turned into linear algebra: the adjacency structure, scaled, is a stochastic matrix. (The chain on this graph has eigenvalues $1$ , $-\tfrac12$ and two others of size less than 1, so the walker’s chances settle.)

Used in the real world· PageRank: the 25 billion dollar eigenvector

The name PageRank plays on Larry Page’s surname as well as on “web page”. Bryan and Leise’s article (SIAM Review, 2006) is the standard mathematical account, and its title is where Spagnolie’s aside came from. The picture is the one in this chapter: the web is a directed graph, $P$ puts weight $1/\ell$ on each of a page’s $\ell$ links, $d = 0.85$ , and the ranking is the stationary vector of $G$ . Each page’s score is $\pi_i$ . A page with few but important links in beats a page with many obscure ones. In the worked example, page 3 had the most links in, and page 1 still came first because page 3, the most-linked page, passed its entire share to page 1.

The real computation: about 50 to 100 sparse matrix-vector products, each costing one operation per link. At $d = 0.85$ the bound $2d^k$ is below $10^{-3}$ by $k = 50$ whatever the size of the web, which is why the method scales to billions of pages. Search engines today combine PageRank-like scores with hundreds of other signals; the matrix described here is the original idea.

Used in the real world· Queueing: a shop with room for two customers

A tiny shop has room for two customers. Each minute, with chance $0.3$ one customer walks in (if there is room), or with chance $0.5$ one customer finishes and leaves (if anyone is there); otherwise nothing changes. The states are $0, 1, 2$ customers, and

P = \begin{bmatrix} 0.7 & 0.5 & 0 \\ 0.3 & 0.2 & 0.5 \\ 0 & 0.3 & 0.5 \end{bmatrix}.

Solving $P\pi = \pi$ : the first row gives $0.3\pi_0 = 0.5\pi_1$ , so $\pi_1 = 0.6\pi_0$ , and the last row gives $0.3\pi_1 = 0.5\pi_2$ , so $\pi_2 = 0.6\pi_1 = 0.36\pi_0$ . The total is $1.96\pi_0 = 1$ , so $\pi = (25, 15, 9)/49 \approx (0.51, 0.31, 0.18)$ . The shop is empty half the time and full about 18 percent of the time, and the owner can find out whether a second server is worth hiring by changing the numbers and re-solving. Telephone exchanges and computer networks are analysed with the same equations, and the weather model of the worked example is a two-state version.

Used in the real world· Generating text: the ancestor of language models (CS 532 and AI)

Take the text “the cat sat on the mat . the cat ate the fish .” and make each distinct token a state. Count how often each token follows each token and divide by the totals. The token “the” is followed by “cat” twice, “mat” once and “fish” once, so column “the” has $\tfrac12$ for cat, $\tfrac14$ for mat and $\tfrac14$ for fish. “cat” is followed by “sat” or “ate”, each with chance $\tfrac12$ . Every other token has one possible successor. Treating the text as a loop (the last ”.” leads back to “the”) makes the matrix stochastic, and its stationary distribution is exactly the word frequencies: “the” has $4/13$ , “cat” and ”.” have $2/13$ each, and the other five tokens have $1/13$ each. Walking the chain generates sentences like “the cat ate the mat .” that follow the statistics of the text, with no idea what they mean.

This is an n-gram model (here a bigram, the last 1 word). Claude Shannon showed text built this way in his 1948 paper on information theory. A modern language model, which predicts the next token from the last $N$ tokens of its context window, is a Markov chain too, formally a chain whose state is the whole window. The states are far too many to write as a matrix, and the transition chances come from a neural network rather than a table. The object (a state, a next-state distribution, a sequence) is still the one in this chapter.

Beyond the course: for understanding· Markov chain Monte Carlo (a mention)

Often you want random samples from a hard distribution $\pi$ (a Bayesian posterior over model weights, for example), and you cannot sample from it directly. The idea of Markov chain Monte Carlo is to build a chain whose stationary distribution is $\pi$ and run it for a long time. The Metropolis–Hastings algorithm constructs such a chain by accepting or rejecting random moves so that the “detailed balance” condition holds (see the stretch problem below). The convergence theory is the theory of this chapter: the chain must be regular, and its second eigenvalue sets how long the walk takes to forget its start.

Traps

Watch out· Columns add to 1, not rows

In this book $P_{ij}$ is the chance of going from $j$ to $i$ , so the COLUMNS add to 1 and the chances are a column vector multiplied on the right. In many probability textbooks it is the other way: rows add to 1 and the chances form a row vector multiplied on the left. If you copy a formula between books, transpose it. Checking the column sums is the first thing to do with any new matrix.

Watch out· Stationary does not mean the chain converges

$P\pi = \pi$ only says $\pi$ is unchanged by a step. The bouncing chain $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$ has a stationary vector $(\tfrac12, \tfrac12)$ and never approaches it. Convergence needs the other eigenvalues to have size less than 1, which is what regularity (or damping) gives.

Watch out· The eigenvector for 1 is of P, not of P-transpose

The proof that $1$ is an eigenvalue uses the vector $\mathbf 1$ , which is an eigenvector of $P^{\mathsf T}$ . It is not the stationary distribution. The stationary distribution is an eigenvector of $P$ itself, and it is not all ones (that would give every page the same rank). $P$ and $P^{\mathsf T}$ share eigenvalues, not eigenvectors.

Watch out· Do not forget to scale

Solving $(P - I)\pi = O$ gives a line of solutions, a null space. The stationary distribution is the one on that line whose entries add to 1. Writing $(2, 1)$ for the weather chain instead of $(\tfrac23, \tfrac13)$ is the most common slip.

Watch out· Eigenvalues can be complex

The three-page web has eigenvalues $\tfrac{-1 \pm i}{2}$ . The theorem $|\lambda| \le 1$ includes them, and this is why the proof uses the size of a complex number. Complex eigenvalues are what make the bars in the visualizer rise and fall as they settle instead of approaching monotonically.

Watch out· Damping changes the answer

The PageRank vector is the stationary distribution of $G$ , not of $P$ . They are different vectors (for the four pages, $(0.368, 0.142, 0.288, 0.202)$ against $(0.387, 0.129, 0.290, 0.194)$ ). The damped one is the ranking that is used in practice, and the small $1 - d$ share of random jumping is what makes it exist and be unique.

Problems

check

Is $\begin{bmatrix} 0.5 & 0.2 \\ 0.5 & 0.7 \end{bmatrix}$ stochastic? Is $\begin{bmatrix} 0.3 & 0.6 \\ 0.7 & 0.4 \end{bmatrix}$ ?

Solution

The first has column sums $1.0$ and $0.9$ , so it is not stochastic. The second has column sums $1.0$ and $1.0$ and no negative entries, so it is.

check

Three pages: page 1 links to page 2, page 2 links to pages 1 and 3, page 3 links to page 1. Write $P$ , and find the surfer’s chances after one step from page 2.

Solution

Column 1 is $(0, 1, 0)$ (one link, to page 2). Column 2 is $(\tfrac12, 0, \tfrac12)$ . Column 3 is $(1, 0, 0)$ . So $P = \begin{bmatrix} 0 & \tfrac12 & 1 \\ 1 & 0 & 0 \\ 0 & \tfrac12 & 0 \end{bmatrix}$ . Starting at $x_0 = (0, 1, 0)$ , $x_1 = Px_0$ is column 2: $(\tfrac12, 0, \tfrac12)$ .

check

Find the stationary distribution of $\begin{bmatrix} 0.9 & 0.5 \\ 0.1 & 0.5 \end{bmatrix}$ .

Solution

$(P - I)\pi = O$ gives $-0.1\pi_1 + 0.5\pi_2 = 0$ , so $\pi_1 = 5\pi_2$ . A basis vector is $(5, 1)$ ; scaled to add to $1$ , $\pi = (\tfrac56, \tfrac16)$ . Check: $0.9 \cdot \tfrac56 + 0.5 \cdot \tfrac16 = \tfrac{4.5 + 0.5}{6} = \tfrac56$ .

use

For $P = \begin{bmatrix} 0.7 & 0.2 \\ 0.3 & 0.8 \end{bmatrix}$ find the stationary distribution, the other eigenvalue, and a formula for $x_k$ starting from $x_0 = (1, 0)$ .

Solution

$(P - I)\pi = O$ gives $-0.3\pi_1 + 0.2\pi_2 = 0$ , so $\pi_2 = 1.5\pi_1$ ; the vector $(2, 3)$ scaled to sum $1$ is $\pi = (0.4, 0.6)$ . The trace is $1.5$ , so the other eigenvalue is $0.5$ , with eigenvector $(1, -1)$ (check: $P(1, -1) = (0.5, -0.5)$ ). Write $x_0 = (1, 0) = \pi + 0.6\,(1, -1)$ . Then $x_k = \pi + 0.6\,(0.5)^k(1, -1) = (0.4 + 0.6\cdot 0.5^k,\ 0.6 - 0.6\cdot 0.5^k)$ . Check $k = 1$ : $(0.7, 0.3)$ , the first column of $P$ .

use

A walker on the path with three vertices $1 - 2 - 3$ moves to a uniformly random neighbour. Write $P$ , find the stationary distribution, and say what happens to $P^kx_0$ from $x_0 = (1, 0, 0)$ .

Solution

Vertex 1 has one neighbour (2), vertex 2 has neighbours 1 and 3, vertex 3 has one neighbour (2). So $P = \begin{bmatrix} 0 & \tfrac12 & 0 \\ 1 & 0 & 1 \\ 0 & \tfrac12 & 0 \end{bmatrix}$ . By the degree rule the stationary distribution is $\pi = (1, 2, 1)/4$ ; check: row 1 of $P\pi$ is $\tfrac12 \cdot \tfrac24 = \tfrac14$ , row 2 is $\tfrac14 + \tfrac14 = \tfrac12$ . From $x_0 = (1, 0, 0)$ the walker alternates: $x_1 = (0, 1, 0)$ , $x_2 = (\tfrac12, 0, \tfrac12)$ , $x_3 = (0, 1, 0)$ , $x_4 = (\tfrac12, 0, \tfrac12)$ , and so on. It never settles because the graph is bipartite and the chain is periodic: the eigenvalues are $1, 0, -1$ , and the eigenvalue $-1$ has size $1$ .

use

Pages: 1 links to 2; 2 links to 1 and 3; 3 links to 1. Find the PageRank vector with $d = \tfrac12$ .

Solution

$P = \begin{bmatrix} 0 & \tfrac12 & 1 \\ 1 & 0 & 0 \\ 0 & \tfrac12 & 0 \end{bmatrix}$ and $\tfrac{1-d}{n} = \tfrac16$ . Solve $(I - \tfrac12P)\pi = \tfrac16\mathbf 1$ : $\pi_1 - \tfrac14\pi_2 - \tfrac12\pi_3 = \tfrac16$ , $\ \pi_2 - \tfrac12\pi_1 = \tfrac16$ , $\ \pi_3 - \tfrac14\pi_2 = \tfrac16$ . From the last two, $\pi_2 = \tfrac16 + \tfrac12\pi_1$ and $\pi_3 = \tfrac16 + \tfrac14\pi_2 = \tfrac16 + \tfrac1{24} + \tfrac18\pi_1 = \tfrac{5}{24} + \tfrac18\pi_1$ . The first equation then reads $\pi_1 - \tfrac1{24} - \tfrac18\pi_1 - \tfrac5{48} - \tfrac1{16}\pi_1 = \tfrac16$ , so $\tfrac{13}{16}\pi_1 = \tfrac16 + \tfrac1{24} + \tfrac5{48} = \tfrac{8 + 2 + 5}{48} = \tfrac{15}{48}$ , giving $\pi_1 = \tfrac{15}{48}\cdot\tfrac{16}{13} = \tfrac5{13}$ . Then $\pi_2 = \tfrac16 + \tfrac5{26} = \tfrac{13 + 15}{78} = \tfrac{14}{39}$ and $\pi_3 = \tfrac5{24} + \tfrac5{104} = \tfrac{65 + 15}{312} = \tfrac{10}{39}$ . So $\pi = (15, 14, 10)/39$ , which adds to $1$ . (Undamped, it is $(2, 2, 1)/5$ .)

prove

Prove that if $P$ is a stochastic matrix then $P^k$ is stochastic for every $k \ge 1$ . Then prove that for a probability vector $x$ and every $k$ , $\lVert P^kx \rVert_1 = 1$ .

Solution

For $k = 1$ this is the hypothesis. If $P^k$ is stochastic, then $P^{k+1} = P \cdot P^k$ is a product of two stochastic matrices, hence stochastic by the product theorem (the argument: its entries are sums of products of non-negative numbers, and its column sums are $\sum_i\sum_l P_{il}(P^k)_{lj} = \sum_l(P^k)_{lj}\sum_iP_{il} = \sum_l(P^k)_{lj} = 1$ ). By induction every $P^k$ is stochastic. For a probability vector $x$ , $P^kx$ is a probability vector by the theorem, and the 1-norm of a vector with non-negative entries is the sum of its entries, which is $1$ .

prove

Let $M$ be a square matrix whose rows (not columns) each add to $1$ . Prove that $1$ is an eigenvalue of $M$ , with eigenvector $\mathbf 1$ .

Solution

Entry $i$ of $M\mathbf 1$ is the sum of row $i$ of $M$ , which is $1$ . So $M\mathbf 1 = \mathbf 1$ and $\mathbf 1 \ne O$ , so $1$ is an eigenvalue with eigenvector $\mathbf 1$ . (This is the row-stochastic convention of probability textbooks; for our column-stochastic matrices the same eigenvector belongs to $P^{\mathsf T}$ , and the eigenvalue moves to $P$ through the characteristic polynomial.)

prove

Prove that for a stochastic matrix $P$ and a vector $x$ with all entries non-negative, $\lVert Px \rVert_1 = \lVert x \rVert_1$ . Where in the proof that $\lVert Px \rVert_1 \le \lVert x \rVert_1$ does the argument become an equality?

Solution

For $x \ge 0$ every entry of $Px$ is non-negative, so $\lVert Px \rVert_1$ is the sum of the entries of $Px$ , which is $\sum_j x_j\sum_iP_{ij} = \sum_jx_j = \lVert x \rVert_1$ . In the earlier proof the only inequality was the triangle inequality $|\sum_jP_{ij}x_j| \le \sum_jP_{ij}|x_j|$ , and when every $x_j \ge 0$ the terms $P_{ij}x_j$ are non-negative, so the absolute values change nothing and the inequality is an equality.

prove

Let $G = dP + \tfrac{1-d}{n}\mathbf 1\mathbf 1^{\mathsf T}$ with $P$ stochastic. Prove that for every probability vector $x$ , $Gx = dPx + \tfrac{1-d}{n}\mathbf 1$ , and that $Gx$ is a probability vector.

Solution

$Gx = dPx + \tfrac{1-d}{n}\mathbf 1(\mathbf 1^{\mathsf T}x)$ . For a probability vector $\mathbf 1^{\mathsf T}x = 1$ , so $Gx = dPx + \tfrac{1-d}{n}\mathbf 1$ . The entries are non-negative (a sum of non-negative terms). They add to $d \cdot 1 + n \cdot \tfrac{1-d}{n} = 1$ , using that $Px$ adds to $1$ . So $Gx$ is a probability vector. This is why one never needs to write the dense matrix $G$ .

stretchthe idea behind Metropolis–Hastings

Let $P$ be stochastic and $\pi$ a probability vector satisfying detailed balance: $P_{ij}\pi_j = P_{ji}\pi_i$ for all $i, j$ (the flow from $j$ to $i$ equals the flow from $i$ to $j$ ). Prove that $\pi$ is stationary. Use it to re-prove that $\pi_v = \deg(v)/2m$ is stationary for the random walk on a graph.

Solution

$(P\pi)_i = \sum_jP_{ij}\pi_j = \sum_jP_{ji}\pi_i = \pi_i\sum_jP_{ji}$ . The last sum is the total chance of leaving state $i$ for some state $j$ , which is column $i$ of $P$ added up: it equals $1$ . So $(P\pi)_i = \pi_i$ . For the graph walk, $P_{ij} = 1/\deg(j)$ when $i \sim j$ , and $P_{ij}\pi_j = \tfrac1{\deg j}\cdot\tfrac{\deg j}{2m} = \tfrac1{2m}$ , which is symmetric in $i$ and $j$ . So detailed balance holds (for non-neighbours both sides are $0$ ) and $\pi$ is stationary.

stretch

For the two-state chain $P = \begin{bmatrix} 1 - a & b \\ a & 1 - b \end{bmatrix}$ with $0 < a, b \le 1$ , find the stationary distribution, the other eigenvalue, and decide when $P^kx_0$ converges for every probability vector $x_0$ .

Solution

$(P - I)\pi = O$ gives $-a\pi_1 + b\pi_2 = 0$ , so $\pi \propto (b, a)$ and $\pi = \dfrac{(b, a)}{a + b}$ . The trace is $2 - a - b$ , so the other eigenvalue is $1 - a - b$ , with eigenvector $(1, -1)$ . Its size is less than $1$ exactly when $0 < a + b < 2$ . Since $a, b > 0$ the sum is positive, and $a + b = 2$ only for $a = b = 1$ , the bouncing chain, where the eigenvalue is $-1$ . So $P^kx_0 \to \pi$ for every $x_0$ unless $a = b = 1$ . (Check with the weather chain, $a = 0.2$ , $b = 0.4$ : $\pi = (0.4, 0.2)/0.6 = (\tfrac23, \tfrac13)$ and the other eigenvalue is $0.4$ .)

Summary

A Markov chain moves among states with fixed chances $P_{ij}$ (from $j$ to $i$ ). The chances of being in each state evolve by $x_{k+1} = Px_k$ .
A stochastic matrix has non-negative entries and columns adding to 1. It keeps probability vectors probability vectors, because the total of the entries of $Px$ is $\mathbf 1^{\mathsf T}Px = \mathbf 1^{\mathsf T}x$ .
A stationary distribution is a probability vector with $P\pi = \pi$ : an eigenvector for eigenvalue 1. Every stochastic matrix has eigenvalue 1 (because $P^{\mathsf T}\mathbf 1 = \mathbf 1$ and $P$ , $P^{\mathsf T}$ share eigenvalues) and no eigenvalue larger than 1 in size (the 1-norm never grows).
If the other eigenvalues have size less than 1, repeated steps kill their parts and $P^kx_0 \to \pi$ at the rate $|\lambda_2|^k$ . This holds for regular chains (Perron–Frobenius, stated here without proof). The power method computes $\pi$ using only matrix-times-vector.
The real web has dead ends, cycles, disconnected pieces and spider traps. Teleporting with chance $1 - d$ gives the Google matrix $G = dP + \tfrac{1-d}{n}\mathbf 1\mathbf 1^{\mathsf T}$ , with $d = 0.85$ .
For $G$ we proved everything: a unique $\pi$ with entries at least $\tfrac{1-d}{n}$ , error at most $2d^k$ from any start, and every other eigenvalue of size at most $d$ . The bound does not depend on the size of the web.
The four-page web has $\pi = (12, 4, 9, 6)/31$ undamped and about $(0.368, 0.142, 0.288, 0.202)$ at $d = 0.85$ . A random walk on an undirected graph has $\pi_v = \deg(v)/2m$ .
Text generated word by word from counts (an n-gram model) is a Markov chain, as is a language model on its context window; Markov chain Monte Carlo designs a chain with the stationary distribution you want.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture

The idea, in words

Definitions and theorems

Markov chain

Stochastic matrix

A stochastic matrix keeps probability vectors

Staying put: stationary distributions

Stationary distribution

One is always an eigenvalue of a stochastic matrix

Eigenvalues of a stochastic matrix have size at most one

Other eigenvectors have entries adding to zero

Does it settle? Convergence and the power method

Convergence for a diagonalizable chain with a simple eigenvalue 1

Power method

Perron–Frobenius theorem for regular chains

What goes wrong on the real web

Google matrix

The Google matrix has a unique stationary distribution

Examples and non-examples

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere