# Transition matrix calculation from text book "Introduction to information retrieval"

According to the example on page in the text book, the graph of documents is as follows:
$1\rightarrow2, 3\rightarrow2, 2\rightarrow1, 2\rightarrow3$
with $\lambda = 0.5$ which would form an adjacency matrix as follows:

Then if we multiply the $\lambda$ by $$A = \begin{bmatrix} 0&1 &0 \\ 1&0 &1 \\ 0&1 &0 \end{bmatrix}$$ we would get a matrix:

$$A = \begin{bmatrix} 0&1/2 &0 \\ 1/2&0 &1/2 \\ 0&1/2 &0 \end{bmatrix}$$

Now if we add $\frac{1 - \lambda}{N}$ to the matrix A, we would get a transition matrix
$$P = \begin{bmatrix} 1/6&2/3 &1/6 \\ 2/3&1/6 &2/3 \\ 1/6&2/3 &1/6 \end{bmatrix}$$ According to the book, the transition probability matrix of surfer's walk with teleportation is: $$P = \begin{bmatrix} 1/6&2/3 &1/6 \\ 5/12&1/6 &5/12 \\ 1/6&2/3 &1/6 \end{bmatrix}$$

• Dividing each 1 in A by the number of 1s in its row.
• Multiply the resulting matrix by $1 - \lambda$
• Add $\frac{\lambda}{N}$

My transition matrix and one form book are a bit different. What are the calculations behind the books matrix?

We assign each outgoing link of node 2, a probability of $0.5$ since each link has an equal chance of the emission. In simple words, we assign $\frac{1}{L}$ to each outgoing link of the particular node, where $L$ is the number of outgoing links of that node. The matrix $A$ would look something like:
$$A = \begin{bmatrix} 0 & 1 &0 \\ 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \end{bmatrix}$$ This would give the correct answer.
• See also (right) stochastic matrix: row sums should be one. (Since $P_{ij}=\Pr[i\to{j}]$, and each $i$ must go somewhere then $\sum_jP_{ij}=1$.) Dec 19 '16 at 14:59