Probability on graphs
Prerequisiti
The course is recommended starting from the fourth year of the corso ordinario, to which it is well suited due to the very limited technical prerequisites. However, it is also suitable for PhD students, given that the content is closely related to current research topics.
The prerequisites consist of the course "Elementi di Probabilità e Statistica" and the course "Probabilità"; some more advanced knowledge of stochastic processes (discrete- and continuous-time Markov chains, Gaussian vectors, Brownian motion) from the courses "Processi Stocastici" or "Istituzioni di Probabilità" may be useful but is not essential, as is some extremely basic knowledge of harmonic functions on R^n.
Programma
The course will explore various aspects of the behaviour of random processes on graphs, with an emphasis on the interplay between probabilistic and combinatorial techniques in producing surprising results rich in applications.
The main topics include:
- Random walks on graphs and their long-term behaviour; electrical network analogy, Pólya's theorem, the type problem;
- A dialogue between discrete and continuous: Donsker's theorem, Green's functions, harmonic measure, and Brownian motion;
- The discrete Gaussian free field;
- Uniform spanning trees and forests: Wilson’s algorithm, the matrix-tree theorem, and local limits;
- Percolation and related topics;
- Mixing times of Markov chains.
Obiettivi formativi
By the end of the course, students will be familiar with several central objects in modern and contemporary discrete probability (random walks, the Gaussian free field, uniform spanning trees, self-avoiding walks, percolation).
They will have learned some of the most important proof techniques and will be able to solve nontrivial exercises.
The course is also intended as a solid introduction for those interested in approaching research in these areas.
Riferimenti bibliografici
- Grimmett G. Probability on Graphs: Random Processes on Graphs and Lattices. 2nd ed. Cambridge University Press; 2018.
- Lyons R, Peres Y. Probability on Trees and Networks. Cambridge University Press; 2017.