A matrix A RX is called stochastic when its entries are nonnegative and the sum...
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these mathematics questions
-
Prove that the product of two lower-triangular matrices is lower-triangular.
-
(a) Prove that the product of two orthogonal matrices is orthogonal, and so is the inverse of an orthogonal matrix. What does this mean in terms of rotations? (b) Show that (6) is an orthogonal...
-
Two dice are thrown and the sum of the two scores is recorded. Draw a graph of the resulting probability distribution of the sum and calculate its mean and variance. What is the probability that the...
-
Given the project network that follows, compute the early, late, and slack times for the project. Be sure to show the early finish and late start times on yournetwork. 20 15 25 10 10 Slack IS B
-
A sociologist is interested in the relation between x = number of job changes and y = annual salary (in thousands of dollars) for people living in the Nashville area. A random sample of 10 people...
-
Deductions for an owner of a rental apartment building who does not provide substantial services are reported on which of the following forms? a. Schedule C b. Schedule A c. Schedule E d. Schedule F
-
As shown in Fig. P8.71, water "bubbles up" 3 in. above the exit of the vertical pipe attached to three horizontal pipe segments. The total length of the 0.75-in.diameter galvanized iron pipe between...
-
Portland Optics, Inc., specializes in manufacturing lenses for large telescopes and cameras used in space exploration. As the specifications for the lenses are determined by the customer and vary...
-
Use the Chain Rule to find the indicated partial derivatives. z=3x-5y; x = u46v, y = (2u - v); dz dz au av 20 220 = = 12u3-56 (2u-v)3 -24(v-2u)3-48v2 eBook Submit Answer x
-
Natura Cosmeticos SA, Brazils all natural, ethically-sourced, sustainable beauty products company, recently purchased Avon Products Inc. as a way to enter the U.S., Europe, and Chinese cosmetics...
-
Which of the market research techniques did you find most (least) valuable? Why? Which market research techniques would be most valuable to a brand manager? Why? How did the type of brand meaning...
-
Develop a list of references that will improve your employment prospects.
-
Evaluate the primary needs of employers for positions of interest.
-
Develop strategies for responding to common job interview questions.
-
Identify a topic of interest. Create a storyboard to outline the titles, content, and related story line of your PowerPoint slides.
-
Think about a recent team or group project you were part of. Evaluate your teams performance in the following ways: How well did your team set goals up front? How well did your team establish norms,...
-
Assess the role of international law in addressing (preventing and responding to) the Covid-19 pandemic. You may choose to limit your answer to one main body of international law. In your essay, make...
-
Find the area of the surface generated by revolving the para- metric curve x = cos 1, y = sin? 1 (0 < I sa/2) about the y-axis.
-
An n-input, m-output boolean function is a function from {TRUE, FALSE} n to {TRUE, FALSE} m . How many n-input, 1-output boolean functions are there? How many n-input, m-output boolean functions are...
-
Consider a modification of the rod-cutting problem in which, in addition to a price p i for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the...
-
Why do we require that w i i = 0 for all 1 i n?
-
Assume that Timmons Towel and Diaper Services bank pays 1% (APR with quarterly compounding) on its compensating balance accounts. What is the EAR of Timmonss three-month loan?
-
What is the difference between transshipment and transloading?
-
Distinguish the roles played by liner shipping companies and terminal operators in LSCM.
Study smarter with the SolutionInn App