Fall 2022 Seminar

This is the homepage for the UC Berkeley Student Probability Seminar, a venue for graduate students in the departments of mathematics, statistics, and others to study aspects of modern probability theory. We meet on Wednesdays in Evans 891 from 2:00 PM - 3:00 PM

Organizers: Ella Hiesmayr and Adam Quinn Jaffe.

The topic for this semester's seminar is the large deviations on random graphs. Near the beginning of the semester we will primarily follow standard sources on classical large deviations theory, like Dembo and Zeitouni [DZ] and den Hollander [dH], and in the middle of the semester we will follow some standard texts on random graphs and graph limits like Lovasz [L]. Our general structure will follow the textbook by Chatterjee [C]. The list of talks and abstracts can be found below.

• 24 August, Initial meeting.
• A casual first meeting to get to know each other and decide on a topic for the semester.
• 31 August, Ella Hiesmayr, Introductory Talk.
• We introduce the basic questions motivating the theory of large deivations for random graphs. Specifically, we describe how the fundamental ideas of classical large deviations theory do not apply to the setting of random graphs, because of the lack of independence and linearity.
• 7 September, Adam Quinn Jaffe, Crámer's Theorem, DZ Chapter 2.2 and dH Chapter I.3
• In this talk we will prove a simple but important result of large deviations theory called Crámer's theorem. Roughly speaking, it states that empirical averages of i.i.d. random variables concentrate exponentially fast around their common mean, and that the exponential rate of convergence is related to the Fenchel-Legendre transform of their common logarithmic moment generating function.
• 14 September, Neo Yin, Proof of Sanov's Theorem, DZ Chapter 2.1 and dH Chapter I.4
• This week we are going to prove Sanov's Theorem on a discrete finite alphabet. Sanov’s Theorem establishes the relative entropy (a.k.a. Kullback-Leibler divergence) as the large deviation rate function for the random empirical measure of iid sampling.
• 21 September, Rikhav Shah, Probabilists love them: Upper bound the rate function using any one of these three easy tricks, C Chapter 4 and DZ Chapter 4.2
• We'll start by taking a step back to get an intuitive grasp on what the technical definitions of "large deviation principle" and "good rate function" really are. This will lead directly to our first trick: bounding the rate function locally is enough to bound it globally. Then, we generalize the classic Chernoff inequality to arbitrary vector spaces using the Fenchel-Legendre transform, giving a bound on the rate function that is often optimal. Finally, we show how to transfer LDPs from one space to another; combined with Sanov's theorem this immediately gives the rate function for many distributions of interest.
• 28 September, Karissa Huang, An Introduction to Graphons, C Chapters 3.1, 3.2, and 3.3
• In this talk we summarize some basic results from graph limit theory. In particular, we will introduce graphons and homomorphism densities. Then, we will equip the space of graphons with an appropriate metric (the cut metric), which induces a metric on the space of equivalence classes of graphons. These results will allow for the rigorous analysis of limits of finite graph sequences.
• 05 October, Yang Chu, Samplings of graphons, L Chapters 10.1, 10.2, 10.3, and 10.4
• We give two schemes of sampling of graphons. One can either view graphons as weighted graphs with nodes as [0,1], or, roughly speaking, a collection of clusters of nodes with random bipartite structure between them. We also investigate finite-sample concentration of homomorphism densities under sampling visa standard concentration of measure methods, and give estimates of cut metric based on these sampling schemes.
• 12 October, Neo Yin, Compactness of graphon space, L Chapters 9.1, 9.2, and 9.3
• In this talk, we will prove that the (quotient) space of graphons equipped with the cut metric is compact, using the regularity theorems.
• 19 October, Gabriel Ramirez Raposo, Some properties of the rate function, C Chapters 5.1 and 5.2
• We introduce the rate function used in large deviation bounds for random graphs. We will show a nice representation of the rate function in terms of a supremum of operators in the set of L2 functions and prove that the rate function is lower semicontinuous in the space of graphons.
• 26 October, Zack McNulty, The large deviations upper bound, in the weak topology, C Chapter 5.3
• In this talk we prove a large deviation upper bound for the probability measure on the space of graphons induced by the Erdős–Rényi model. We show on weakly closed sets that a natural extension of the binary relative entropy function acts as the desired rate function with rate 2/n^2. As the cut topology on W acts as an extension of the weak topology, this result will be a stepping stone towards proving a similar result on the quotient space of graphons.
• 02 November, Mriganka Basu Roy Chowdhury, The large deviations upper bound, in the cut topology, C Chapter 5.4
• Last week we saw the proof of the upper tail in the weak topology. This week we extend the proof to the cut topology on the graphon space, with the same rate function. This is (half of) the LDP result proved by Chatterjee-Varadhan in their seminal 2011 paper.
• 09 November, Jorge Garza Vargas, The large deviations lower bound, C Chapter 5.4
• We will prove the lower bound in the LDP for the Erdős–Rényi model on the graphon space equipped with the cut metric (the rate function will be the usual one). As in last talk, the idea is to reduce the problem to proving a local statement for any graphon h in W. Then, the key idea in showing the local statement will be to tilt the Erdős–Rényi measure towards h in some judicious manner, and showing that the relative entropy of this new measure with respect to the Erdős–Rényi measure, in the limit, is precisely the rate function at h.

The remainder of the talks were canceled in solidarity with the academic workers' strike over contract negotiations. Thanks for the great semester, everyone!