Visit https://brilliant.org/Reducible/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription.
1:00 Defining Markov Chains
2:00 Introducing the Problem
4:08 Modeling Markov Chains
6:26 Stationary Distributions
7:20 Uniqueness of Stationary Distributions (Irreducibility)
9:11 Convergence of Stationary Distributions (Periodicity)
12:15 Ergodic Theorem
13:32 Computing Stationary Distributions
17:43 Practically Computing Stationary Distributions
19:29 PageRank Algorithm
23:12 Sponsored Message (Brilliant)
In the late 1990’s two PhD Students Larry Page and Sergey Brin came up with an algorithm that revolutionized search called PageRank. In this video we discuss some of the beautiful mathematical ideas and complexities of PageRank. Fundamentally, PageRank is all about calculating stationary distributions of Markov chains. We talk about some of the challenges of computing these distributions as well as the adjustments that PageRank made to these ideas to make it dominate the search landscape.
Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.
Original PageRank Paper: http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf
Proof of the Ergodic Theorem: https://math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALFULL/Casarotto.pdf
General inspiration/further reading for Markov chains: Ch 1 of Probability in Electrical Engineering and Computer Science by Jean Walrand
Good discussion on stationary distributions of Markov chains: https://brilliant.org/wiki/stationary-distributions/
Markov chains and PageRank: https://www2.math.upenn.edu/~kazdan/312F12/JJ/MarkovChains/markov_google.pdf
This video wouldn’t be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim – Mathematical Animation Framework (Version v0.11.0) [Computer software]. https://www.manim.community/
Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible
Music in this video comes from Jesús Rascón and Aaskash Gandhi
Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons: