2022-05-22

[public] 17.1K views, 7.67K likes, dislikes audio only

Reducible

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