Recitation 3Steve GuJan 31 2008Outline• Part I: Review of LDSDDS– Linear, Deterministic, Stationary, Discrete, Dynamic System– Example: Google’s PageRank• Part II: From Deterministic to Stochastic– Randomness– Some histogramsPart IReview of LDSDDS X0X(0) = xX(n + 1) = F X(n) + G u(n)y(n) = H (n)Review of LDSDDS                                                1 1 12 2 23 3 31,1 1,2 1,3 1,1 1,2 1,3112 2,1 2,2 2,3 2 2,1 2,2 2,3333,1 3,2 3,3 3,1 3,2 3,3x u yX = x ,U = u ,Y = yx u yf f f g g gx (n +1) x (n)x (n +1) = f f f x (n) + g g gx (n +1) x (n)f f f g g g               ()()()nnn1231,1 1,2 1,3112 2,1 2,2 2,3 2333,1 3,2 3,3u (n)u (n)u (n)h h hy x (n)y = h h h x (n)y x (n)h h hFor example:Review of LDSDDS• Interested?• Confused?• Doubted?• Bored?• Hey! Let’s take a real examplePageRank• PageRank was developed at Stanford University by Larry Page (hence the name Page-Rank[1]) and later Sergey Brin as part of a research project about a new kind of search engine. The project started in 1995 and led to a functional prototype, named Google, in 1998PageRankHow to rank the importance of web pages?PageRankhttp://en.wikipedia.org/wiki/Image:PageRanks-Example.svgPageRank: Modelling Votesv link to uPR(v)PR(u) =L(v)PR(v) is the PageRank of vL(v) is the number of pages linked to vPR(u) is a collection of votes by pages linked to it!PageRank• For example:ABDCA receives 3 votesB receives 1 votesC receives 1 votesD receives nonePR(C) PR(D)PR(A) = PR(B) + +22PR(C)PR(B) =2PR(D)PR(C) =2PR(D) = 0PageRank: Dynamic Systems?For N pages, say p1,…,pNWrite the Equation to compute PageRank as:where l(i,j) is define to be:PageRank: Dynamic Systems?• Written in Matrix Form:12N-1NPR(p )PR(p )X=PR(p )PR(p )                           1122N-1 N-1NNPR(p ,n +1) PR(p ,n)l(1,1) l(1,2) l(1,N)PR(p ,n +1) PR(p ,n)l(2,1) l(2,2) l(2,N)PR(p ,n +1) PR(p ,n)l(N,1) l(N,N - 1) l(N,N)PR(p ,n +1) PR(p ,n)FX(n +1) = F X(n)Look familiar?PageRank: Dynamic Systems?• Usually there is a damping factor d, which is used to guarantee convergence, that is:   1122N-1 N-1NNPR(p ,n +1) PR(p ,n)1l(1,1) l(1,2) l(1,N)PR(p ,n +1) PR(p ,n)1l(2,1) l(2,2) l(2,N)(1- d)= + dNPR(p ,n +1) PR(p ,n)1l(N,1) l(N,N -1) l(N,N)PR(p ,n +1) PR(p ,n1)X(n +1) = F X(n) + G u(n)PageRank: Dynamic Systems!• PageRank is fully described by a LDSDDS• There is no magic here! • Ideas change the world (e.g. Google)• LDSDDS is simple• LDSDDS is powerful• LDSDDS is useful• LDSDDS is beautifulPart IIFrom Deterministic to StochasticRandomnessRandomness• Stock Prices• Games (Poker, Casino, etc)• Biology: Evolution, Mutation• Physics: Quantum Mechanics• …• Is the world deterministic or stochastic?Some Common HistogramsReview• LDSDDS• Uncover the secret: Google’s PageRank• DeterministicStochastic• That’s more fascinating• Welcome to the Stochastic World!The End• Thank you•