MATH 100 / COSC 149.9 and COSC 49.02*
Topics in Probability:
Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)
Abstract  Classes  Staff  Textbooks  Grading  News and current assignment  Past assignments  Exams  Honor Code
News 
This week: Wednesday 6/1 extended office hour, 1:00  3:30 (in Kemeny 231); Thursday 6/2
office hour 910 in Kemeny 231; no Xhour.
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, MultiArmed 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 graphcoloring 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 inclass exam: Monday, May 9. There will be an optional Xhour 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 mixup, the course is also known as COSC 49.01.
We will meet in the "10" slot, MWF 10:1011: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:


Classes 
Room: Irving Energy Center, IR 080 

Staff 


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 inclass 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 (1c)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 xbulb outlasts the ybulb 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, 1p). 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 randomtorandom 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 Δ+2colorings 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, nonbipartite, dregular 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 MetropolisHastings 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 resistancefree 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 twoandahalf 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 dregular 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 toptorandom 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 oneonone recordings: By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any oneonone 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. 69900, 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. 