Random Walks

Explore the fascinating world of random walks and Markov chains in this comprehensive lecture. Delve into the mathematical foundations of these concepts, starting with an introduction to Markov chains and their definitions. Learn through practical examples and clear notation how to model and analyze random processes. Discover key theorems, including the Fundamental Theorem and Mean First Recurrence Theorem, that provide insights into the long-term behavior of Markov chains. Investigate the concept of invariant distribution and its calculation. As an interlude, examine the PageRank algorithm, a real-world application of Markov chains in web search engines. Conclude by studying random walks on connected undirected graphs, exploring transition matrices, and invariant distributions in this context. Gain a solid understanding of these powerful mathematical tools used in various fields, from computer science to physics.

Intro
A day in the life of me
Markov Chain – Definition
Markov Chain – Example
Markov Chain - Notation
A random initial state
Invariant Distribution calculation
Fundamental Theorem
Mean First Recurrence Thm
Markov Chain Summary
Interlude: PageRank
Connected undirected graph. Each step: go to a random neighbor.
What is the transition matrix K?
What is the invariant distribution ?
Examples