MATH 100 / COSC 149.9 and COSC 49.02
(Topics in Probability)
The Shape of Large Random Systems
Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)
Abstract  Classes  Staff  Textbooks  Grading  News and current assignment  Past assignments  Exams  Honor Code
News 
It has come to my attention that it's not as easy as I thought to
find on the web answers to the exercises in Grinstead and Snell.
A set of answers that are "mostly correct" was sent to me by
Charles Grinstead and can be found
here.
Our final exam (for MATH 100, COSC 149.9, and COSC 49.02) will
be at 3 pm Saturday June 1, in the Bond Room (Kemeny 007).
here.
 
Abstract 
Large random structures occur frequently in mathematics, computer science, and statistical physics  these days, also in medicine, astronomy, and the social sciences. In this course we will be especially interested in systems that consist of a large number of simple, small components, that interact via a few rules (possibly none at all). Theoretically, a huge variety of things could happen; for example, all of the molecules of air in the classroom might suddenly find themselves in the lefthand half of the room. In practice, such unlikely behaviors are never seen. Indeed, one configuration of a large random system tends to look a lot like any other. For example, if you flip a fair coin 1,000 times, the good old Law of Large Numbers tells you that, with high probability, you will record about 500 heads. Here's a more shocking example that we will prove in class: two countably infinite random graphs will be isomorphic with probability one! In class we'll examine some powerful tools for dealing with random structures, and determining what they look like. The tools include expectations and moments, the Central Limit Theorem, and Large Deviation Principles; the systems include sequences, graphs, permutations, and in one case a random surface. Prerequisites: The mathematical sophistication of a beginning math
graduate student or advanced undergraduate math math major, or the same
for theory and algorithms in computer science. A basic acquaintance
with probability, as encountered in MATH 20 or COSC 70, will be assumed;
check with the instructor if you're not sure about whether your background
is sufficient for this course.
There will be daily (small) assignments, and inclass exams including
a final. You will see some proofs in class and occasionally be asked
to prove something not too complex. You will not be required to write
computer programs, but doing so will sometimes provide an alternative way
to do an assignment.
Here is a rough weekly syllabus:


Classes 
Room: TBA 

Staff 


Textbooks 
There is no official textbook for the course, but you will find some useful information in Alon and Spencer's The Probabilistic Method, PDF's of which can be found online (not necessarily the most recent edition, but that's OK). 


If you need to brush up on elementary probability, read Grinstead and Snell's Introduction to Probability, which is available online here at Dartmouth, along with Peter Doyle's solutions to the exercises therein. 

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 15 and Monday, May 6. Let your instructor know in advance if you antipate a conflict. The final exam will be held on the assigned day and time for "9L" slot classes. 

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 27: You flip a fair coin 10,000 times. What can be said about the length of your longest run, i.e., the largest k such that k heads in a row or k tails in a row appear in your outcome sequence? You may use math or do a simulation. Due Friday March 29: On average, how many rolls of a die does it take to see all six numbers? You may do the math, or do simulations and report the results. Due Monday April 1: 64 evenly matched teams are randomly bracketed and engaged in an elimination tournament. What is the probability that two particular teams (say, Dartmouth and Davidson) meet? You may do the math, or do simulations and report the results. Due Wednesday April 3: On average, how many rolls of a die does it take to get a 6, given that you don't roll any odd numbers en route? You may do the math, or do simulations (by rejection sampling!) and report the results. Due Friday April 5: Domino City occupies 6 islands in the Domino River, arranged like the pips on a die (or a domino). Islands A, B, and C, near the west bank, are connected by bridges to the west bank; D, E, and F to the east bank. Additional bridges connect the islands in a grid pattern: A to B, B to C, D to E, E to F, A to D, B to E, and C to F; 13 bridges in all. An earthquake is anticipated and the seismologists and engineers agree that each bridge will independently(!) collapse with probability 50%. What is the probability that, after the earthquake, it will still be possible to cross the river on the remaining bridges? (You may write a program to compute this, or to estimate it by random sampling; or, of course, you may try to solve it with mathematical reasoning.) reminder: Homeworks are due on paper at the beginning of each class. If you submit by email it must be before class, and should include the reason why you can't be in class. And don't forget the names of your collaborators! Due Monday April 8: Consider the following twopart experiment. First, choose a number p uniformly at random from the unit interval [0,1], and manufacture a coin whose probability of flipping "heads" is exactly p. Second, flip your coin 100 times. What is the probability that this experiment results in precisely 50 heads? (Note that your answer will not depend on p, since choosing p is part of the experiment.) You may use math or run your own computer experiments.
Due Wednesday April 10:
Prove that if p < 1/3, then the probability of bond percolation on the plane grid is zero.
You may want to use the fact that if the open cluster containing the origin is infinite, then
for every n there is an open path of length Due Friday April 12: Let T_{k,n} be the kbranching tree of depth n (which has a root r and k^{n} leaves). We will do bond percolation on T_{k,n}, meaning that each edge (bond) is open independently with some fixed probability p. Let P_{k,n} be the probability that there is an open path from r to some leaf (any leaf). Express P_{k,n} in terms of p and P_{k,n1}. Due Wednesday April 17: What fraction of a large box in the plane can be covered by disjoint unitradius disks? Due Friday April 19: Use the last homework to help you prove that any 10 points on the plane can be covered by disjoint unit disks. Due Monday April 22: Compute the expected number of monochromatic sets (cliques or independent sets) of size k in G_{n,1/2} . What can you conclude from your computation? Due Wednesday April 24: We know that the expected number of monotone subsequences of length k in a uniformly random permutation of order n is (n choose k) times 2/k!. For given large n, approximately what value of k will result in this expectation being equal to 1? What can you conclude from this about the expected length of the longest monotone subsequence in a random permutation of order n? Due Friday April 26: Fix a positive integer k and a probability p strictly between 0 and 1. Show that as n approaches infinity, the probability that G_{n,p} satisfies the kth Alice's Restaurant axiom φ_{k} approaches 1. The kth Alice's Restaurant axiom φ_{k} says that for any vertices u_{1}, u_{2}, . . . , u_{k}, and v_{1}, v_{2}, . . . , v_{k}, where no u_{i} is equal to any v_{j}, there's a vertex z that is adjacent to all the u_{i}'s and none of the v_{j}'s. Due Monday April 29: Express as a firstorder logic sentence the property that a graph is regular of degree 3, i.e., every vertex is adjacent to exactly three other vertices. Due Wednesday May 1: Find a graph property P (that is, a set of graphs that is closed under isomorphism) such that the limit as n approaches infinity of the probability that G_{n,1/2} satisfies P is a number strictly between 0 and 1. Due Friday May 3: Prove or argue or demonstrate experimentally that if V and W are exponential random variables with means a and b, respectively, then the probability that V > W is a/(a+b). In other words, an "exponential" light bulb with expected lifetime a will outlast one of expected lifetime b with probability a/(a+b). Due Wednesday May 8: Find two probability distributions such that if X has the first distribution and Y the second, and X and Y are independent, then X > Y with probability greater than 1/2, even though the expectation of X is less than the expectation of Y. No homework due Friday May 10: But you might want to refresh (or charge) your memory by glancing at Chapter 11 of Grinstead and Snell. Markov chains! Due Monday May 13: Estimate: (1) The expected number of pairs of multiple edges that will appear, for large n, with 3 stubs per vertex, when we pair up stubs uniformly at random; (b) the probability that the resulting graph G will have no multiple edges; and (c) the probability that G will have neither multiple edges nor loops. Your estimate can be derived either from math or from simulations. Due Wednesday May 15: Let P be (the transition matrix of) the Markov chain whose state space is the set of permutations of the numbers from 1 to 52, and whose transitions are as follows. Let (n_{1}, n_{2}, . . . , n_{52}) be the current permutation. Choose i uniformly at random between 1 and 51, and switch n_{i} with n_{i+1}. (This is called "random adjacent transposition.") Answer, with reasoning: Is P irreducible? Is P ergodic? Due Friday May 17: Let the graph G be a path of length n, on vertices 0, 1, 2, . . ., n. What is the maximum over all starting vertices k of the expected time for a simple random walk on G, starting at k, to hit every vertex of G? Due Monday May 20: Prove that our Markov chain on Δ+2colorings of a graph of maximum degree Δ is irreducible; i.e., show that for any two proper qcolorings of a finite graph G, where q=Δ+2, you can get from one coloring to the other by changing colors one vertex at a time. Note that every vertex always has at least two colors available to it, that is, unused by any neighbor. Due Wednesday May 22: A stream n_{1}, . . . , n_{1,000,000} of names is input to a computer that has only 1,000 registers to store names in. The following algorithm is executed: d ← 0, L ← emptyset. For i = 1, . . . , 1,000,000 do: L ← L \ {n_{i}}, then add n_{i} to the set L with probability 1/2^{d}. If L = 1000 do: Flip a coin for each element of L and remove it if "tails"; then, set d ← d+1. Output 2^{d} L. Question 1: What is this algorithm trying to approximate? Question 2: Why does it (probably) succeed? Due Friday May 24: Write a program to compute the entropy of the binomial distribution B(n,1/2) and run it for various n, comparing your answer to (1/2)log_{2} n. Or: Let k be a divisor of n, and calculate the entropy of the probability distribution on n values, the first n/k of which have probability (k1)/n each, the rest having probability 1/((k1)n) each. Due Wednesday May 29: Calculate the homorphism density of the path of length 2 (three vertices) in G_{n,p}.  
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 employ generative AI, e.g. ChatGPT, say so, and say how you verified that what it told you is correct. 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. 