Free Probability and Ramanujan Graphs
Spring 2024
About the course
Free probability is a mathematical theory that generalizes classical probability theory to the non-commutative setting. In the classical setting, random variables are often combined and studied using their joint distributions, which take into account the dependencies and correlations between them. In free probability, "freeness" is an abstract concept that describes a lack of correlations between non-commutative random variables.
Free probability theory is an exciting and growing field with deep connections to random matrix theory, quantum mechanics, and other areas. Closer to home, free probability, or more precisely a finite analog of it, was employed in a seminal sequence of works for the construction of bipartite Ramanujan graphs.
The mathematics of free probability is quite sophisticated, involving advanced concepts from functional analysis, operator algebras, and combinatorics. In this course, we will embark on an exploration of free probability theory, including both its infinite and finite manifestations, with a particular emphasis on applications in graph theory.
Technicalities
When and where
Lectures are on Tuesdays 10:10-13:00 at Check Point 380, and recitations by Gal Maor are afterwards, namely, Tuesdays 15:10-16:00 at Dan David 204.
Grade
Half of the grade will be based on approximately 6 homework assignments. Homework will be submitted in pairs if the number of participants is high enough. The other half of the grade will be based on a ~50-minute presentation to be given by each student at the end of the semester, covering a chapter from the Nica-Speicher book or a relevant paper.
Literature
We will mostly follow the great book Lectures on the Combinatorics of Free Probability Theory by Nica and Speicher. The latter author gave a fantastic course on the subject. The course website contains useful information and the lectures were recorded (audio quality is not great). For the finite free probability part we will cover original papers (see this video lecture by Spielman or that one by Marcus to get a sense for this part of the course). Last but not least, see Gal’s introductory lecture on free probability, aimed at theoretical computer scientists.
Tentative Syllabus & notes
Video lectures. The video lectures, presented in English, are regularly uploaded to the course’s YouTube channel.
Disclaimer regarding notes: My notes below are primarily intended to serve as a guide for my lectures. They are not comprehensive, and much of the information I will convey during the lecture is not included in these notes. However, you may still find them useful.
Introduction & mathematical background
Unit 1. Introduction (notes)
Unit 2. Non-commutative probability spaces (notes)
Unit 3. Measure Theory 101 (notes)
Unit 4. Complex analysis 101 (notes)
Free Probability Theory
Unit 5. A case study (notes)
Unit 6. Free independence (notes)
Unit 7. A central limit theorem (notes)
Unit 8. Basic combinatorics of non-crossing partitions (notes)
Unit 9. The Mobius inversion formula (notes)
Unit 10. Multiplicative functions (notes)
Unit 11. Free cumulants (notes)
Unit 12. Sum of random variables & free (additive) convolution (notes)
Finite Free Probability
Unit 13. Finite free (additive) convolution (notes)
Unit 14. The finite free convolution formula (notes)
Unit 15. Quadrature (notes)
Unit 16. Interlacing (notes)
Unit 17. MSS's one-sided Ramanujan graphs (notes)
Projects
The following are the book chapters (from Nica-Speicher) / papers you may choose from. Each student should list their top three choices in order of preference. Some of the projects are suitable for 2 students. If you want to pair up on a project please indicate that (otherwise I'll do that pairing, hopefully avoiding crossings :)).
-
Lecture 14 - Products of free random variables (two students).
-
Lecture 16 - The R-transform (two students).
-
Lecture 17 (keep in mind it builds on lecture 16) - The operation of boxed convolution (two students).
-
Lecture 22 - Gaussian random matrices (two students).
-
Lecture 23 - Unitary random matrices (two students).
-
Chapter 5 in these notes - The subordination function (one student).
-
Ramanujan graphs in polynomial time (two students).
-
Covering the symmetric multiplicative convolution & the asymmetric additive convolution from finite free convolution of polynomials. Note we covered the symmetric additive convolution in class (two students).
-
Interlacing families I: bipartite Ramanujan graphs of all degrees (two students). This is an earlier paper that uses some of the techniques we learned.
-
Applications to quantum algorithms (more precisely, this paper) (one student).
Video lectures
Lecture 1. Introduction
Lecture 2. Measure Theory 101
-
Measure Theory 101 - Sets of measure zero & "almost everywhere"
-
Measure Theory 101 - Lebesgue integrals for non-negative measurable functions
Alternatively, you can look at the live recoding from class.
Recitation 2 (recitation 1 wasn't recorded)
Lecture 3. Complex Analysis 101, a case study, and the Cauchy transform & Stieltjes inversion formula
-
Complex Analysis 101 - Holomorphic functions
-
An important correction: I defined a function as holomorphic at a point if the suitable limit exists. However, the correct definition states that a function is holomorphic at a point if there is a neighborhood of that point where the suitable limit exists for every point within that neighborhood.
-
Recitation 3
Lecture 4. Case study continued; Freeness
Recitation 4
Lecture 5. Free central limit theorem; Combinatorics of non-crossing partitions
Recitation 5
Recitation 5.5 (bonus)
Lecture 6. Kreweras Complement & Factorization in NC; The Incidence Algebra
Recitation 6
Lecture 7. Mobius functions & multiplicative functions
Recitation 7
Lecture 8. Free cumulants & the free additive convolution
Recitation 8
Lecture 9. The R transform; Kesten-McKay distribution; finite FPT
Lecture 10. The Finite R-transform theorem
Remark. This is more like 3/2 lectures in terms of length
Recitation 10 (there is no recitation 9)
Lecture 11. Quadrature, interlacing & Ramanujan graphs
Remark. This is more like 3/2 lectures in terms of length