Consider a random walk over 3 webpages, 1, 2, 3. At any step, if the person...

Transcribed Image Text:

Consider a random walk over 3 webpages, 1, 2, 3. At any step, if the person is at webpage 1, then with probability 1/6, she will go to webpage 2, and with probability 1/6, she will go to webpage 3. If the person is at webpage 2, then with probability 1/2, she will go to webpage 1, and with probability 1/2, she will go to webpage 3. If the person is at webpage 3, then with probability 1/2, she will go to webpage 1, and with probability 1/2, she will go to webpage 2. Let X, be the webpage the person is browsing at time t, and let us assume she starts from webpage 1 at time 0, i.e., Xo = 1. (1) Let Kij %3D P(X+1 = j|X = i). Let K = (Kj) be the 3 x 3 transition matrix. Write down !! %3D К. (2) Let p" = P(Xt = i). Let p) = (p",i = 1,2,3) be the row vector. Calculate p for t = 1,2,3 using vector matrix multiplication. (3) Let 7; be the stationary distribution at webpage i, so that 7; = E n;Kij. Let 7 = (7i, i = 1, 2, 3) be the row vector. Then 7 = aK. Given K, solve a from this equation. Is p3) close to n? (4) Based on the above calculations, answer the following questions. Suppose there are 1 million people doing the above random walk independently, and suppose they all start from webpage 1 at time t = 0. Then on average, what is the distribution of these 1 million people for t = 1,2, 3? What is the stationary distribution of these 1 million people? Which page is the most popular? %3D %3D Consider a random walk over 3 webpages, 1, 2, 3. At any step, if the person is at webpage 1, then with probability 1/6, she will go to webpage 2, and with probability 1/6, she will go to webpage 3. If the person is at webpage 2, then with probability 1/2, she will go to webpage 1, and with probability 1/2, she will go to webpage 3. If the person is at webpage 3, then with probability 1/2, she will go to webpage 1, and with probability 1/2, she will go to webpage 2. Let X, be the webpage the person is browsing at time t, and let us assume she starts from webpage 1 at time 0, i.e., Xo = 1. (1) Let Kij %3D P(X+1 = j|X = i). Let K = (Kj) be the 3 x 3 transition matrix. Write down !! %3D К. (2) Let p" = P(Xt = i). Let p) = (p",i = 1,2,3) be the row vector. Calculate p for t = 1,2,3 using vector matrix multiplication. (3) Let 7; be the stationary distribution at webpage i, so that 7; = E n;Kij. Let 7 = (7i, i = 1, 2, 3) be the row vector. Then 7 = aK. Given K, solve a from this equation. Is p3) close to n? (4) Based on the above calculations, answer the following questions. Suppose there are 1 million people doing the above random walk independently, and suppose they all start from webpage 1 at time t = 0. Then on average, what is the distribution of these 1 million people for t = 1,2, 3? What is the stationary distribution of these 1 million people? Which page is the most popular? %3D %3D