Probabilistic Methods for Informatics
A.Y. 2024/2025
Learning objectives
This course is devoted to study probabilistic tools and techniques used in general in different fields of Computer Science. In particular, a specific goal is to familiarize students with probabilistic methods and notions used in the design and analysis of randomized algorithms.
Expected learning outcomes
A first expected outcome is the knowledge of a set of probabilistic notions and methods used in designing algorithms and more generally in computational and informatics applications. Students will learn to make probabilistic arguments and proofs in Computer Science contexts. In particular, they are expected to learn to apply to new simple problems the probabilistic methods studied in the analysis of classical randomized algorithms.
Lesson period: Second semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
Second semester
Course syllabus
1. Elements of probability theory.
Discrete and continuous random variables, density and distribution functions, moments, classical examples.
Markov and Chebychev inequalities. Chernoff inequality and its applications. Generalities on stochastic processes. Introduction to Poisson processes.
2. Introduction to randomized algorithms.
Classification: Las Vegas algorithms, 1-sided error algorithms, bounded and unbounded error algorithms. Methods for reduction of error probability.
3. Graphs and matrices.
Oriented graphs and nonnegative matrices. Classification and periods of nodes.
Primitive and irreducible matrices. Period of irreducible matrices. Perron-Frobenius theorem. Stochastic vector and matrices.
4. Markov chains.
Finite and homogenous Markov chains. Classification of states. Recurrent and transient classes. Irreducible and aperiodic chains.
Time of first entry. Stationary distributions. Ergodic Markov chains and converge rate to the stationary distribution.
Reversible Markov chains. Random walks on graphs. Randomized algorithm for 2-SODD.
5. Algorithmic applications of Markov chains.
Non-uniform random generation and simulation of Markov chains.
Markov Chain Monte Carlo (MCMC). Gibbs samplers. Metropolis algorithm. MCMC algorithms for the random generation of independent sets and colorings of graphs.
Analysis of convergence speed to the stationary distribution: general case, coupling method, the example of graph colouring.
Introduction to randomized algorithms for approximate counting (graph colourings).
Discrete and continuous random variables, density and distribution functions, moments, classical examples.
Markov and Chebychev inequalities. Chernoff inequality and its applications. Generalities on stochastic processes. Introduction to Poisson processes.
2. Introduction to randomized algorithms.
Classification: Las Vegas algorithms, 1-sided error algorithms, bounded and unbounded error algorithms. Methods for reduction of error probability.
3. Graphs and matrices.
Oriented graphs and nonnegative matrices. Classification and periods of nodes.
Primitive and irreducible matrices. Period of irreducible matrices. Perron-Frobenius theorem. Stochastic vector and matrices.
4. Markov chains.
Finite and homogenous Markov chains. Classification of states. Recurrent and transient classes. Irreducible and aperiodic chains.
Time of first entry. Stationary distributions. Ergodic Markov chains and converge rate to the stationary distribution.
Reversible Markov chains. Random walks on graphs. Randomized algorithm for 2-SODD.
5. Algorithmic applications of Markov chains.
Non-uniform random generation and simulation of Markov chains.
Markov Chain Monte Carlo (MCMC). Gibbs samplers. Metropolis algorithm. MCMC algorithms for the random generation of independent sets and colorings of graphs.
Analysis of convergence speed to the stationary distribution: general case, coupling method, the example of graph colouring.
Introduction to randomized algorithms for approximate counting (graph colourings).
Prerequisites for admission
Linear algebra, matrices, elements of probability theory.
We suggest to pass the examinations of the courses of mathematics and probability theory of a computer science program at an undergraduate level.
We suggest to pass the examinations of the courses of mathematics and probability theory of a computer science program at an undergraduate level.
Teaching methods
The course is based on traditional lectures.
Teaching Resources
- Web page : http://users.mat.unimi.it/users/goldwurm/Metodi_probabilistici/
which will also include a link to the web site MyAriel of the present course for the new academic year.
Main text:
Massimiliano Goldwurm, Catene di Markov e applicazioni algoritmiche. Milano University Press, Gennaio 2024
(available at https://libri.unimi.it/index.php/milanoup/catalog/book/158).
Class notes (available at the sites above)
· M. Goldwurm, Compendio di calcolo delle probabilità (a brief summary of Probability Theory),
Università degli Studi di Milano, a.a. 2016/2017.
- References :
· B.V. Gnedenko, The theory of Probability, 6th edition, Gordon and Breach Science Publishers, 1997.
· M. Iosifescu, Finite Markov Processes and their Applications, John Wiley & Sons, 1980.
· O. Häggström. Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003.
· E. Seneta, Non-negative Matrices and Markov Chains, Springer-Verlag, 1981.
· W. Woess, Catene di Markov e teoria del potenziale nel discreto, Quaderni dell'U.M.I., Pitagora Editrice, 1996.
· M. Mitzenmacher, E. Upfal, Probability and Computing, Cambridge university Press, 2005.
· J. Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005.
which will also include a link to the web site MyAriel of the present course for the new academic year.
Main text:
Massimiliano Goldwurm, Catene di Markov e applicazioni algoritmiche. Milano University Press, Gennaio 2024
(available at https://libri.unimi.it/index.php/milanoup/catalog/book/158).
Class notes (available at the sites above)
· M. Goldwurm, Compendio di calcolo delle probabilità (a brief summary of Probability Theory),
Università degli Studi di Milano, a.a. 2016/2017.
- References :
· B.V. Gnedenko, The theory of Probability, 6th edition, Gordon and Breach Science Publishers, 1997.
· M. Iosifescu, Finite Markov Processes and their Applications, John Wiley & Sons, 1980.
· O. Häggström. Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003.
· E. Seneta, Non-negative Matrices and Markov Chains, Springer-Verlag, 1981.
· W. Woess, Catene di Markov e teoria del potenziale nel discreto, Quaderni dell'U.M.I., Pitagora Editrice, 1996.
· M. Mitzenmacher, E. Upfal, Probability and Computing, Cambridge university Press, 2005.
· J. Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005.
Assessment methods and Criteria
The examination consists of an oral exam aimed to verify the knowledge of the topics of the program and the comprehension of the methods presented for the analysis of probabilistic models and algorithm. We also aim to verify the ability to apply the same techniques to simple new problems.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor:
Goldwurm Massimiliano
Shifts:
Turno
Professor:
Goldwurm MassimilianoEducational website(s)
Professor(s)