Suppose that there are web pages. A user staying at a web page at time () will move to one of the linked pages at time with equal probability. If there are no linked pages, the user will stay at the same page as time . Let () denote the probability of the user staying at the -th page at time , and denote the vector that summarizes them.
First, let us consider the case of shown in Table 1. When there are three web pages shown in Table 1, the state transition diagram that represents a user's state is depicted as a graph in Figure 1. Each node in the graph shown in Figure 1 corresponds one-to-one to a page in Table 1, and an edge represents a transition between the pages from time to time . The value appended to an edge shows the probability of the transition occurring. Note that when there are no linked pages and a user keeps staying at the same page, it is interpreted as a transition to the same page as time .
Answer the following questions.
(1) Given , find and .
(2) Represent and using . is the same as in Question (1).
(3) Find when . is the same as in Question (1).
Next, we introduce an operation called "jump" that occurs during a move between pages from time to time with a constant probability . When a jump occurs, the user moves to one of pages (including the current page) with equal probability. When a jump does not occur, the user moves to one of the linked pages with equal probability in the same manner as before (if there are no linked pages, the user will keep staying at the current page).
(4) We introduce the jump operation into the case in Table 1. Suppose that . Draw a state transition diagram for this case. Also, find the transition probability matrix that satisfies the following equation
(5) When , this is called a stationary distribution. Find the stationary distribution in the case of Question (4).
Finally, we consider the transition probability matrix and stationary distribution of a general case where the jump operation is introduced. For answering the following questions, you can use the Perron–Frobenius theorem described below.
Perron–Frobenius theorem for positive matrices
A positive square matrix has a positive eigenvalue that satisfies the following. Here, a positive matrix is a matrix whose elements are all positive real numbers.
(i) For the absolute value of an arbitrary eigenvalue other than , holds.
(ii) The eigenvalue is a simple root (i.e., has the multiplicity of 1), and there exists a positive eigenvector that belongs to the eigenvalue . Here, a positive vector is a vector whose elements are all positive real numbers.
(iii) There are no positive eigenvectors that belong to eigenvalues other than .
(6) Show that , the transpose of , has 1 as an eigenvalue, and that this is the eigenvalue with the largest absolute value.
(7) Show that a stationary distribution exists uniquely. Here, you can assume the following fact as given; In general, a square matrix and its transpose have the same set of eigenvalues.
(8) Show that, by iteratively computing following the equation , regardless of the initial probability distribution , converges to the stationary distribution when . You can assume that can be represented as a linear combination of eigenvectors, . Here, denotes the -th eigenvalue of while is its coefficient.
