Transition matri cesPowers of matrices can describe trans ition of a system.Example 1. (review)•Fibona c c i numbers Fn: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,• Fn+1= Fn+ Fn− 1• Hence:Fn+1Fn= nF1F0Example 2. Con sid er a fixed population of people with or with out a job. Suppose that,each year,50% of those unemployed fin d a job while 10% of those employed loose theirjob.What is the unemployment rate in the long term equilibrium?Solution.employed no job0.10.90.50.5xt: employed at ti me tyt: unemployed at ti me txt+1yt+1=The matri x is a Markov matrix. Its columns add t o 1 and it has no negative entries.Armi n [email protected] rankGoogle’s success is based on an algor ithm to rank websites , thePage rank, named afterGoogle founder Larry Page.The basic idea is to determine how likely it is that a web user randomly gets to a gi venwe bpage. The webpages are then ranked by these probabilities.Example 4. Suppose the internet consisted of only the four webpages A, B, C,D linkedas in the following gra p h:Imagine a surfer following these l inks at random.For the probabilityPRn(A) that s he is at A (after n steps), we add:• the probability that she was at B (at exactly one time s tep before),and left forA, (that’s PRn − 1(B) ·12)• the proba bility that sh e was at C, and left for A,• the proba bility that sh e was at D, and left for A.A BC D• Hence: PRn(A) = PRn− 1(B) ·12+ PRn− 1(C) ·11+ PRn− 1(D) ·01•P Rn(A)=0121 0PRn − 1(A)PRn − 1(B)PRn − 1(C)PRn − 1(D)• The PageRank vectorPR (A)PR (B)PR (C)PR (D)=P R∞(A)P R∞(B)P R∞(C)P R∞(D)is the long-term equilibrium .Armi n [email protected] 5. In practical situations, the system might be too large for finding th e eigen-vector by elimination.An altern ative to elimination is the power method:If T is a n (acy clic and irreducible) Markov matrix, then for any v0the vectors Tnv0converge to an eigenvect or with eigenvalue 1.Here:T =0121 0130 0 0130 0 113120 0P R(A)P R(B)PR (C)P R(D)=0.3750.1250.3130.188T1/41/41/41/4=Remark 6.•If all entries of T are positive, then the power method is guaranteed to work.• In the context of PageRank, we can make sure that this is the case, by replacing Twith• Why does Tnv0converge to a n eigenvector with eigenvalue 1?Armi n
View Full Document
Unlocking...