Question 7.4.1: As in Example 9 of Section 2.1, consider a “mini-Web” with o......
As in Example 9 of Section 2.1, consider a “mini-Web” with only three pages, labeled 1, 2, and 3. Initially there is an equal number of surfers on each page, meaning that the initial distribution vector is
\vec{x}_0=\begin{bmatrix}1/3\\1/3\\1/3\end{bmatrix}.
At the blow of a whistle, some surfers will move on to a different page, in a way described by the transition matrix
A=\begin{bmatrix}0.7&0.1&0.2\\0.2&0.4&0.2\\0.1&0.5&0.6\end{bmatrix}.
For example, the entries of the first column of A tell us that 20% of those who are initially on Page 1 will move to Page 2, while 10% will move to Page 3 and 70% will stay on Page 1. (These are not the rules of transition we considered when defining PageRank.)
We can represent the rules of transition in a diagram:
After one transition, the distribution of the surfers will be
A\vec{x}_0=\begin{bmatrix}1/3\\4/15\\2/5\end{bmatrix}≈\begin{bmatrix}0.333\\0.267\\0.4\end{bmatrix}.
If we iterate this transition t times, the final distribution will be A^t\vec{x}_0.
a. Find a closed formula for A^t\vec{x}_0, expressing the vector A^t\vec{x}_0 as a function of t.
b. What happens in the long run? Find \lim\limits_{t \to \infty} A^t\vec{x}_0 if it exists.
a. Following the strategy outlined in Theorem 7.1.6, we wish to construct an eigenbasis for A. Using technology, we find the eigenvalues λ_1 = 1, λ_2 = 0.5, and λ_3 = 0.2 of A. At this point, we know that matrix A is diagonalizable, by Theorem 7.3.4.
A straightforward but tedious computation, involving nothing more than finding some reduced row-echelon forms, reveals that
E_1 = span\begin{bmatrix}7\\5\\8\end{bmatrix}, E_0.5 = span\begin{bmatrix}1\\0\\-1\end{bmatrix}, E_0.2 = span\begin{bmatrix}-1\\3\\4\end{bmatrix}.
Thus, we have the eigenbasis \vec{v}_1=\begin{bmatrix}7\\5\\8\end{bmatrix}, \begin{bmatrix}1\\0\\-1\end{bmatrix}, \begin{bmatrix}-1\\-3\\4\end{bmatrix}.
Next we need to find the coordinates c_1, c_2, c_3 of the initial state vector \vec{x}_0 with respect to the given eigenbasis \vec{v}_1, \vec{v}_2, \vec{v}_3. It turns out that
\vec{x}_0 = c_1\vec{v}_1 + c_2\vec{v}_2 + c_3\vec{v}_3 = \frac{1}{20}\vec{v}_1 − \frac{2}{45}\vec{v}_2 − \frac{1}{36}\vec{v}_3.
Using the formula derived in Theorem 7.1.6, we have
A^t\vec{x}_0=c_1λ^t_1\vec{v}_1+c_2λ^t\vec{v}_2+c_3λ^t_3\vec{v}_3
=\frac{1}{20}\begin{bmatrix}7\\5\\8\end{bmatrix}-\frac{2}{45}(0.5)^t\begin{bmatrix}1\\0\\-1\end{bmatrix}-\frac{1}{36}(0.2)^t\begin{bmatrix}-1\\-3\\4\end{bmatrix}.
For example, the proportion of surfers on Page 1 after t iterations will be
\frac{7}{20}-\frac{2}{45}(0.5)^t+\frac{1}{36}(0.2)^t.
In the long run, as we let t go to infinity, this proportion will approach \frac{7}{20} =35%, since the other two terms, \frac{2}{45}(0.5)^t and \frac{1}{36} (0.2)^t , decay exponentially.
b. \lim\limits_{t \to \infty}(A^t \vec{x}_0) = \frac{1}{20}\begin{bmatrix}7\\5\\8\end{bmatrix}=\begin{bmatrix}35\%\\25\%\\40\%\end{bmatrix}, since the other two terms go to \vec{0}. See our work at the end of part a. In the long run, the proportions of surfers on the three pages will approach 35%, 25%, and 40%, respectively. Note that this limit is the unique distribution vector that is an eigenvector of A with eigenvalue 1. With the terminology of Theorem 2.3.11, this is the equilibrium distribution for A.
\vec{x}_equ=\frac{1}{20}\begin{bmatrix}7\\5\\8\end{bmatrix}.
In summary, \lim\limits_{t \to \infty} (A^t\vec{x}_0)=\vec{x}_{equ}.