Welcome to the MATH 100-COSC 49/149 Web Page

Math 100/COSC 149 and COSC 49

Topics in Probability:
Discrete Models of Diffusion

Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)

Abstract | Classes | Staff | Textbooks | Grading | News and current assignment | Past assignments | Exams | Honor Code


News

Final exam will be 8 am on Friday, Nov 16, in Kemeny 105. PW will have regular office hours this week (Nov 13 & 15), and Chris will hold a help session at 1pm Thursday Nov 15, in Kemeny 229.

Reference for random walk on a graph: here

Reference for firefighting in a Poisson forest: here

Reference for first-passage percolation: here

Abstract

How do things spread on a network? Examples: rumors or fake news on the web; contagious diseases in a population; liquid in a porous medium.

A famous model for the latter, called "percolation," will be our base and starting point. From there we proceed to variations such as first and last passage percolation, used in modeling spread of diseases, then broadcasting on a graph, and SIR models where we have recovery as well as infection.

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 see the instructor.

Here is an initial rough syllabus by weeks:

1. Percolation history and basics

2. Transitions and the critial point

3. Cluster size

4. Conformal invariance

5. Directed percolation

6. Coordinate percolation

7. First-passage: the shape theorem

8. Broadcasting on a graph

9. Infection and recovery models

Classes

Room: Kemeny Hall 105
Lectures: "10" slot, in particular: Monday, Wednesday and Friday 10:10 - 11:15.
X-hour: Thursdays (same room) 12:15 pm - 1:05 pm. Will be used only when so announced in class.

Staff

Instructor:
Pete Winkler -- Kemeny Hall 231
Office Hours: Tu 2:00 - 3:30; Th 10:15 - 11:45.
email: peter.winkler@dartmouth.edu
TA:
Chris Coscia -- Kemeny Hall 243
Office Hours: Mo 1:30 - 2:30.
email: christopher.s.coscia.GR@dartmouth.edu

Textbook

Bela Bollobas and Oliver Riordan, Percolation, Cambridge U. Press 2006.
Supplementary materials (for other models) will be supplied in class.

Grading

Your grade will be based on homework, class participation, two hour exams, and a final exam. Homework and grading might be slightly different for enrollees of MATH 100/COSC 149 and enrollees of the simultaneous undergraduate course, COSC 49. The hour exams will be given in class on Monday, Oct 1 and Monday, Oct 22; let me know immediately if you have any possible conflict. The final exam will be in the regular slot for MWF10 courses.

Quizzes

There may be unannounced in-class quizzes, just to make sure everyone is keeping up.

Homework

Homework will be assigned at each class period, due at the beginning of the next class.

Assignments

Due Friday Sept 14: Let r(p) = 2p2 - p4 + 2p3(1-p)2 be the reliability function computed in class. Either plot this (using your favorite software) and observe its symmetry about the point (1/2,1/2), or prove the latter by showing r(1-p) = 1 - r(p). (This should be handed in at the beginning of class.) Then, read the Preface and begin Chapter 1 of your text.

Due Monday Sept 17: Fix p and let u and v be sites (vertices) of the infinite square grid. Let |Cu| be the size of the open cluster containing u, and similarly for v. Use coupling to show that |Cu| and |Cv| have the same probability distribution.

Due Wednesday Sept 19: Compute θ(p) for the 3-regular tree, i.e., the Bethe lattice B3. Draw (roughly by hand, or accurately via software) the graph of θ(p) for p between 0 and 1.

Due Friday Sept 21: You begin a daily hunt for a certain pesky woodchuck. On unsuccessful days, you spend on average h hours hunting; on your successful day, though, you expect to spend only h/2 hours. Your probability of success on any given day is p. (1) What is the expected value of the total number of hours you spend hunting? (2) What is the expected value of the total number of hours spent hunting on unsuccessful days?

Due Monday Sept 24: Let Λ' be the result of altering a board Λ by replacing each bond with a "Vermont road lozenge." In other words, for each pair u~v of adjacent sites, the bond from site u to site v is replaced by five bonds connecting u, v, and two new vertices x and y with u~x, u~y, v~x, v~y and x~y. Find an equation tying the percolation threshold p'H of Λ' to the percolation threshold pH of Λ. Which is threshold is higher?

Due Wednesday Sept 26: Finish the argument that every oriented edge of B* has exactly one other starting at its head, by considering the cases where the other vertices in the box may not belong to either C or C.

Due Friday Sept 28: Show that an s-t switch network needs at least k2 bonds to be proof against fewer than k failures. In other words, let G be a graph with vertices s and t, having the property that if fewer than k edges disappear, there is always still a path from s to t; and if fewer than k edges become indestructible, destroying the rest of the edges of G will always separate s from t. Show that G has at least k2 edges.

Due Wednesday Oct 3: Suppose you are percolating at p = 1/2 on the bonds of a 3 by 2 rectangle (which is, by our agreement, only two bonds wide and one bond tall) in the plane grid Z2. Compute the probabilities of the following three events: H(R3,2), V(R3,2), and H(R3,2) ∧ V(R3,2). Verify that (as claimed by Harris' Lemma) the last of these is at least the product of the first two.

Due Friday Oct 5: We'd all like to get some idea of how h1/2(R2n,n) behaves as n increases. Choose one of the following: (A) Calculate h1/2(R4,2) and compare with h1/2(R2,1); (B) Write and run a program that computes h1/2(R2n,n) for small n; (c) Write and run a program that estimates h1/2(R2n,n) by running random examples. For any of these options it may be useful to remember that open/closed bond configurations on R2n,n correspond to uniformly random binary strings of length 4n2-3n (the number of bonds in R2n,n).

Due Monday Oct 8: Suppose that A1, A2,...,Ak are disjoint events with union A. Show that if P(B|Ai) > p for each i, then P(B|A) > p.

Due Wednesday Oct 10: Needing to get a message to a confederate in Pyongyang, you can hire either Agency A or Agency B. Agency A will try to send one agent who needs to cross one border. Agency B would send two agents, each of whom must cross two borders, but if only one gets to Pyongyang you're OK. The probability of a successful crossing of any border is p. For what values of p should you hire Agency B, to maximize the probability that your message goes through?

Due Monday Oct 15: Show that when percolation occurs in the Bethe lattice Bk, for k>2, there will (with probability 1) be infinitely many infinite components.

Due Wednesday Oct 17: Suppose the Red Sox meet the Dodgers in the best-of-seven game World Series of Baseball. Normally the Red Sox win any game independently with probability 60%, but when the Dodgers are behind in the series their probability of winning shoots up from 40% to 60%. What is the probability that the Red Sox win the World Series?

Due Friday Oct 19: Prove that if the distribution of τ is non-trivial, then the limiting rate μ(e1) for diffusion along the X-axis is strictly less than Eτ. You may want to use the fact that if for some n the expected value of T(0,ne1) is less than nEτ, the above conclusion follows. NOTE: "50 Years of First-Passage Percolation" can be found at https://arxiv.org/abs/1511.03262.

Due Wednesday Oct 24: Get an upper bound on μ(v) := limn → ∞ T(0,nv)/n for v = (1,1) and τ uniform on [0,1], by just looking at paths that stay as near as possible to the diagonal y=x.

Due Friday Oct 26: Suppose you are using Dijkstra's algorithm to try to compute B(t) for some fixed t, i.e., to try to identify all sites in first passage percolation (with some fixed passage distribution) that are reached from the origin by time t. When would you stop your algorithm, and how would you then show that you have the right answer?

Due Monday Oct 29: Show that two firefighters are enough to contain a fire that starts at one tree of the square grid.

Due Wednesday Oct 31: Let Gλ be the graph obtained by connecting two points of a Poisson process of density λ on the plane when they are at distance less than 1. Let λc be the critical density for Gλ to have an infinite component (thus, to need some firefighting). Use the fact that the critical probability for face percolation on the hexagonal lattice is 1/2 to get a upper bound for λc.

Due Friday Nov 2: Again, let Gλ be the graph obtained by connecting two points of a Poisson process of density λ on the plane when they are at distance less than 1. Without reference to face percolation on the hexagonal lattice, argue that if Gλ has average degree less than 2, it won't have an infinite component.

Due Monday Nov 5: Let C be a simple closed curve in the plane, enclosing an open set U. The internal diameter of U is the sup, over all pairs (P,Q) of points in U, of the inf of the lengths of all paths from P to Q that lie entirely in U. Show that the internal diameter of U is less than half the length of C. (Note that the internal diameter coincides with the ordinary diameter if U is convex, but otherwise may be greater.)

Due Wednesday Nov 7: For the triangular and hexagonal lattices, what directions are most and least efficient for travel? How efficient are they? Efficiency is determined by determining the ratio of graph distance to Euclidean distance, over long distances.

Due Friday Nov 9: (1) Compute the minimum number of initially sick cells needed to infect an a x b rectangle in the plane grid, in the bootstrap percolation model. (2) Prove your result!

Due Monday Nov 12: Alice and Bob each start with $100 and repeatedly bet $1 on coin flips. Alice bets on heads, which has probability p > 1/2; Bob's coin also comes up heads with probability p but he bets on tails. As it happens, both eventually run out of money. Which is more likely to have run out first?

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 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.