Markov chains

A Markov chain is a discrete-time stochastic process: a process that occurs in a series of time-steps in each of which a random choice is made. A Markov chain consists of $N$ states. Each web page will correspond to a state in the Markov chain we will formulate.

A Markov chain is characterized by an $N \times N$ transition probability matrix $P$ each of whose entries is in the interval $[0,1]$; the entries in each row of $P$ add up to 1. The Markov chain can be in one of the $N$ states at any given time-step; then, the entry $P_{ij}$ tells us the probability that the state at the next time-step is $j$, conditioned on the current state being $i$. Each entry $P_{ij}$ is known as a transition probability and depends only on the current state $i$; this is known as the Markov property. Thus, by the Markov property,

$$\forall i,j, P_{ij}\in[0,1]$$ (251)

and

$$\forall i, \sum_{j=1}^N P_{ij}=1.$$ (252)

A matrix with non-negative entries that satisfies Equation 252 is known as a stochastic matrix . A key property of a stochastic matrix is that it has a principal left eigenvector corresponding to its largest eigenvalue, which is 1.

In a Markov chain, the probability distribution of next states for a Markov chain depends only on the current state, and not on how the Markov chain arrived at the current state. Figure 21.2 shows a simple Markov chain with three states. From the middle state A, we proceed with (equal) probabilities of 0.5 to either B or C. From either B or C, we proceed with probability 1 to A. The transition probability matrix of this Markov chain is then

$$\left( \begin{array}{ccc} 0 & 0.5 & 0.5 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ \end{array}\right)$$ (253)

Figure 21.2: A simple Markov chain with three states; the numbers on the links indicate the transition probabilities.

A Markov chain's probability distribution over its states may be viewed as a probability vector : a vector all of whose entries are in the interval $[0,1]$, and the entries add up to 1. An $N$-dimensional probability vector each of whose components corresponds to one of the $N$ states of a Markov chain can be viewed as a probability distribution over its states. For our simple Markov chain of Figure 21.2 , the probability vector would have 3 components that sum to 1.

We can view a random surfer on the web graph as a Markov chain, with one state for each web page, and each transition probability representing the probability of moving from one web page to another. The teleport operation contributes to these transition probabilities. The adjacency matrix $A$ of the web graph is defined as follows: if there is a hyperlink from page $i$ to page $j$, then $A_{ij}=1$, otherwise $A_{ij}=0$. We can readily derive the transition probability matrix $P$ for our Markov chain from the $N \times N$ matrix $A$:

1. If a row of $A$ has no 1's, then replace each element by 1/N. For all other rows proceed as follows.
2. Divide each 1 in $A$ by the number of 1's in its row. Thus, if there is a row with three 1's, then each of them is replaced by $1/3$.
3. Multiply the resulting matrix by $1-\alpha$.
4. Add $\alpha/N$ to every entry of the resulting matrix, to obtain $P$.

We can depict the probability distribution of the surfer's position at any time by a probability vector $\vec{x}$. At $t=0$ the surfer may begin at a state whose corresponding entry in $\vec{x}$ is 1 while all others are zero. By definition, the surfer's distribution at $t=1$ is given by the probability vector $\vec{x}P$; at $t=2$ by $(\vec{x}P)P=\vec{x}P^2$, and so on. We will detail this process in Section 21.2.2 . We can thus compute the surfer's distribution over the states at any time, given only the initial distribution and the transition probability matrix $P$.

If a Markov chain is allowed to run for many time steps, each state is visited at a (different) frequency that depends on the structure of the Markov chain. In our running analogy, the surfer visits certain web pages (say, popular news home pages) more often than other pages. We now make this intuition precise, establishing conditions under which such the visit frequency converges to fixed, steady-state quantity. Following this, we set the PageRank of each node $v$ to this steady-state visit frequency and show how it can be computed.