Introduction to Markov chains Definitions, properties and PageRank example Towards Data Science Feb 24, 2019 https://towardsdatascience.com/brief-introduction-to-markov-chains-2c8cab9c98ab --- Define a markov chain where states are the pages on the internet, and transitions are the links from a given page, all having equal probabilities. Let a random surfer, starting at a random page, traverse the chain. Eventually the distribution of states will converge to some stationary distribution. Use the probability of each state as the relative importance of that page. In practice, we don't need to run a random surfer at all, but just recover the probabilities of each transition by letting it be $1/K$ if there are $K$ out links. Then build a probability transition matrix: ![[Screenshot from 2021-05-21 23-11-30.png|300]] Find the eigenvalues of this system by solving this problem (where $\pi$ is the stationary distribution, and $\pi_i$ is the probability of being in state $i$): ![[Screenshot from 2021-05-21 23-11-34.png|400]] and those probabilities now serve as page rank values for each page: ![[Screenshot from 2021-05-21 23-11-40.png|600]]