Opening Markov Chains Continued Further (Statistics 110, Lecture 33)
Markov Chains Continued Further (Statistics 110, Lecture 33)
- Length
- 47 min
- Level
- Undergraduate
- Recorded
- Harvard University2013
Chapter 1 of 5: Weighted random walk on networks
Builds Google's PageRank as a Markov chain with teleportation and computes its stationary distribution iteratively.
Random walks on weighted networks generalize the simple random walk on an undirected graph, and Blitzstein opens his 33rd Statistics 110 lecture at Harvard with them. Putting weights on the edges makes the stationary distribution proportional to each node's total edge weight, and every reversible Markov chain turns out to be such a walk. The rest builds the PageRank chain of Brin and Page, with web pages as states and hyperlinks as transitions. A teleportation term removes absorbing pages, makes the chain irreducible and clears zeros from the transition matrix. Iterated sparse matrix multiplication then replaces cubic-cost Gaussian elimination, assuming familiarity with transition matrices and basic linear algebra.
Random walks on weighted networks generalize the simple random walk on an undirected graph, and Blitzstein opens his 33rd Statistics 110 lecture at Harvard with them. Putting weights on the edges makes the stationary distribution proportional to each node's total edge weight, and every reversible Markov chain turns out to be such a walk. The rest builds the PageRank chain of Brin and Page, with web pages as states and hyperlinks as transitions. A teleportation term removes absorbing pages, makes the chain irreducible and clears zeros from the transition matrix. Iterated sparse matrix multiplication then replaces cubic-cost Gaussian elimination, assuming familiarity with transition matrices and basic linear algebra.
This lecture
Lecture 32 of 34 of Probability.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in