Probabilistic methods for informatics

A.Y. 2020/2021
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
Italian
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.
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).
Prerequisites for admission
Linear algebra, matrices, elements of probability theory.
It is strongly suggested 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/
- Class notes:
· M. Goldwurm, Catene di Markov e applicazioni algoritmiche,
Laurea Magistrale di Informatica, Università degli Studi di Milano, maggio 2018.
· M. Goldwurm, Compendio di calcolo delle probabilità,
dispense ausiliarie dedicate alle nozioni introduttive di probabilità e ad alcuni argomenti avanzati,
Università degli Studi di Milano, anno accademico 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.

An Ariel site of the present course is available at:
https://mgoldwurmmpi.ariel.ctu.unimi.it/v5/Home/
Assessment methods and Criteria
The examination consists of an oral exam aimed to verify the knowledge of the topics of the program, the comprehension of the methods for algorithm analysis included in the same program and the ability to apply the same techniques to simple new problems.
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Educational website(s)