Markov Chains, PageRank & Path Counting

A Markov chain is a discrete process whose next state depends only on the current state, not on past history (Def.\ 7.8). The state is a probability distribution vector $x=[x_{1},\dots,x_{n}]^{T}$: every entry satisfies $0\le x_{i}\le 1$ and $x_{1}+\cdots+x_{n}=1$ (Def.\ 7.9), with $x_{i}$ the probability of being in state $i$. Any nonzero vector $v$ with nonnegative entries becomes a probability vector by normalizing -- dividing by its entry-sum (Rmk.\ 7.7): $x=\dfrac{v}{v_{1}+\cdots+v_{n}}$. For instance $v=[3,2,0,1]^{T}$ gives $x=\big[\tfrac12,\tfrac13,0,\tfrac16\big]^{T}$. The transition probabilities live in a transition matrix $A=[a_{ij}]$, where $a_{ij}$ is the probability of moving from state $j$ to state $i$ (note the reversed indices!). Since each column lists where a fixed source state $j$ can go, every column is itself a probability vector: $0\le a_{ij}\le 1$ and $\sum_{i}a_{ij}=1$ for each $j$. Such an $A$ is called column-stochastic.

The chain updates by the linear iteration $x(k+1)=Ax(k)$ with a fixed (time-independent) matrix $A$ -- that time-independence is exactly what makes it a Markov chain. Starting from a probability vector $x(0)$, the state after $k$ steps is $x(k)=A^{k}x(0)$. Proposition 7.3 keeps the model sensible: if $A$ is a transition matrix and $x$ a probability vector, then $Ax$ is again a probability vector. Hence every $x(k)$ is a probability vector -- a 'chain' of distributions describing the system over time. Moreover the entries of $A^{k}$ are the $k$-step transition probabilities: the $(i,j)$-entry of $A^{k}$ is the probability of going from state $j$ to state $i$ in exactly $k$ steps.

A transition matrix is positive if every entry is $>0$, and regular (eventually positive) if some power $A^{m}$ is positive (Def.\ 7.10). Regularity means that for some number of steps you can reach any state from any other with positive probability. For a regular $A$, the Perron--Frobenius theorem (Thm.\ 7.13) gives a unique probability vector $x^{*}$ with $Ax^{*}=x^{*}$ -- the equilibrium distribution, all of whose entries are strictly positive -- and $A^{m}x\to x^{*}$ for every starting distribution $x$. So $x^{*}$ is the (normalized) eigenvector for eigenvalue $\lambda=1$, and it is a globally stable equilibrium (Rmk.\ 7.8). To find it: solve the homogeneous system $(A-I)x^{*}=0$, then rescale the solution so its entries sum to $1$. Not every chain is regular -- the reflection $\begin{bmatrix}0&1\\1&0\end{bmatrix}$ has powers that only alternate between $A$ and $I$, so it never becomes positive and has no stable limit.

A directed graph (digraph) has vertices joined by arrows (edges). Its adjacency matrix $A=[a_{ij}]$ sets $a_{ij}=1$ when there is an edge from $v_{j}$ to $v_{i}$ and $0$ otherwise (Def.\ 7.11) -- again column $=$ source, row $=$ destination. An $r$-path from $v_{j}$ to $v_{i}$ is a sequence of $r$ consecutive directed edges leading from $v_{j}$ to $v_{i}$ (Def.\ 7.12); single edges are the $1$-paths counted by $A$ itself. The path-counting theorem (Thm.\ 7.14) says the $(i,j)$-entry of $A^{r}$ equals the number of distinct $r$-paths from $v_{j}$ to $v_{i}$. This is the same matrix-power idea as a Markov chain, except the entries count paths instead of carrying probabilities; replacing the $1$'s by transition probabilities turns the digraph into a Markov chain. A PageRank web graph (Ex.\ 7.17) is precisely such a weighted digraph.