Below are the notes I prepared for a talk that I gave at our seminar on limiting distributions for (finite-state, time-homogeneous) Markov chains, drawing on PageRank as an example. We see in particular how the “random teleport” possibility in the PageRank random walk algorithm can be motivated by the theoretical guarantees that result from it: the transition matrix is both irreducible and aperiodic, and iterated application of the transmission matrix converges more rapidly to the unique stationary distribution.
More thorough reading material:
- Karl Sigman’s online lecture notes one two
- Klenke’s book Wahrscheinlichkeitstheorie
- Haveliwala et. al, The Second Eigenvalue of the Google Matrix (2003)
Update: that the limit of the average time spent is the reciprocal of the expected return time can be proved using the renewal reward theorem (thank you Prof. Sigman!)
2 Replies to “Limiting Distributions of Markov Chains”