PhD course: Random walks on graphs and their applications
Michal Koucký
<koucky@math.cas.cz>
Spring Semester 2012
Duration: 6 weeks (first lecture April 10)
Time and place: Tue 12:302:15pm in Nygaard297 and Thu 10:15noon in Nygaard298
In this course I plan to give an introduction to Markov chains, random walks on graphs and their
applications. This course assumes a reasonable knowledge of mathematics and probability theory. It
is intended for computer science PhD students. It is expected to be possible for PhD students to
take the course for credit, the exact number of ECTS and exam form will be negotiated later.
The tentative list of topics:

Markov chains

Stationary distribution, convergence

Applications: selfadjusting queues

Random walks on graphs

Hitting time, cover time

Applications: testing connectivity, treasure hunt

Short random walks

Dynamically changing graphs

Graph resistance

Applications: Pagerank, individual pagerank, clustering
References:
 Handout lecture notes.
 James R. Norris. Markov Chains, Cambridge University Press, 1998.
 Olle Häggström. Finite Markov Chains and Algorithmic Applications, Cambridge University Press, 2002.

László Lovász. Random Walks on Graphs:
A Survey.

David Aldous and James Allen Fill. Reversible Markov Chains
and Random Walks on Graphs.
 Greg Barnes and Uriel Feige. Short random walks on graphs. SIAM J. Discrete Math. 9(1): 1928 (1996).
 Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, and Masafumi Yamashita. Impact of local topological information on random walks on finite graphs. ICALP 2003.
 Chen Avin, Michal Koucký, and Zvi Lotker. How to explore a fastchanging world (cover time of a simple random walk on evolving graphs). ICALP 2008.
 Prasad Tetali. Random Walks and the Effective Resistance of Networks. Journal of Theoretical Probability 4 (1991), 101109.
 Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari. The Electrical Resistance of a Graph Captures its Commute and Cover Times. Computational Complexity, 6(4): 312340 (1997).
 Reid Andersen, Fan Chung, and Kevin Lang. Using pagerank vectors to locally partition a graph. Internet Math. 4(1):3564 (2007).
Probability overview.
Exam
The exam is oral. Write me an email to schedule an exam which must take place before June 21st.
Exam topics
 Stationary distribution and convergence of random walks.
 Hitting time, Matthews bound.
 Cover time of undirected graphs.
 Random walks on trees.
 Short random walks, the Metropolis chain.
 Random walks on dynamically changing graphs.
 Graph resistance.