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.

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 left-hand 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 in-class 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:

1. Random sequences, random subsets, Law of Large Numbers, Central Limit Theorem

2. Random systems, random graphs, Erdos and Renyi

3. Expectations; first moment method; second moment; new progress

4. The 0-1 Law, Fagin's proof and the Rado graph

5. Limit structures: subgraph frequencies, graphons, Razborov's scalloped triangle

6. Chatterjee & Varadhan's Large Deviations Principle; Radin and Sadun's landscape

7. Permutations and permutation patterns

8. Permutons and their Large Deviations Principle

9. Ulam's problem and the shape of random Young diagrams

Classes

Room: TBA
Lectures: 9L slot: Monday, Wednesday and Friday 8:50 - 9:55.
Classroom: Kemeny Hall 007.
X-hour: Thursdays 9:05 - 9:55. Will be used only when so announced in class.

Staff

Instructor:

Prof. Pete Winkler -- Kemeny Hall 231
Office Hours: Mon 2-3, Thu 10:30-11:30. email: peter.winkler at dartmouth.edu

TA:

Jamie Schmidt
email: James.A.Schmidt.GR at dartmouth.edu

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 in-class 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 two-part 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 n starting at the origin. Note that if the probability that the open cluster containing 0 is infinite is 0, then so is the probability that the open cluster at any other point (x,y) is zero; and thus the probability of percolation is bounded by the sum of 0 over all (x,y) which is zero.

Due Friday April 12: Let T_k,n be the k-branching tree of depth n (which has a root r and kⁿ 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,n-1.

Due Wednesday April 17: What fraction of a large box in the plane can be covered by disjoint unit-radius 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₁, u₂, . . . , u_k, and v₁, v₂, . . . , 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 first-order 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.

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