View syllabus
NUMERICAL METHODS FOR MARKOV CHAINS.
BEATRICE MEINI
Academic year2021/22
CourseMATHEMATICS
Code148AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
METODI NUMERICI PER CATENE DI MARKOV/aMAT/08LEZIONI42
BEATRICE MEINI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Lo studente che ha superato l'esame con successo ha acquisito conoscenze in merito a questioni computazionali e applicative legate a catene di Markov e teoria delle code. In particolare, e' in grado di applicare algoritmi specifici e avanzati per la risoluzione numerica di catene di Markov.

 

Knowledge

The student who successfully completes the course will have the ability to to know computational and applicative issues related to Markov chains and queueing theory. In particular, he/she will be able to apply advanced algorithms for the efficient numerical solution of Markov chains

Modalità di verifica delle conoscenze

La verifica delle conoscenze verra' effettuata durante l'esame orale finale

Assessment criteria of knowledge

The knowledge will be verified during the exam sessions

 

 

 

 

Capacità

Al termine del corso lo studente sara' in grado di risolvere numericamente problemi computazionali legati a matrici non negative e catene di Markov

Skills

At the and of the course the student will be able to numerically solve computational problems related to nonnegative matrices and Markov chains.

Modalità di verifica delle capacità

Nell'esame orale in forma di seminario, allo studente viene assegnato un argomento non affrontato nel corso, la cui comprensione richiede le capacita' acquisite durante il corso. Nell'esame in forma di orale classico, vengono fatte domande allo studente relative ai contenuti del corso.

Assessment criteria of skills

The student may choose between an oral presentation (seminar) and classical oral exam. With the oral presentation, to be made to the teacher and possibly the other students, the student must demonstrate the ability to approach a circumscribed research problem related to the contents of the course, and organise an effective exposition of the results. With the classical oral exam the student must demonstrate, by answering questions on theretical and numerical issues, to have acquired the skills presented during the course

 

Comportamenti

Lo studente acquisira' l'autonomia di affrontare problemi computazionali legati a matrici non negative e catene di Markov

Behaviors

The student will acquire the capability to deal with computational problems related to nonnegative matrices and Markov chains.

Modalità di verifica dei comportamenti

Nell'esame sotto forma di seminario lo studente affrontera' un agomento non trattato durante il corso. Nell'esame in forma di orale classico possono essere fatte domande specifiche per verificare l'autonomia

Assessment criteria of behaviors

In the exam in the form of seminar, the student will deal with a subject related with the contents of the course, but not explicitly treated. In the classical oral exam, the student will answer questions related to the contents of the course, to check the authonomy and the acquisition of skills.

 

Prerequisiti (conoscenze iniziali)

Nozioni elementari di calcolo delle probabilita', algebra lineare e analisi numerica

Prerequisites

Elementary probability, linear algebra and numerical analysis

Teaching methods

Delivery: face to face

Attendance: Advised

Learning activities:

  • attending lectures
  • participation in seminar
  • individual study
  • Laboratory work

 

Teaching methods:

  • Lectures
  • Seminar
  • laboratory

 

Programma (contenuti dell'insegnamento)

Richiami sulle catene di Markov, catene di Markov discrete, matrice di
transizione, classificazione degli stati, distribuzione stazionaria.

Proprieta' delle matrici non negative, teorema di Perron-Frobenius,
M-matrici.

Metodi diretti e iterativi per catene di Markov finite.

Modelli di teoria delle code, problemi di tipo M/G/1 e G/M/1, processi
Quasi-Birth-Death (QBD), struttura delle matrici di transizione. Caso
con numero di stati finito e infinito.

Rappresentazione funzionale di matrici di transizione infinite con struttura
M/G/1, G/M/1 e QBD. Algebra di Wiener, fattorizzazioni di Wiener-Hopf e
equazioni di matrici. La formula di Ramaswami.

Metodi numerici per catene di Markov infinite. Metodi di
iterazione funzionale, metodi di riduzione ciclica, metodi di
interpolazione. Tecniche di accelerazione.

 

Syllabus

Introduction to Markov chains and related computational problems. Theory of nonnegative matrices. Numerical methods for finite Markov chains. Markov chains of M/G/1 type. Numerical methods for infinite structured Markov chains, like M/G/1-type, Quasi-birth and death processes.

Bibliografia e materiale didattico

D.A. Bini, G. Latouche, B. Meini, Numerical
Methods for Structured Markov Chains, Oxford University Press 2005;

G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in
Stochastic Modeling, SIAM 1999;

W.J. Stewart, Introduction to the Numerical Solution of Markov
Chains. Princeton University Press, 1994.

Bibliography

Recommended reading includes the following books: D.A. Bini, G. Latouche, B. Meini, Numerical Methods for Structured Markov Chains, Oxford University Press 2005; G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, SIAM 1999; W.J. Stewart, Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1994.

Modalità d'esame

La verifica avviene mediante esame orale. Lo studente puo' scegliere di effettuare:

1. esame orale, con interrogazione sugli argomenti presentati durante corso

oppure

2. esame sotto forma di seminario, con argomenti legati ai contenuti del corso e non affrontati durante il corso.

Assessment methods

The exam is oral and the student can choose between:

1. classical oral exam, with specific questions  on the contents of the course

2. exam in the form of seminar, where the student will deal with a subject related with the contents of the course, but not explicitly treated.

 

Updated: 03/08/2021 15:50