News

This week: Wednesday 6/1 extended office hour, 1:00 - 3:30 (in Kemeny 231); Thursday 6/2 office hour 9-10 in Kemeny 231; no X-hour. Friday 6/3 help session with Prof. Winkler, noon in Kemeny 229; Final exam Sunday 6/5 in IR080, 3:00 - 6:00 (or 1:30 - 4:30 by arrangement).

A couple of riffle shuffle and exact mixing references: Bayer and Diaconis; Fast Mixing.

References for the "grade" and for hitting time with restarts: On Playing Golf with Two Balls; Hitting Times for Random Walks with Restarts; The Markovian Price of Information; and the book on the Gittins index (in its readable second edition) is J. Gittins, K. Glazebrook, and R. Weber, Multi-Armed Bandit Allocation Indices, 2nd Ed., Wiley 2011.

Bernardi's paper on his elementary proof of Rayleigh's theorem can be found here.

Lecture notes by Alistair Sinclair (a collaborator of Mark Jerrum's) on the graph-coloring Markov chain can be found here; Jerrum's paper is here. A nice survey on the whole problem is here.

The Bubley and Dyer paper where they apply path coupling to the problem of sampling random linear extensions can be found here.

Next in-class exam: Monday, May 9. There will be an optional X-hour this Thursday at 12:15, in the usual room, for review (no new material). There will also be a help session with Grant, at noon Friday May 6, in Kemeny 229.

Friday May 13 (not May 6!), our class will be in Haldeman 041 instead of in Irving.

A possibly helpful survey on random walk on graphs can be found here. Caveat: You may already have noticed that notation and terminology differ from book to book and paper to paper; for example, in the survey above, Lovasz uses the term "access time" for what we call "hitting time." The random walk research community has not, alas, converged on vocabulary; part of the problem is that the members of this community come from many different places, e.g., probability theory, graph theory, algorithms, operations research, and electrical engineering.

Reference for the commute time formula can be found here.

Reference for the "lollipop" graph having largest expected hitting time: here

*Due to some mix-up, the course is also known as COSC 49.01.

We will meet in the "10" slot, MWF 10:10-11:15.

Our assigned classroom is IR080, the larger of two classrooms in the Irving Energy Center, West Campus. (Enter, turn left, descend the stairs.)

Abstract

Random walk is simple and ubiquitous, both a fascinating topic in its own right and a powerful tool in mathematics and computer science.

In its simplest form, a token begins at 0 on the number line and at each tick of a clock, moves right or left one step according to the flip of a fair coin. How far does it get, on average, after n steps? Does it always return to 0, and if so, how long does it take?

What happens if we walk instead on the plane grid? Or on an arbitrary graph, perhaps with weighted edges? How can we use random walk to obtain approximate solutions to problems that are too hard to solve exactly? How is random walk used to study gambling, or to mimic an electrical network, or model the New York Stock Exchange?

In this course we begin with the fundamentals of random walk and go on to look at generalizations and applications.

Prerequisites: Mathematical background of a senior mathematics major or a beginning graduate student in mathematics or theoretical computer science, including a course in probability (e.g., MATH 20 or Math 60). If in doubt, please contact the instructor.

Here is an initial rough syllabus by weeks:

1. Random walk on the line

2. Random walk on a graph

3. Reversible Markov Chains

4. Electric Networks

5. Markov Chain Monte Carlo

6. Mixing Time and Approximation Algorithms

7. Rayleigh's Random Flight Theorem

8. Martingales and the Stock Exchange

9. Games and Other Applications

Classes

Room: Irving Energy Center, IR 080
Lectures: "10" slot, in particular: Monday, Wednesday and Friday 10:10 - 11:15.
X-hour: Thursdays 12:15 - 1:05 pm. Will be used only when so announced in class.

Staff

Instructor:

Pete Winkler -- Kemeny Hall 231
Office Hours: Tue 9-10, Wed 2-3, Thu 9-10. Bring a mask!
email: peter.winkler@dartmouth.edu

TA:

Grant Molnar -- Kemeny Hall 245
email: grant.s.molnar.gr@dartmouth.edu

Textbooks

Peter Doyle and Laurie Snell, Random Walks and Electric Networks, here; David Aldous and James Allen Fill, Reversible Markov Chains and Random Walks on Graphs, here.

Grading

Your grade will be based on homework, class participation (attendance is expected!), midterms, and a final exam.

Exams

There will be in-class exams on Monday, April 18 and Monday, May 9. Let your instructor know in advance if you antipate a conflict. The final exam will be held on the assigned day and time for "10" slot classes, namely, 3 pm Sunday June 6.

Homework

Homework will be assigned at each class period, due on paper at the beginning of the next class. If you can't make it to class (e.g., on account of COVID quarantine), let the instructor know, and you will be able to email a PDF of your homework to the instructor and the TA. Late homeworks will be checked off but not graded.

Assignments

Due Wednesday March 30: You begin with $10 and each minute, you bet $1 (at even odds) on a coinflip. You quit when you run out of money or build up to $100. What is your probability of winning? How long do you expect to be playing?

Due Friday April 1: Let the graph G consist of a clique (complete subgraph) of size cn, with a path of length (1-c)n attached at one end of the path. Assume that n is large and compute the constant c that maximizes the expected hitting time of a simple random walk that begins in the clique and terminates at the far end of the path.

Due Monday April 4: At time 0 you turn on two light bulbs; one has expected lifetime x hours, the other y hours. Each lifetime is exponentially distributed. The correct formula for the density of an exponential variable of mean mu (at the point t) is (1/mu)e^{-t/mu}. Your mission is to show that the probability that the x-bulb outlasts the y-bulb is x/(x+y). To do this you may use calculus, experiment, or reasoning. The latter can be based on the fact that the lifetimes are memoryless, i.e. if a lightbulb is still burning at time t, its lifetime going forward from there is no different from what it was at time 0.

Due Wednesday April 6: Use the Central Limit Theorem to get as good an estimate as you can for the probability that, in 100 flips of a fair coin, the number of Heads you get is between 50 and 60, inclusive. You can use the web to look up the meaning of, and values for, the "error function" associated with the standard normal distribution.

Due Friday April 8: Compute the expected cover time for simple random walk on the path whose vertices are numbered 0 through n, if the walk begins at vertex k.

Due Monday April 11: Read Doyle and Snell through 1.1.5. Let W be a random walk on the path whose vertices are numbered 0 through n, and which is biased in the sense that at any interior vertex, the probability of stepping to the right is p (and thus, to the left, 1-p). Suppose W is modeled by an electric network whose voltage at vertex k is the probability that when W starts at k, it hits n before it hits 0. What should the resistances be?

Due Wednesday April 13: Read Doyle and Snell 1.1.6 through 1.2.5. Compute the effective resistance between antipodal vertices of a wire cube having resistance 1 on each edge.

Due Friday April 15: Let G be the cycle on 12 vertices numbered 0 through 11. (1) What is the probability that a simple random walk on G, begun at 0, reaches 6 before it returns to 0? (2) Same question, but with the edge between 9 and 10 removed (so that G is now a path).

Due Wednesday April 20: The broom graph B_n consists of a star with n leaves, plus a path of length n attached to the star's hub. Thus B_n is a tree with 2n+1 vertices, of which n+1 are leaves. What is the expected commute time C(h,y) = H(h,y) + H(y,h) between the hub h and the vertex y at the far end of the path? And: without calculating them, which of H(h,y) and H(y,h) do you expect to be greater?

Due Friday April 22: You take a simple random walk on K_3 (vertices 0, 1, and 2, connected in a triangle), beginning at vertex 0. Use math or experimentation to compute the probability that you are back at 0 after exactly 2 steps. How about 3 steps? 4? What is happening here, and how fast is it happening?

Due Monday April 25: Let A be the partially ordered set with points a, b, c, and d, and relations a < c, a < d, and b < c. (This is known as the "N" poset, on account of the shape of its Hasse diagram.) Draw the graph whose vertices are the linear extensions of A, with two vertices adjacent if the corresponding linear extensions differ by an adjacent transposition.

Due Wednesday April 27: A random-to-random shuffle constitutes removing a random card and sticking it back in in a random place (so, if there are n cards, there are n^2 ways to do this). As a function of n, what is the diameter of the state graph? Equivalently: what is the least number D such that you can get from any state to any other in at most D steps?

Due Friday April 29: Let M be the Markov chain whose states are the independent sets of a fixed finite graph G. You can think of an independent set as a function s from the vertices V of G to {0,1}, where if x and y are adjacent vertices, s(x) and s(y) can't both be 1. A step of M is made by choosing a vertex u of G uniformly at random, and flipping a fair coin. If "tails," s(u) is set to 0; if heads, s(u) is set to 1 if allowed, otherwise it is reset to 0. Show that M is reversible.

Due Monday May 2: To do Glauber dynamics for the hard core model (random independent sets) with "fugacity" λ on a graph G, choose a vertex of G uniformly at random, then flip a coin whose probability of heads is λ/(1+λ). If it comes up "heads," set the spin of the vertex to 1 if possible. If "tails," set it to 0. Show that this is a reversible Markov chain, and determine its stationary distribution (up to a constant factor).

Due Wednesday May 4: Show that the state graph for Δ+2-colorings of a graph with maximum degree Δ is connected; that is, you can get from any coloring by a fixed set of q = Δ+2 colors to any other such coloring, by changing the colors of vertices one at a time, never allowing two adjacent vertices to have the same color. Use your proof to get an upper bound on the diameter of the state graph, in terms of n and q.

Due Friday May 6: Recall that to do Glauber dynamics for the hard core model (random independent sets) with fugacity λ on a graph G, choose a vertex of G uniformly at random, then flip a coin whose probability of heads is λ/(1+λ). If it comes up heads, set the spin of the vertex to 1 if possible (that is, if no neighbors have spin 1). If tails, set it to 0. Your mission for Friday: use path coupling to find a condition for λ under which this chain mixes in polynomial time, given that G has maximum degree 4.

Due Wednesday May 11: Suppose you are given a connected, non-bipartite, d-regular state graph S and a probability distribution μ on the vertices (states) of S. You run a Markov chain on S in the following way. If you're currently in state i, choose a neighbor j uniformly at random. If μ_i ≤ μ_j, go to j. If μ_i > μ_j, go to j with probability μ_j/μ_i, else stay at i. Show that this chain is reversible, and its stationary probability is μ.

Due Monday May 16: Let G be a graph with n vertices, and let Ω be the graph of independent sets of G (in which i is adjacent to j if they differ at exactly one vertex). Add loops to Ω so that it becomes regular (of degree n). Then simple random walk on Ω will have uniform stationary distribution. But suppose instead that what you want is that the stationary probability of i is proportional to λ^|i|, where λ is some fixed real number greater than 1, and |i| is the size of the independent set i. We have two ways to make such a chain on Ω: via updates, where a vertex u of G is chosen u.a.r. and updated using a coin that flips heads with probability λ/(λ+1), or via the Metropolis-Hastings algorithm. Do these give the same Markov chain? If not, how do they differ?

Due Wednesday May 18: Let u and v be vertices of a finite connected graph G, with unit resistance on every edge. When does adding an edge to G not decrease the effective resistance R_uv between u and v?

Due Friday May 20: Let T_d be the (infinite) regular tree of degree d. Choose any vertex to be the "root" u, and let S_n be the set of vertices at distance n from u. Short S_n out with a resistance-free wire, and compute the effective resistance from u to S_n, which is now in effect a single vertex.

Due Monday May 23: Read 2.2.3 through 2.2.10 in Doyle and Snell, and write your answer to the following hypothetical question. If there were such a thing as simple random walk on the two-and-a-half dimensional grid, would it be recurrent or transient? Why?

Due Wednesday May 25: Let u and v be two vertices at distance 3 apart in the d-regular tree T_d. Compute the expected hitting time with restarts from u to v.

Due Friday May 27: Compute the grade of the vertices (2,0) and (1,1) in the plane grid, with the origin as target.

Due Wednesday June 1: Find a stopping rule for the top-to-random shuffle that gets you from any state to the stationary (uniform) distribution. How many shuffles does your rule require on average? Apply the halting state test to determine whether your rule is optimal.

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!

Notification to Student re Recording

(1) Consent to recording of course meetings and office hours that are open to multiple students. By enrolling in this course, a) I affirm my understanding that the instructor may record meetings of this course and any associated meetings open to multiple students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, within any digital platform, including those used to offer remote instruction for this course. b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth. (2) Requirement of consent to one-on-one recordings: By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any one-on-one meeting with the instructor or another member of the class or group of members of the class without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including separation from Dartmouth, as well as any other civil or criminal penalties under applicable law. I understand that an exception to this consent applies to accommodations approved by SAS for a student’s disability, and that one or more students in a class may record class lectures, discussions, lab sessions, and review sessions and take pictures of essential information, and/or be provided class notes for personal study use only.

If you have questions, please contact the Office of the Dean of the Faculty of Arts and Sciences.

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations that 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.