Light Random Walks on Graphs

Status: placeholder — light treatment only (no MCMC in this course).

Goals¶

• Random walk on an undirected graph

• Stationary distribution (degree-proportional)

• Intuition only: mixing / exploration

• Pointer: Markov-chain methods (MCMC, MH, Gibbs) are deferred to Statistical Machine Learning

Outline¶

1. One-step transition on an undirected graph

2. Stationary distribution $\pi_v \propto \deg(v)$

3. Why walks explore a graph (short demo)

4. Bridge to SML: Markov chains as a full topic next semester

Sources¶

• Blum, Hopcroft, Kannan, Foundations of Data Science, selected sections