Lecture 16

Question 1

Adjacency matrix, from? to?

Answer 1

from top (column indexes) to left (line indexes)

Question 2

Markov property

Answer 2

only the most recent state matters to determine the probability of the next state

Question 3

Transition (or Markov) matrices

Answer 3

(I,J) entry is a transition probability in [0,1], from state J to state I. Columns add up to one.

Question 4

Markov A, state x0, how to predict?

Answer 4

x1 = A.x0
x2 = A.x1…
Power method

Question 5

Steady-state?

Answer 5

Long-run equilibrium state reached regardless of the current state, converges to steady-state vector x=Ax s.t x is the eigenvector corresponding to eigenvalue λ=1

Question 6

Page rank

Answer 6

Probability for a website to be visited by a user randomly clicking on links.
Howto:
Matrix with links from one website to another. Then columns are averaged to get the probability to go from one website to another. If no link in a website, numerical issue, we average to every website.

Question 7

Page rank issue

Answer 7

Markov matrix does not guarantee a unique solution if the graph is not connected.
Perron-Frobenius Theorem: if M markov matrix with all positive entries, then M has a unique steady-state x.

M=0.85A + 0.15/n 1, O(n) (as if 85% chance to clic a link / 15% chance to start over from a random page)