Exercise 3: (8 pts) Consider the very simple link diagram below. Ralph has a % chance of starting at page A and a % chance of starting at page B. Once per minute, he clicks on a random link, if possible. A.-B a. (2 pts) What is the probability that Ralph will be on page B after four minutes? b. (6 pts) Now suppose that whenever Ralph accesses page B, after one minute he will randomly (with equal probability) jump to either page A or stay on page B. Find the probability that Ralph will be on page B after four minutes. Finding a steadystate vector of an altered transition matrix works well when the number of web pages is small, but is completely unfeasible when attempting to rank millions of webpages. In such a case, the best we can do is to approximate the PageRank vector. The following denition and theorem from your text help us to do this. Definition: A stochastic matrix P is regular if for some k every entry of P* is positive. Theorem: If P is a regular stochastic matrix, then P has a unique steady-state vector ~. Addi- tionally, if To is a probability vector, then the Markov chain { Pro} approaches T as k - co.Exercise 4: (8 pts) Consider the graph of links below. A B 1/3 The PageRank vector is, unsurprisingly, T= 1/3 1 /3 a. (2 pts) Find the altered transition matrix P. 0.27 b. (4 pts) Let To = 0.3 . Find Pro, P2To, P3xo, and P100 To. 0.5 c. (2 pts) Does the sequence { PKTo} approach r? If the altered transition matrix P is not regular, then P may not have a unique steady-state vector, and the limit of a Markov chain { Pro} may not be a steady-state vector of P. To fix this, we build a new matrix out of of P whose entries are all positive. If P is n xn, define M to be the n x n matrix whose columns are all (- , 1, n'n' . . . , n), and let 0