Random Walks on Graphs

Random Walks on Finite and Infinite Graphs

Random walks on graphs involve a process where a particle moves from vertex to vertex based on transition probabilities. For finite graphs, the walk is often analyzed for properties like recurrence and transience, while for infinite graphs, aspects like escape probabilities are considered.

Hitting Times, Cover Times, and Mixing Times

Hitting time ${\tau }_{u,v}$ is the expected time to reach vertex $v$ from $u$. Cover time is the expected time to visit all vertices. Mixing time refers to how quickly the walk approaches its stationary distribution $\pi$.

Electrical Networks and Spectral Graph Theory

There is a deep connection between random walks and electrical networks, where hitting times can be expressed as resistances. Spectral graph theory uses eigenvalues of the Laplacian or adjacency matrix to bound mixing times, such as through the spectral gap ${\lambda }_2$.

Applications to Web Search and Sampling Algorithms

Random walks are used in PageRank for web search, modeling web surfers. They also serve in Markov Chain Monte Carlo methods for sampling from complex distributions.

Common Pitfalls

Common mistakes include assuming symmetry in transition probabilities or neglecting boundary effects in infinite graphs. Another pitfall is misinterpreting mixing times for non-reversible chains.

Summary

• Random walks are fundamental processes on graphs with applications in various fields.
• Key metrics include hitting times, cover times, and mixing times, which measure efficiency and convergence.
• Electrical network analogies provide intuitive understanding and computational tools.
• Spectral methods offer rigorous bounds on mixing behavior through eigenvalues.
• Applications span from web search algorithms like PageRank to statistical sampling techniques.