A matrix A RX is called stochastic when its entries are nonnegative and the sum...

Transcribed Image Text:

A matrix A € R"X" is called stochastic when its entries are nonnegative and the sum of the entries in each of its columns is equal to 1. 1. Prove that the product of two stochastic matrices is also stochastic. 2. Prove that 1 occurs as an eigenvalue for every stochastic matrix A. Hint: consider a vector in the image of (A – I); does it satisfy any linear condition? 3. There are five bureaucrats at the University of Toronto -- let's not name names, so we'll call them 1, 2, 3, 4, 5. None of them want to help you, so they talk to you for 1 minute and then randomly send you to other bureaucrats according to the following directed graph: 1 2 3 4 > 5 This means, for example, that Bureaucrat 2 will send you to number 4 or number 5 with equal probability 1/2. During an eternity of going through red tape, following the directions of these bureaucrats, a certain fraction of your time will be spent with each of these bureaucrats (assume your travel between the offices is instantaneous). Rank the bureaucrats in order from the most time-wasting to the least. Hint: The expected fraction of time x; spent at bureaucrat i will be a sum of the expected fractions a3, weighted by the probability that j sends you to i. For example a1 = 4, because the only way to get to 1 is if you were at 4 and they happened to send you to 1, which only happens half the time (the other half, you would be sent to 5). Write the whole problem as an eigenvector problem Ar = x, r = where A is a stochastic 5 x 5 matrix. Use whatever means at your disposal to resolve the eigenvalue problem, just explain the steps or software. Remark: once you find the ranking of the bureaucrats, you will understand exactly how Google decides how to rank webpages in order of "importance": the bureaucrats are webpages and the arrows are hyperlinks between them. The procedure outlined above may fail for a more complicated network, where you can have sub-nets which are completely disconnected from other parts of the network. The simple idea of the Google founders was to put extra links in by hand which are only followed with low probability -- then the stochastic eigenvalue problem has a unique solution. To learn exactly how the Google algorithm works, read this article. A matrix A € R"X" is called stochastic when its entries are nonnegative and the sum of the entries in each of its columns is equal to 1. 1. Prove that the product of two stochastic matrices is also stochastic. 2. Prove that 1 occurs as an eigenvalue for every stochastic matrix A. Hint: consider a vector in the image of (A – I); does it satisfy any linear condition? 3. There are five bureaucrats at the University of Toronto -- let's not name names, so we'll call them 1, 2, 3, 4, 5. None of them want to help you, so they talk to you for 1 minute and then randomly send you to other bureaucrats according to the following directed graph: 1 2 3 4 > 5 This means, for example, that Bureaucrat 2 will send you to number 4 or number 5 with equal probability 1/2. During an eternity of going through red tape, following the directions of these bureaucrats, a certain fraction of your time will be spent with each of these bureaucrats (assume your travel between the offices is instantaneous). Rank the bureaucrats in order from the most time-wasting to the least. Hint: The expected fraction of time x; spent at bureaucrat i will be a sum of the expected fractions a3, weighted by the probability that j sends you to i. For example a1 = 4, because the only way to get to 1 is if you were at 4 and they happened to send you to 1, which only happens half the time (the other half, you would be sent to 5). Write the whole problem as an eigenvector problem Ar = x, r = where A is a stochastic 5 x 5 matrix. Use whatever means at your disposal to resolve the eigenvalue problem, just explain the steps or software. Remark: once you find the ranking of the bureaucrats, you will understand exactly how Google decides how to rank webpages in order of "importance": the bureaucrats are webpages and the arrows are hyperlinks between them. The procedure outlined above may fail for a more complicated network, where you can have sub-nets which are completely disconnected from other parts of the network. The simple idea of the Google founders was to put extra links in by hand which are only followed with low probability -- then the stochastic eigenvalue problem has a unique solution. To learn exactly how the Google algorithm works, read this article.