Random Walks

This course introduces random walks through Markov chains, covering transition probabilities, invariant distributions, and recurrence results. It applies these ideas to PageRank and randomized algorithms for graph connectivity.

Syllabus

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