Modelli stocastici Markoviani
Argomenti svolti a lezione
Anno Accademico 2006/2007
-
Lezione 1 (5 marzo)
Presentazione del corso. Il programma, i testi, materiale didattico, modalità d'esame.
Descrizione del carattere del corso. Le due tematiche principali:
1) le catene di Markov finite, omogenee, e le loro proprietà ergodiche;
2) applicazioni algoritmiche (procedure di generazione casuale, conteggio approssimato,
ottimizzazione).
Cenni storici alle figure di Markov e Chebychev.
-
Lezione 2 (12 marzo)
Esempi semplici di modelli di catene di Markov: rovina del giocatore, moto di particelle su un segmento intero
(barriere riflettenti ed elastiche),
il modello di Bernoulli (liquidi incomprimibili in due contenitori),
il modello di Ehrenfest (scambio di calore tra corpi isolati),
passeggiata dell'ubriaco, passeggiata in grafi non orientati,
modelli di simulazione di giochi.
Definizione intuitiva di catena di Markov: l'insieme degli stati, lo stato iniziale, la matrice di transizione.
-
Lezione 3 (15 marzo)
Definizione assiomatica di catena di Markov. La sua consistenza e il legame con la nozione intuitiva.
Lo spazio delle traiettorie.
Matrici stocastiche, le proprietà dei loro autovalori e autovettori.
-
Lezione 4 (19 marzo)
Prime proprietà delle catene di Markov. Le equazioni di Chapman-Kolmogorov.
La distribuzione della n-esima variabile aleatoria,
la distribuzione congiunta delle prime n variabili.
Le potenze della matrice transizione; valutazione del numero medio di passaggi per un dato stato.
-
Lezione 5 (22 marzo)
Il calcolo delle potenze di un matrice di transizione: l'algoritmo divide et impera naive, la diagonalizzazione,
la funzione generatrice di Green, l'equazione di ricorrenza associata alle funzioni generatrici razionali.
-
Lezione 6 (26 marzo)
Simulazione di una catena di Markov. Tempi di prima entrata in uno stato, le relative probabilità,
i valori medi e le loro equazioni elementari.
-
Lezione 7 (12 aprile)
Grafi orientati e matrici non negative. Le relazioni di connessione in un grafo orientato.
Le classi di un grafo. Il grafo ridotto. Nodi essenziali. Il periodo di un nodo. Le matrici irriducibili.
Matrici irriducibili periodiche e aperiodiche. Matrici decomponibili e le forme triangolari a blocchi.
-
Lezione 8 (16 aprile)
Proprietà delle matrici irriducibili. La loro decomposizione ciclica. Le matrici primitive.
Esempi di matrici irriducibili che non sono primitive.
-
Lezione 9 (19 aprile)
Teorema di Perron-Frobenius per matrici primitive: la costruzione dell'autovalore di
modulo massimo, la positività e la molteplicità dei suoi autovettori.
-
Lezione 10 (23 aprile)
Espressione asintotica delle potenze di una matrice primitiva.
Il teorema di ergodicità per le catene primitive.
-
Lezione 11 (26 aprile)
Stati ricorrenti: definizione e proprietà iniziali. La probabilità di rientrare in un dato stato infinite volte.
Il legame tra la ricorrenza di uno stato e la probabilità di primo rientro.
La ricorrenza di uno stato e la convergenza della serie di Green associata.
La ricorrenza come proprietà delle classi.
-
Lezione 12 (3 maggio)
Equivalenza tra stati ricorrenti e stati essenziali nelle catene di Markov finite.
-
Lezione 13 (7 maggio)
Tempo medio di rientro in uno stato ricorrente.
-
Lezione 14 (14 maggio)
Proprietà della distribuzione stazionaria nelle catene irriducibili.
Calcolo di una distribuzione stazionaria a partire da uno stato ricorrente.
-
Lezione 15 (16 maggio)
Confronto tra le proprietà di ergodicità e le distribuzioni stazionarie in alcuni tipi
rilevanti di catene di Markov: primitive, mixing, irriducibili periodiche,
con più classi essenziali. Cenni alle catene con un numero infinito di stati:
le principali differenze rispetto al caso finito.
-
Lezione 16 (17 maggio)
Catene di Markov reversibili. Le catene di passeggiate casuali in un grafo.
La reversibilità delle catene di nascita e morte. Esempi di matrici bistocastiche
corrispondenti a catene non reversibili.
-
Lezione 17 (21 maggio)
Cenni ai metodi Monte Carlo e alla complessità del problema di minimo indipendent set.
Metodi Monte Carlo basati su catene di Markov (MCMC). Esempio guida: procedura per la generazione casuale uniforme
di un indipendent set in un grafo non orientato; proprietà della catena di Markov associata:
irriducibilità, aperiodicità, reversibilità.
-
Lezione 18 (23 maggio)
Campionatori di Gibbs tradizionali. Algoritmo MCMC per la generazione casuale uniforme di una q-colorazione di un grafo
non orientato. Proprietà della catena di Markov associata: aperiodicità e reversibilità.
Campionatori di Gibbs ciclici.
-
Lezione 19 (24 maggio)
Distanza tra distribuzioni di probabilità. Analisi dell'errore del campionatore di Gibbs per la generazione
di una q-colorazione casuale di un grafo.
-
Lezione 20 (28 maggio)
Cenni alla complessità di enumerazione. Schemi probabilistici di approssimazione polinomiale.
Algoritmo probabilistico per il calcolo del numero di q-colorazioni di un grafo:
descrizione della procedura e analisi della probabilità di errore.
-
Lezione 21 (1° giugno)
Introduzione a Pagerank: Google incontra Markov.
Lezione tenuta dal dr. Massimo Santini.