PageRank: A Trillion Dollar Algorithm

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. Chapters: 0:00 Intro 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) 24:25 Recap/Conclusion 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. References: 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 Socials: Patreon: https://www.patreon.com/reducible Twitter: https://twitter.com/Reducible20 Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons: Andreas Adam Dřínek Burt Humburg Eugene Tulushev Matt Q Winston Durand Andjela Arsic Mutual Information Richard Wells Sebastian Gamboa Zac Landis