Some processes forget their past. Where a bike is tomorrow depends only on where it is today; which page a web surfer visits next depends only on the page they're on. Collect the chances into a matrix $P$ and the chances of being in each place into a vector $x_k$, and one step of the process is $x_{k+1} = Px_k$. This page asks where that goes in the long run, and the answer turns out to be an eigenvector for the eigenvalue $1$. The same idea, run on the whole web, is how Google first ranked pages.
A bike-share has three stations, and every day riders carry the bikes around. Track the share of bikes at each station, and you get three numbers that add up to $1$: a point on a triangle in space. Each day the point hops to a new spot on that triangle. This page watches where it ends up, and the place it ends up is an eigenvector you can see.
On Matrix Powers & Recurrences, populations grew by $x_{k+1} = Ax_k$ and the dominant eigenvalue decided the long run. Here nothing is born and nothing dies: things just move around. So the total never changes, and the winning eigenvalue is exactly $1$.
Start with every bike at station A, or every bike at station C: ten days later the stations hold $80$, $50$, and $70$ bikes either way (to the nearest bike). The rest of the page explains why the start stops mattering, and how to find those numbers without running the days.
Hefferon tells the story of a wildlife reserve with no fence. Every year $10\%$ of the animals in the park wander out, and $1\%$ of the animals outside wander in. Nothing else happens: the animals only move. Two kinds of numbers describe this, and each gets a name.
A probability vector is a vector whose entries are all $\ge 0$ and add up to $1$.
The park's shares are one: $20\%$ of the animals inside and $80\%$ outside make the probability vector $(0.2, 0.8)$. The chances of moving get collected the same way, one column per place.
A square matrix $P$ is stochastic (a transition matrix) if all of its entries are $\ge 0$ and each of its columns adds up to $1$. In other words, every column of $P$ is a probability vector.
The two go together: column $j$ of $P$ lists where whatever is in state $j$ goes next, so it adds up to $1$, and the vector $x_k$ lists the chance of being in each state, so it does too.
The park holds $110{,}000$ animals in all, $22{,}000$ inside the park and $88{,}000$ outside. Write the move as $x_{k+1} = Px_k$ and find next year's counts.
Take state $1$ to be "in the park" and state $2$ "outside". Of the animals in the park, $90\%$ stay and $10\%$ leave: that's column $1$. Of those outside, $1\%$ come in and $99\%$ stay: column $2$.
$$P = \begin{pmatrix} 0.9 & 0.01 \\ 0.1 & 0.99 \end{pmatrix}, \qquad Px_0 = \begin{pmatrix} 0.9(22{,}000) + 0.01(88{,}000) \\ 0.1(22{,}000) + 0.99(88{,}000) \end{pmatrix} = \begin{pmatrix} 20{,}680 \\ 89{,}320 \end{pmatrix}.$$The total is still $110{,}000$. Counts or shares both work: dividing by $110{,}000$ turns $x_0$ into the probability vector $(0.2, 0.8)$, and then $x_1 = (0.188, 0.812)$.
As shares, the two numbers add up to $1$, so the state is a point on the line segment from $(1, 0)$ (every animal in the park) to $(0, 1)$ (every animal outside). Here it is, year after year.
A process run by a stochastic matrix like this one gets a name.
A Markov chain with states $1, \ldots, n$ is a sequence of probability vectors $x_0, x_1, x_2, \ldots$ with $x_{k+1} = Px_k$ for an $n \times n$ stochastic matrix $P$. Entry $i$ of $x_k$ is the chance of being in state $i$ after $k$ steps, and $P_{ij}$ is the chance of moving to state $i$ from state $j$ in one step.
Read $P_{ij}$ as "to $i$, from $j$". That order is what makes $x_{k+1} = Px_k$ come out right: entry $i$ of $Px_k$ is row $i$ of $P$ times $x_k$, which adds up everything arriving at state $i$.
The total stayed put, and it always will. That's worth stating once, because everything on this page leans on it.
If $P$ is stochastic and $x$ is a probability vector, then $Px$ is a probability vector. So every $x_k$ in a Markov chain is a probability vector, and every power $P^k$ is stochastic.
Each entry $(Px)_i = \sum_j P_{ij}x_j$ is a sum of products of numbers $\ge 0$, so it is $\ge 0$. Adding up the entries and swapping the order of the sums,
$$\sum_i (Px)_i = \sum_j x_j\Big(\sum_i P_{ij}\Big) = \sum_j x_j \cdot 1 = 1.$$So $Px$ is a probability vector, and by induction so is every $x_k = Px_{k-1}$. For $P^k$: column $j$ of $P^k$ is $P^k e_j$, and $e_j$ is a probability vector, so each column of $P^k$ is one. $\blacksquare$
This is a visual argument, not a formal proof. In space, the probability vectors with three entries are exactly the points of the triangle with corners $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$: all entries $\ge 0$ on the plane $x + y + z = 1$. Each column of $P$ is one of those points. And
$$Px = x_1(\text{column } 1) + x_2(\text{column } 2) + x_3(\text{column } 3)$$is a weighted average of the three column points, with weights $\ge 0$ that add up to $1$. A weighted average of points always lands inside the triangle they make (think of a balance point), and that triangle sits inside the big one. Here it is with the bike-share matrix from the opening picture.
The full proof is in the n version.
Now three states. Here is the bike-share from the opening picture.
Each day, of the bikes at station A, $70\%$ stay, $10\%$ end up at B, and $20\%$ at C. Of the bikes at B, $20\%$ go to A, $70\%$ stay, and $10\%$ go to C. Of the bikes at C, $20\%$ go to A, $10\%$ to B, and $70\%$ stay. Today there are $60$ bikes at A, $100$ at B, and $40$ at C. How many are at each station tomorrow?
Each station's percents make one column:
$$P = \begin{pmatrix} 0.7 & 0.2 & 0.2 \\ 0.1 & 0.7 & 0.1 \\ 0.2 & 0.1 & 0.7 \end{pmatrix}, \qquad P\begin{pmatrix} 60 \\ 100 \\ 40 \end{pmatrix} = \begin{pmatrix} 42 + 20 + 8 \\ 6 + 70 + 4 \\ 12 + 10 + 28 \end{pmatrix} = \begin{pmatrix} 70 \\ 80 \\ 50 \end{pmatrix}.$$Row $1$ collects the bikes that end up at A: $42$ stayed, $20$ came from B, $8$ came from C. Still $200$ bikes.
Notice which way the percents went into $P$.
The classic slip is reading $P$ sideways. The percents for one station go down a column, because a column is "from here". If your rows add up to $1$ and your columns don't, you've built the transpose. (Many statistics books do use rows, with $x$ written as a row vector on the left: $x_{k+1} = x_kP$. Same chain, everything transposed.)
Your turn: run a chain for a step or two. In free response, type the entries in order, split by commas, like 70, 80, 50.
Loading practice engine...
If the chain ever settles down, it settles at a vector that $P$ doesn't change: $Pq = q$. That is an eigenvector for the eigenvalue $1$. The good news is that a stochastic matrix always has that eigenvalue, and nothing bigger.
Every stochastic matrix $P$ has $1$ as an eigenvalue, and every eigenvalue $\lambda$ of $P$ (real or complex) has $|\lambda| \le 1$.
Each column of $P - I$ adds up to $1 - 1 = 0$, so the rows of $P - I$ add up to the zero row: they are linearly dependent. By the Invertible Matrix Theorem (items (9) and (2)), $\det(P - I) = 0$, so $1$ is an eigenvalue (eigenvalues and determinants).
For the bound, let $Pv = \lambda v$ with $v \neq 0$ (complex entries allowed). For any vector $y$,
$$\sum_i |(Py)_i| = \sum_i \Big|\sum_j P_{ij}y_j\Big| \le \sum_j |y_j| \sum_i P_{ij} = \sum_j |y_j|,$$by the triangle inequality and because the columns add up to $1$. With $y = v$ the left side is $|\lambda|\sum_i |v_i|$, so $|\lambda| \le 1$. $\blacksquare$
This is a visual argument in two parts, not a formal proof. First, why $1$ is an eigenvalue. Each column of $P$ adds up to $1$, so each column of $P - I$ adds up to $0$. Every arrow whose entries add up to $0$ lies in one plane through the origin, the plane $x + y + z = 0$. So the three columns of $P - I$ lie in one plane, and $P - I$ squashes space flat: $\det(P - I) = 0$, which is exactly what makes $1$ an eigenvalue.
Second, why no eigenvalue is bigger than $1$ in size. Think of each entry of a vector as a pile, positive or negative. Multiplying by $P$ splits each pile into pieces, by the percents in its column, and sends the pieces to the stations. The pieces of one pile add up to the pile itself, so nothing is created. But a positive piece and a negative piece landing at the same station cancel, so the total size of the piles can only shrink. If $Pv = \lambda v$, the total size gets multiplied by $|\lambda|$, so $|\lambda| \le 1$.
The full proof is in the n version.
An eigenvector for $1$ can be scaled any way you like. The one that matters is scaled to be a probability vector.
A steady-state vector of a stochastic matrix $P$ is a probability vector $q$ with $Pq = q$: an eigenvector for the eigenvalue $1$, scaled so its entries add up to $1$.
Start a chain at $q$ and it never moves. Back to the park.
Find the steady state of the park, $P = \begin{pmatrix} 0.9 & 0.01 \\ 0.1 & 0.99 \end{pmatrix}$, and the counts it means for $110{,}000$ animals.
$(P - I)q = 0$ reads $-0.1q_1 + 0.01q_2 = 0$ (the second row says the same thing, times $-1$). So $q_2 = 10q_1$, and with $q_1 + q_2 = 1$, $q = \left(\frac{1}{11}, \frac{10}{11}\right)$. That's $10{,}000$ animals in the park and $100{,}000$ outside.
Check it the way Hefferon does: each year $10\%$ of $10{,}000$ leave and $1\%$ of $100{,}000$ arrive. A thousand each way, so nothing changes.
Three states take one more equation, and a trick saves work.
The equations of $(P - I)q = 0$ always include one extra: their rows add up to zero, so any one of them follows from the others. Throw one away and use "the entries add up to $1$" in its place. That gives a system with exactly one solution.
Here's the trick on the bike-share.
Find the steady state of the bike-share and the number of bikes it means at each station.
The first two rows of $(P - I)q = 0$, plus the sum:
$$-0.3q_1 + 0.2q_2 + 0.2q_3 = 0, \qquad 0.1q_1 - 0.3q_2 + 0.1q_3 = 0, \qquad q_1 + q_2 + q_3 = 1.$$The second equation says $q_1 + q_3 = 3q_2$; put it in the sum, and $4q_2 = 1$, so $q_2 = 0.25$. Then $q_1 + q_3 = 0.75$, and the first equation says $0.3q_1 = 0.2(q_2 + q_3) = 0.2(1 - q_1)$, so $q_1 = 0.4$ and $q_3 = 0.35$:
$$q = (0.4, \ 0.25, \ 0.35).$$With $200$ bikes, that's $80$ at A, $50$ at B, and $70$ at C: the numbers the opening picture settled on. Check one: $Pq$ has first entry $0.28 + 0.05 + 0.07 = 0.4$.
On the triangle, $q$ is a single point. The next section shows every start walking to it.
Your turn. In free response, type the entries in order, split by commas; fractions like 1/3 are fine.
Loading practice engine...
Having a steady state doesn't mean the chain gets there. The swap $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ has steady state $\left(\frac12, \frac12\right)$, yet from $(1, 0)$ it flips to $(0, 1)$ and back forever. What rules that out is a little mixing.
A stochastic matrix $P$ is regular if some power $P^k$ has every entry $> 0$.
So after $k$ steps, every state can reach every state. The bike-share is regular with $k = 1$: no entry of $P$ is $0$. The swap is not, since its powers just alternate between the swap and $I$.
If $P$ is a regular stochastic matrix, then $P$ has exactly one steady-state vector $q$, every entry of $q$ is $> 0$, and for every probability vector $x_0$,
$$x_k = P^kx_0 \to q \quad \text{as } k \to \infty.$$Write $|y|_+ = \sum_i |y_i|$ for the total size of a vector (just for this proof). The proof above showed $|Py|_+ \le |y|_+$ for every stochastic $P$.
Step 1: a stochastic matrix $M$ with every entry $\ge m > 0$ shrinks vectors whose entries add up to $0$. If $\sum_j y_j = 0$, then $\sum_j m\,y_j = 0$ too, so $(My)_i = \sum_j (M_{ij} - m)y_j$, and the numbers $M_{ij} - m$ are $\ge 0$ with column sums $1 - nm$. As before,
$$|My|_+ \le \sum_j |y_j| \sum_i (M_{ij} - m) = (1 - nm)\,|y|_+ .$$Call $c = 1 - nm$; then $0 \le c < 1$.
Step 2: the chain converges. Let $P^r$ have every entry $> 0$, with smallest entry $m$, and apply Step 1 to $M = P^r$. The vector $y = x_1 - x_0$ has entries adding up to $1 - 1 = 0$, and so does every $P^jy = x_{j+1} - x_j$. Since $P$ never increases $|\cdot|_+$ and $P^r$ multiplies it by at most $c$,
$$|x_{j+1} - x_j|_+ = |P^jy|_+ \le c^{\lfloor j/r \rfloor}|y|_+ \le 2c^{\lfloor j/r \rfloor}.$$These bounds add up to a finite number (a geometric series, $r$ terms per power of $c$). So in each entry, $x_k = x_0 + \sum_{j < k}(x_{j+1} - x_j)$ is a series whose terms are bounded by a convergent geometric series, and $x_k$ converges to some vector $q$. Each $x_k$ is a probability vector, so $q$ is one too, and $Pq = \lim Px_k = \lim x_{k+1} = q$.
Step 3: there is only one, and it is positive. If $q'$ is another steady-state vector, then $q - q'$ has entries adding up to $0$, so $|q - q'|_+ = |P^{rk}(q - q')|_+ \le c^k|q - q'|_+ \to 0$, and $q' = q$. So every start converges to the same $q$. Finally $q = P^rq$, and each entry of $P^rq$ is a sum of positive numbers times entries of $q$ that are $\ge 0$ and not all $0$, so it is $> 0$. $\blacksquare$
This is a visual argument, not a formal proof. Every start is a point of the big triangle $T$. After one step, the picture above says every point has landed in the smaller triangle $PT$ whose corners are the columns of $P$. After two steps, every point is in $P(PT)$, whose corners are the columns of $P^2$, smaller still. When every entry of $P$ is positive, each triangle sits strictly inside the one before. Watch them shrink.
The steady state $q$ is in every one of these triangles (it never moves), and every start is trapped in them too. The picture shows the triangles closing in on one point; that they shrink all the way down, and don't stall at some small size, is the part a picture can't measure. The full proof is in the n version, and it measures exactly that.
When $P$ has a basis of eigenvectors, the powers theorem shows the convergence happening, and how fast. Here $1$ is the dominant eigenvalue, and the long-run theorem says the iterates line up with its eigenvector, at a growth factor of exactly $1$: no growth at all.
The bike-share's other eigenvalues are $0.6$ and $0.5$, with eigenvectors $v_2 = (0, 1, -1)$ and $v_3 = (1, 0, -1)$. Starting from $x_0 = (0.3, 0.5, 0.2)$ (the $60$, $100$, $40$ bikes), write $x_k$ exactly.
Check one eigenvector: $Pv_2 = (0.2 - 0.2, \ 0.7 - 0.1, \ 0.1 - 0.7) = (0, 0.6, -0.6) = 0.6v_2$. Notice the entries of $v_2$ and $v_3$ add up to $0$. That always happens for an eigenvalue $\lambda \ne 1$, because $P$ keeps the total: the total of $Pv$ is the total of $v$, and also $\lambda$ times it, so the total is $0$.
So split $x_0$ as $q$ plus a piece whose entries add up to $0$: $x_0 - q = (-0.1, 0.25, -0.15) = 0.25v_2 - 0.1v_3$. By the powers theorem,
$$x_k = q + 0.25(0.6)^kv_2 - 0.1(0.5)^kv_3.$$The coefficient of $q$ is exactly $1$, whatever the start: the other pieces add up to $0$, and $x_k$ has to add up to $1$. The leftover pieces shrink by $0.6$ and $0.5$ a day. After a week, $0.25(0.6)^7 \approx 0.007$ and $0.1(0.5)^7 \approx 0.001$: out of $200$ bikes, every station is within $2$ bikes of the steady state.
Both eigenvectors lie along edges' directions of the triangle, so the two leftover pieces are short arrows on the triangle, shrinking toward $q$.
So the second-biggest eigenvalue, by size, sets the speed: the closer it is to $1$, the slower the chain forgets its start. The park's other eigenvalue is $0.89$ (Hefferon finds it too), so its gap from the steady state shrinks by only $11\%$ a year.
The chain forgets where it started. Every bike, every surfer, every animal. Give it a week and the past is gone. Honestly, relatable.
Two states are enough to see all of this. Set the two chances of switching and watch the shares.
With $P = \begin{pmatrix} 1 - a & b \\ a & 1 - b \end{pmatrix}$, the steady state is $\frac{1}{a + b}(b, a)$ and the other eigenvalue is $1 - a - b$. When that eigenvalue is $0$ the chain settles in one step; when it is $-1$ ($a = b = 1$, the swap) it never settles.
Some chains aren't regular on purpose: they have states you can't leave.
A state $j$ of a Markov chain is absorbing if $P_{jj} = 1$: once the chain is there, it stays there. Column $j$ of $P$ is then $e_j$.
A gambler's bankroll is the classic example: going broke ends the game for good.
This example has six states, so it steps past what the triangle can draw. That's on purpose: a game needs room to wander. The bars below draw it instead.
Hefferon's coin game: a player bets a dollar on each coin flip and stops at $\$0$ (broke) or $\$5$ (goal). The states are the amounts $\$0, \ldots, \$5$, and $\$0$ and $\$5$ are absorbing. Starting with $\$3$, what is the chance of reaching $\$5$?
From $\$1$ through $\$4$, the money goes up or down a dollar, each with chance $\frac12$. Running the chain from $x_0 = e_3$ (state $\$3$) piles the chance up at the two ends: after $24$ flips Hefferon's table has about $0.396$ at $\$0$ and $0.597$ at $\$5$, with almost nothing left in the middle.
For the exact answer, look at the row $r = (0, 1, 2, 3, 4, 5)$, the dollar amounts. Then $rP = r$: in column $j$ of $P$, the average amount the player has next is $\frac12(j - 1) + \frac12(j + 1) = j$ for a middle state, and $j$ itself for the two ends. So $r x_k = r(P x_{k-1}) = r x_{k-1}$: the expected amount of money never changes. It starts at $\$3$. In the long run all the chance sits at $\$0$ and $\$5$, so if $p$ is the chance of reaching $\$5$, $5p = 3$:
$$p = \frac35.$$Here is the chain running, flip by flip, with the expected money underneath.
An absorbing chain has more than one steady state (sitting at $\$0$ forever, sitting at $\$5$ forever, and every mix of the two), and where it ends up depends on where it starts. Both are exactly what the convergence theorem rules out for regular chains.
How should a search engine decide which pages matter? Google's founders proposed that a page is important if important pages link to it. That sounds circular, but it's an eigenvector problem. Picture a surfer who clicks a random link on every page they visit. In the long run, the share of time they spend on each page is that page's rank.
The link matrix $H$ of a web of $n$ pages has column $j$ split evenly over the pages that page $j$ links to: $H_{ij} = 1/(\text{number of links on page } j)$ if page $j$ links to page $i$, and $0$ otherwise. A page with no links (a dangling page) gets a column of $1/n$'s instead: the surfer jumps anywhere.
So $H$ is stochastic, and the surfer is a Markov chain. Each page splits its own rank evenly among its links, which is why a link from an important page with few links counts for a lot.
A web has three pages: page $1$ links to pages $2$ and $3$, page $2$ links to page $3$, and page $3$ links to page $1$. Find the PageRank (the steady state of $H$).
Page $1$'s vote splits in half, the others go whole:
$$H = \begin{pmatrix} 0 & 0 & 1 \\ \frac12 & 0 & 0 \\ \frac12 & 1 & 0 \end{pmatrix}.$$$Hq = q$ says $q_1 = q_3$ and $q_2 = \frac12q_1$. With the entries adding up to $1$, $q = (0.4, 0.2, 0.4)$. Page $3$ collects two links and ties with page $1$, which gets only one: but that one link carries all of page $3$'s rank. $H$ is regular ($H^5$ is the first power with every entry positive: by then every page can reach every page in exactly $5$ clicks, mixing the $2$-click loop $1 \to 3 \to 1$ with the $3$-click loop $1 \to 2 \to 3 \to 1$), so the surfer really does settle here.
Watch the rank flow along the links until it settles, then watch what damping (coming up next) does to it.
A dangling page changes $H$, but not the method.
Hefferon's four-page web: page $1$ links to $2$; page $2$ links to $3$; page $3$ links to $1$, $2$, and $4$; page $4$ has no links. Find the PageRank.
Solving $Hq = q$ gives a multiple of $(1, 2, \frac94, 1)$, as Hefferon finds. Scaled to add up to $1$ (he scales it to length $1$ instead; the ranking is the same), $q = (0.16, 0.32, 0.36, 0.16)$. Pages $2$ and $3$ are the important ones.
Change the web so page $3$ has no links: page $1$ links to $2$ and $3$, page $2$ links to $3$, and page $3$ is dangling. Find the PageRank.
$Hq = q$ says $q_1 = \frac13q_3$ and $q_2 = \frac12q_1 + \frac13q_3$. Take $q_3 = 3$: then $q_1 = 1$ and $q_2 = 1.5$, which add up to $5.5$. So $q = \left(\frac{2}{11}, \frac{3}{11}, \frac{6}{11}\right)$. Page $3$ still wins: everything flows into it, and the jump spreads its rank back out evenly.
Real webs have pages that trap the surfer (a group of pages that only link to each other) and $H$ is far from regular. Google's fix is to let the surfer get bored.
For a web of $n$ pages with link matrix $H$ and a damping factor $\alpha$ with $0 < \alpha < 1$, the Google matrix is $G = \alpha H + (1 - \alpha)S$, where every entry of $S$ is $1/n$. The PageRank vector is the steady-state vector of $G$.
With chance $\alpha$ the surfer follows a link, and otherwise jumps to a page picked at random. Hefferon reports that $\alpha$ is usually between $0.85$ and $0.99$.
For $0 < \alpha < 1$, the Google matrix $G$ is stochastic and every entry of $G$ is at least $\frac{1 - \alpha}{n} > 0$. So $G$ is regular, and it has exactly one PageRank vector, which every start converges to.
Each column of $G$ is $\alpha$ times a column of $H$ plus $1 - \alpha$ times a column of $S$; both columns add up to $1$, so this one adds up to $\alpha + (1 - \alpha) = 1$. Every entry is $\alpha H_{ij} + \frac{1 - \alpha}{n} \ge \frac{1 - \alpha}{n} > 0$. So $G$ is regular with $k = 1$, and the convergence theorem does the rest. $\blacksquare$
Damping changes the numbers a little, and sometimes the order.
Find the PageRank of the three-page web above ($1 \to 2, 3$; $2 \to 3$; $3 \to 1$) with $\alpha = 0.85$.
If the entries of $q$ add up to $1$, then $Sq = \left(\frac13, \frac13, \frac13\right)$, so $Gq = q$ becomes $q = 0.85Hq + (0.05, 0.05, 0.05)$:
$$q_1 = 0.05 + 0.85q_3, \qquad q_2 = 0.05 + 0.425q_1, \qquad q_3 = 0.05 + 0.425q_1 + 0.85q_2.$$Solving, $q \approx (0.388, \ 0.215, \ 0.397)$. Page $3$ now edges out page $1$. Page $1$'s rank all comes through one link, from page $3$, and damping takes $15\%$ off it; page $3$ is fed by two pages, and the random jumps spread rank toward the page with less (page $2$).
On the triangle, damping slides every column of $H$ $15\%$ of the way to the center, so the triangle of columns moves off the edges and every entry turns positive.
The real web has billions of pages, so nobody solves $Gq = q$ by elimination. Instead, start anywhere and multiply by $G$ again and again: this page's convergence theorem says that walks to the PageRank. That's the power method, a later page, and it is how the ranking was actually computed.
Now build a web yourself. Click an arrow to switch that link on or off, and watch the ranks.
Your turn, without damping. In free response, type the ranks in order, split by commas, like 2/5, 1/5, 2/5 (or one number when it asks for one page).
Loading practice engine...
The toolkit for this page: a Markov chain is $x_{k+1} = Px_k$ with $P$'s columns adding up to $1$, and $P$ keeps every probability vector a probability vector. $1$ is always an eigenvalue, nothing is bigger in size, and its eigenvector scaled to add up to $1$ is the steady state. If $P$ is regular, every start walks to that one steady state, at a speed set by the next eigenvalue. PageRank is the steady state of the surfer's chain, made regular by damping.
Every question so far came right after its idea, which is a hint a quiz never gives you. Down here the hint is gone. First, true or false: a claim from anywhere on this page, and you decide whether it holds.
Loading practice engine...
Next, a mixed set: every question type on this page, shuffled. Type the entries split by commas when it asks you to.
Loading practice engine...
Made it this far? Time for something with a little heat: PageRank with damping, worked out exactly. In free response, type one number; fractions like 13/23 are fine.
Loading practice engine...