Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2018/2019
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Docente Fagnola Franco
Cfu 8.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento

Obiettivi dell'insegnamento

The aim of this course is to provide a simple and accessible introduction to discrete and time-continuous Markov chains, the simplest mathematical model for random phenomena evolving in time, with applications to queueing models, biological models, Markov chain Monte Carlo, reliability. Moreover, a wide variety of models will be illustrated to provide the student with useful tools to apply the methods in new situations. A brief introduction to martingale theory and methods with applications to Markov chains will also be given.

Risultati di apprendimento attesi

Learn the fundamental mathematical models with discrete and continuous time Markov chains and martingale methods. Learn the constructive mathematical proofs of some key result of the theory. Understand the key structures underlying Markov chain models.

Analyze random phenomena discriminating those that can be described by Markov chains and design the corresponding models with a correct scientific approach.  Develop new ideas and solutions to find quantitative rigorous solutions in new situations creating new models.

Acquire the ability to present in a clear and precise way the models and results of the theory.

Argomenti trattati

1. DISCRETE TIME MARKOV CHAINS. Markov chains, classes of states and their structure, periodicity, transience and recurrence. Random walks, recurrence and transience of random walks, binary communication channels. Invariant distributions. Recurrence and transience. Stopping times and strong Markov property.  Hitting times and absorption probabilities. Mean absorption times. Application to ruin problems (ruin probability and mean ruin time). Empirical means and ergodic theorem. Reversibility. Applications to queueing models and population models. Lyapunov functions and Foster criteria. Exponential convergence to invariant distributions and Doeblin condition. Monte Carlo methods, Metropolis algorithm, binomial model.

2. CONTINUOUS TIME MARKOV CHAINS. Consistent families of probability distributions, Kolmogorov’s theorem, canonical processes. Trajectories and modifications. Transition rates, Chapman-Kolmogorov equation and transition semigroup, forward and backward Kolmogorov equations. Transition rate matrices and their exponentials. Markov property and exponential sojourn times, jump chain and holding times of a continuous time Markov chain. Invariant distributions, ergodic theorem and convergence to invariant distributions. Poisson process, independence of increments. Birth and death processes. Non-minimal chains and explosion in finite time. M/M/1 and M/M/k queues and performance indices.

Renewal processes: law of large numbers and central limit theorem. Failure rate and reliability.

3. MARTINGALES. Martingales, supermartingales and submartingales. Modelling a player’s fortune. Filtrations and information. Predictable processes and predictable strategies. Discrete time stochastic integrals and return of a strategy. Stopping theorem. Maximal inequality and Doob inequality. Martingales of a Markov chain, Lyapunov functions and submartingales.

Results will be presented in a rigorous way. However, only proofs deemed useful for understanding structures or clarifying models and methods will be discussed in detail.


The only prerequisite is a first course in probability. Knowledge of basic measure theory would be an advantage, but it is not a prerequisite in the strict sense.

Modalità di valutazione

The final exam is made of a preliminary written test, followed by an oral test. In both stages of the exam the student will have to demonstrate: knowledge of definitions and concept and some of the main constructive mathematical proofs, skills in the identification and construction of Markov chain models in real-world situations, critical reasoning skills in the application of the learnt methods.  

The written test usually consists of 2 exercises, one on discrete time and the other on continuous time Markov chains, each one containing 4 – 5 questions. The candidate will be usually asked to construct the mathematical model that he will analyze to obtain quantitative information (probabilities, mean times …).

The oral exam consists of questioning on topics of the course. The candidate will be asked to illustrate some results with proofs from a part of the programme chosen by the candidate himself among: 1 discrete time Markov chains till the strong Markov property included, 2 discrete time Markov processes from hitting times and absorption probabilities, 3 continuous time Markov chains, 4 conditional expectation and martingales. Moreover, the candidate is supposed to be able to present rigorously, without proofs, all the results and models.

Risorsa bibliografica facoltativaJ.R. Norris, Markov Chains, Editore: Cambridge University Press, Anno edizione: 2012, ISBN: 9780511810633 www.cambridge.org/core/books/markov-chains/A3F966B10633A32C8F06F37158031739

pdf files of some chapters are available from the author's website www.statslab.cam.ac.uk/james/Markov

Risorsa bibliografica facoltativaF. Fagnola, Continuous-time Markov chains beep.metid.polimi.it

Lecture notes available on Beep

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
Ore di studio autonome
Laboratorio Informatico
Laboratorio Sperimentale
Laboratorio Di Progetto
Totale 80:00 120:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.5 / 1.6.5
Area Servizi ICT