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.
Unit 1. Introduction (notes)
Unit 2. Non-commutative probability spaces (notes)
Unit 3. Measure Theory 101 (notes)
Unit 4. Complex analysis 101 (notes)
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
Unit 13. Finite free probability
Unit 14. MSS's Ramanujan graphs
Unit 15. Further topics (time permitting)
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
Lecture 6. Kreweras Complement & Factorization in NC; The Incidence Algebra
Recitation 6