Suppose we perform a random walk over three states = {1, 2, 3}. Let Xt be the

state at step t. Suppose we start from 1, i.e., X0 = 1. Suppose at each step, we randomly move to one of the other two states with equal probability, regardless of the past history. That is, P (Xt+1 = y|Xt = x,Xt1,Xt2,...,X0) = P(Xt+1 = y|Xt = x). Let K(x,y) = P(Xt+1 = y|Xt = x), where x, y .

(1) Write down K as a 33 matrix. (2) Prove P(Xt+1 = y) = x P(Xt = x)K(x,y) for any y . (3) Calculate P(X1 =x), P(X2 =x),P(X3 =x) for x. (4) What does P(Xt = x) converge to in this case? You don't have to be rigorous for proving

convergence. Can you map the above calculations to an elementary school problem by considering 1 million people starting from state 1, and doing random walk independently? Can you expand this problem so that contains millions of webpages on the internet, and people are doing random surfing?