News

Abstract

When a token moves randomly from vertex to vertex via the edges of a graph, it is taking a random walk. This simple process is as useful as it is elegant, with multiple analogies in electrical networks and applications to the theory of computing. There have been remarkable new advances in this classical subject and we will spend much time with recent work and unsolved problems.

Prerequisites: Basic probability (e.g., Math 20 or 60), and the mathematical sophistication of a beginning graduate student, an advanced undergraduate mathematics major, or a theory-oriented CS major.

Here is a (tentative) rough weekly syllabus:

1. Review of probability; random walk definition, examples, generalizations

Week 1, Doyle and Snell, Chapter 1.

2. Electrical networks, Rayleigh monotonicity, Foster's Theorem

3. Random walk on a grid; Polya's Theorem

4. Hitting and commute times, Chandra's Theorem

5. Cover times, Mathew's Theorem, universal sequences

6. Mixing and sampling

7. Collisions and an application in distributed computing

8. Markov decision theory and the Gittins Index

9. Search and pursuit; blanketing

Classes

Room: Kemeny Hall 108
Lectures: "10A" slot, in particular: Tuesdays and Thursdays 10-11:50 (with a break).
X-hour: Wednesdays (same room) 3:00 pm--3:50pm February 6,13 and 20.

Staff

Instructor:

Peter Winkler -- Kemeny Hall 231 / Tel. 6-3468
Office Hours: Tuesdays, 3:30-4:30; Wednesdays, 2-3; Fridays, 11-12; and by appointment.

Textbooks

Peter Doyle and J. Laurie Snell, Random Walks and Electrical Networks, Mathematical Association of America Carus Manuscript, 1984.
Available online here.

David Aldous and James Fill, Reversible Markov Chains and Random Walks on Graphs, monograph in preparation.
Available online here.

Grading

Your grade will be based on homework, class participation, and a project (different for each student) which entails a half-hour class presentation and a short paper. There may also be the occasional surprise in-class one-question quiz.

Final papers are posted below, alphabetically by author. If at any time you want yours withdrawn or replaced by an new version, I am happy to oblige.

Following are the papers:

Ivan Antoniv, Ergodicity for Non-reversible Chains

Kassie Archer, Exact Mixing and the Halting State Theorem

Keith Carlson, Collisions of Multiple Tokens Taking Random Walks on a Graph

Fabio Drucker, Run or Hide? Fixed and Moving Targets

Tim Dwyer, Uniform Distribution of Last New Vertex in Random Walk on a Graph Determines (Almost) the Graph

Shahrzad Haddadan, Shuffling

Zachary Hamaker, Blanket Times and the Gaussian Free Field

Andrew Hannigan, Whirling Tours and Hitting Times on Trees

Seth Harris, The Gittins Strategy: Choosing from Multiple Markov Chains

Jeffery Hein, Wald's Identity

EJ Infeld, Unpredictable Walks on the Integers

Li Jiang, Cover Time on a Regular Graph

Sagar Kale, Eigenvalues and Mixing Time

Sucharita Jayanti, The Random Target Lemma

Natasha Komarov, On Bounding the Expected Progress of a Random Walk

Vijay Kothari, Random Walks and Random Spanning Trees

Scott M. Lalonde, The Martingale Stopping Theorem

Zhong Li, Introduction to Discrete Time Birth-Death Models

Shrirang Mare, Polya's Recurrence Theorem

Nathan McNew, Random Walk with Restarts, 3 Examples

Sandeep Nuckchady, Two Proofs of Commute Time Being Proportional to Effective Resistance

Athina Panotopoulou, Bounds for Edge-Cover by Random Walks

Xiaochen Qi, Random Walks and Universal Sequences

Longquan Qiao, Maximum Hitting Time

Chen Qin, Random Walks and Foster's Resistance Theorem

Everett Sullivan, A Brief Overview of the Clairvoyant Demon

Homework

Homework will be assigned at each class period, due at the beginning of the next class. In most cases nothing written will be due, but any student may be called upon to present his or her homework to the class.

Assignments

Due Thursday Jan 10: Derive a formula for the probability that a random walk on K_3 is at its starting point at time n.

Due Tuesday Jan 15: A Markov chain is ergodic if for some N, it is possible to get from any state i to any state j in exactly N steps. Prove that random walk on a finite, connected, non-bipartite graph is ergodic.

Due Thursday Jan 17: Problems 1.1.9 and 1.1.10 from Doyle & Snell.

Due Tuesday Jan 22: Find the expected hitting time from i to j for simple random walk on the path on vertices 0 to m. (States 0 and m are not absorbing states here, just vertices of degree 1.) HINT: you might find it easiest to start with the i=0 case.

Due Thursday Jan 24: Compute and hand in (except for those students who are presenting next week) the three different effective resistances between pairs of vertices of the cube. Assume unit resistance on each of the 12 edges.

Due Tuesday Jan 29: (a) Compute the expected cover time for the path on vertices 0,...,m for a simple random walk starting at vertex j; and (b) Same for the cycle on n vertices, starting anywhere.

Due Thursday Jan 31: Compute the expected time to walk from 0 to m on a path of length m, given that you never return to 0.

Due Tuesday Feb 5: Prove, or at least argue, that for any 3 vertices x, y and z of a graph G, the expected time for a simple random walk starting at x to hit y, then z, and then return to x equals the expected time starting at x to hit z, then y, and then return to x.

Due Thursday Feb 7: Prove the Random Target Lemma by showing that the expected time to reach a random target (chosen from the stationary distribution) from vertex i is a harmonic function of i, with no boundary, and therefore constant.

Due Tuesday Feb 12: (a) What is the largest possible effective resistance between two adjacent vertices u and v in an n-vertex, d-regular graph? (You may assume n is large compared to d.) (b) To think about: what n-vertex, cubic (3-regular) graph do you think has highest expected cover time?

Due Thursday Feb 14: (a) Compute the expected time for a simple random walk on the n-vertex cycle to traverse every edge. (b) If you can, do the same but this time requiring that every edge be traversed in both directions.

Due Tuesday Feb 19: Look up the exponential and Poisson distributions, and see if you can verify the memorylessness property of either or both.

Due Thursday Feb 28: Prove that an exponential lightbulb with expected lifetime x will outlast one with expected lifetime y with probability x/(x+y). (This can be done using calculus, or, better, just the memorylessness property of the exponential distribution.)

Due Tuesday March 5: Figure out what the triangle handout is all about, and verify that it is correct!

Due Thursday March 7: Let p be between 1/2 and 1. Start a token at 1 on the path from 0 to m and let it take a biased random walk until it hits 0 or m. Prove that the expected time to reach m, given that it hit m before 0, is the same if the walk is biased p to the right, as it is if it is biased p to the left.

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.