Markov chains and Google's PageRank algorithm

Determine whether the following statements are true or false and provide a justification of your response.

1. Every stochastic matrix has a steady-state vector.

2. If $A$ is a stochastic matrix, then any Markov chain defined by $A$ converges to a steady-state vector.

3. If $A$ is a stochastic matrix, then $\lambda=1$ is an eigenvalue and all the other eigenvalues satisfy $|\lambda| \lt 1$.

4. A positive stochastic matrix has a unique steady-sta…

Consider the stochastic matrix .

1. Find the eigenvalues of $A$.

2. Do the conditions of the Perron-Frobenius theorem apply to this matrix?

3. Find the steady-state vectors of $A$.

4. What can we guarantee about the long-term behavior of a Markov chain defined by the matrix $A$?

Explain your responses to the following.

1. Why does Google use a Markov chain to compute the PageRank vector?

2. Describe two problems that can happen when Google constructs a Markov chain using the Google matrix $G$.

3. Describe how these problems are consistent with the Perron-Frobenius theorem.

4. Describe why the Perron-Frobenius theorem suggests creating a Markov chain using the modified Google matrix $G' = \alpha G + (1-\alpha)H_n$.

Suppose that $A$ is a stochastic matrix and that $\xvec$ is a probability vector. We would like to explain why the product $A\xvec$ is a probability vector.

1. Explain why $\xvec=\threevec{0.4}{0.5}{0.1}$ is a probability vector and then find the product $S\xvec$.

2. More generally, if $\xvec$ is any probability vector, what is the product $S\xvec$?

3. If $A$ is a stochastic matrix, explain why $SA=S$.

4. Explain why $A\xvec$ is a probability vector by considering the product $SA\xvec$.

Using the results of the previous exercise, we would like to explain why $A^2$ is a stochastic matrix if $A$ is stochastic.

1. Suppose that $A$ and $B$ are stochastic matrices. Explain why the product $AB$ is a stochastic matrix by considering the product $SAB$.

2. Explain why $A^2$ is a stochastic matrix.

3. How do the steady-state vectors of $A^2$ compare to the steady-state vectors of $A$?

This exercise explains why $\lambda=1$ is an eigenvalue of a stochastic matrix $A$. To conclude that $\lambda=1$ is an eigenvalue, we need to know that $A-I$ is not invertible.

1. What is the product $S(A-I)$?

2. What is the product $S\evec_1$?

3. Consider the equation $(A-I)\xvec = \evec_1$. Explain why this equation cannot be consistent by multiplying by $S$ to obtain $S(A-I)\xvec = S\evec_1$.

4. What can you say about the span of the columns of $A-I$?

5. Explain why we can conclude that $A-I$ is not invertib…