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
-
Refer to the previous exercise. The same week that the Field Poll was released a Web site called SFGate.com (www.sfgate.com/polls/) (www.sfgate.com/polls/) asked visitors to Click to vote on their...
-
Paint is poured onto a table, forming a circle which increases at a rate of 2.5 cm s . Find the rate the radius is increasing when the area of the circle is 20 cm.
-
If it's \(3: 00\), what time will it be in 89 hours?
-
Gunn Manufacturing Company experienced the following accounting events during its first year of operation. With the exception of the adjusting entries for depreciation, assume that all transactions...
-
The following information for Sarajevah Company is available on February 28, 2002, the end of a monthly accounting period. You are to prepare the necessary adjusting journal entries for Sarajevah...
-
You are considering a purchase of a 4-plex, which is located in a desirable neighborhood. The cost of the property is $500,000. Effective rents are expected to average $1500 per month. Every resident...
-
The percentage of all distributed coupons that are taken to stores for price discounts is known as the _____. a. turnover rate b. discount rate c. conversion rate d. redemption rate e. return on...
-
For the following simply supported beam: a) Determine equations for V(x) and M(x) for sections 0 x 14 and 14 x20. Box your answers. b) Roughly sketch the shear and bending moment diagram for the...
-
You are preparing for a top-level meeting between the Minister of International Trade, the Minister of Foreign Affairs, and senior business executives representing several multinational corporations...
-
1. A rope AB 6 m long is connected at two points A and B at the same level 4.5 m apart. A load of 2000 N is suspended from point C on the rope at 2 m from A, as shown in the figure below. What load...
-
Assume that Fake Stone, Inc. is operating at full capacity. Also assume that assets, costs, and current liabilities vary directly with sales. The dividend payout ratio is constant. The Companys sales...
-
A given hardware contains 5 logic blocks that require 20ns, 35ns, 15ns, 50ns and 25ns respectively. The latches require 10ns to load. To speed up the operation, you pipelined the hardware. Draw your...
-
AutoParts Ltd. uses a periodic inventory system and the LIFO method for inventory valuation. The company recorded the following inventory transactions in December 20X1: Beginning Inventory on...
-
Discuss whether responsible human resources management should apply different standards for the home company and suppliers, for developed countries and developing countries, and for large companies...
-
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?
-
6. One afternoon while visiting friends, tennis star Vitas Gerulaitis fell asleep in their pool house. A mechanic had improperly installed the swimming pool heater, which leaked carbon monoxide fumes...
-
5. One Friday afternoon a custodian at the Lazear Elementary School in Oakland, California, raped an 11-year-old student in his office on the school premises. The
-
8. A. B. Rains worked as a broker for the Joseph Denunzio Fruit Co. Raymond Crane offered to sell Rains nine carloads of emperor grapes. Rains accepted the offer on behalf of Denunzio. Later, Rains...
Study smarter with the SolutionInn App