advertisement

Recitation 3

Steve Gu

Jan 31 2008

Outline

• Part I: Review of LDSDDS

– Linear, Deterministic, Stationary, Discrete,

Dynamic System

– Example: Google’s PageRank

• Part II: From Deterministic to Stochastic

– Randomness

– Some histograms

Part I

Review of LDSDDS

X(0) = x

0 y(n) = H X (n)

Review of LDSDDS

x x

1

u

3

u

y y

1

2

3

y

1

( ) y y

2

3

For example: x (n +1)

f f

1,1

2,1

3,1 f f f

1,2

2,2

3,2 f f f

1,3

2,3

3,3

2 x (n)

g g

1,1

2,1

3,1 g g g

1,2

2,2

3,2 g g g

1,3

2,3

3,3

h h

1,1

2,1

3,1 h h h

1,2

2,2

3,2 h h h

1,3

2,3

3,3

1 x (n)

1 u (n)

Review of LDSDDS

• Interested?

• Confused?

• Doubted?

• Bored?

• Hey! Let’s take a real example

PageRank

• 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 1998

**How to rank the importance of web pages?**

PageRank

PageRank http://en.wikipedia.org/wiki/Image:PageRanks-Example.svg

PageRank: Modelling Votes

PR(u) = v link to u

PR(v)

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!

• For example:

**B**

PageRank

A receives 3 votes

B receives 1 votes

C receives 1 votes

D receives none

**A**

**D**

**C**

PR(A) = PR(B) +

PR(B) =

PR(C) =

PR(C)

2

PR(D)

2

PR(D) = 0

2 2

PageRank: Dynamic Systems?

For N pages, say p1,…,pN

Write the Equation to compute PageRank as: where l(i,j) is define to be:

X =

PageRank: Dynamic Systems?

• Written in Matrix Form:

1

PR(p ,n +1)

N-1

PR(p ,n +1)

l(1,1) l(1,2) l(2,1) l(2,2) l(N,1) l(1,N) l(2,N) l(N,N - 1) l(N,N)

F Look familiar?

PageRank: Dynamic Systems?

• Usually there is a damping factor d, which is used to guarantee convergence, that is:

1

PR(p ,n +1)

N-1

PR(p ,n +1)

=

(1- d)

N

1

1

1

+ d

l(1,1) l(1,2) l(2,1) l(2,2) l(N,1) l(1,N) l(2,N) l(N,N - 1) l(N,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 beautiful

Part II

From Deterministic to Stochastic

Randomness

Randomness

• Stock Prices

• Games (Poker, Casino, etc)

• Biology: Evolution, Mutation

• Physics: Quantum Mechanics

• …

• Is the world deterministic or stochastic?

Some Common Histograms

Review

• LDSDDS

• Uncover the secret: Google’s PageRank

• Deterministic Stochastic

• That’s more fascinating

• Welcome to the Stochastic World!

• Thank you

• Q&A

The End