Processi Stocastici A.A. 2022-2023

Testo Primo Appello
Soluzioni Compito
Testo Secondo Appello
Testo Terzo Appello
Soluzioni Terzo Appello
Testo Quarto Appello

Sesto appello: 30 Gennaio 2024.
Ore 09:00, Aula II, Dipartimento di Matematica Guido Castelnuovo.

Descrizione prova d'esame e programma del corso



Link vademecum per studenti per compilazione questionari
Codice Opis del corso: SMQ8HRGK

Appunti (scritti a mano) su Teoria delle Reti + note lezione tempi di Mixing

Eserciziario

Testi di riferimento:
1. Markov Chains, J.R. Norris,  University of Cambridge  (Capitoli 1-3)
2. Markov Chains and Mixing Times, D. A. Levin and Y. Peres, American Mathematical Society (Capitoli 1-7)
3. Probability on Trees and Networks, Lyons and Peres, Cambridge Series



Lezione 1 (28 Febbraio 2023)
Introduzione al corso e informazioni pratiche. Definizione di catena di Markov, caratterizzazione di catena di Markov finita.
Esercizio: completare dimostrazione sulla caratterizzazione di catena di Markov finita.

Lezione 2 (3 Marzo 2023)
Proprietà di Markov (Thm 1.1.2, Norris), distribuzione della catena dopo un numero arbitrario di steps (Thm. 1.1.3, Norris), struttura di classi (Thm. 1.2.1), esempio.
Esercizio: dimostrazione prima parte Thm.1.1.3, esercizi 1.2.1 e 1.2.2 sul libro Norris. 

Lezione 3 (6 Marzo 2023)
Probabilità di arrivo, tempi di arrivo, rovina del giocatore, tempi di arresto.
Esercizi 1, 2, 3, 4 dell'eserciziario. Gli esercizi possono essere consegnati il 14 Marzo e sono facoltativi, andrebbero risolti in gruppi di tre.

Lezione 4 (10 Marzo 2023)
Proprietà di Markov forte, problema dell'uscita dall'insieme, problema delle visite nell'insieme.
Esercizio: trovare controesempio per il problema dell'uscita dall'insieme.

Lezione 5 (14 Marzo 2023)
Problema del collezionista (Levin-Peres), Stati ricorrenti e stati transienti (Norris), teorema sulla dicotomia e lemmi ausiliari (Norris).
Esercizio: dimostrare lo step 1 nella dimostrazione del problema del collezionista.

Lezione 6 (17 Marzo 2023)
Dimostrazione teorema sulla dicotomia, la ricorrenza è una proprietà di classe, ogni classe aperta è transiente, ogni classe finita chiusa è ricorrente, in una classe ricorrente tutti gli stati vengono visitati con probabilità uno.

Lezione 7 (21 Marzo 2023)
Il vettore gamma è una misura invariante se P è ricorrente e irriducibile,  le misure invarianti non nulle hanno tutte le coordinate positive, la misura gamma^k è quella minima tra tutte le misure invarianti che valgono uno sullo stato k se P è irriducibile ed è l'unica se P è anche ricorrente, se P è irriducibile e ricorrente tutte le misure invarianti sono tra di loro proporzionali.
Esercizi 6, 7, 8 eserciziario.

Lezione 8 (24 Marzo 2023)
Ricapitolazione, esistono stati positivamente ricorrente se e solo se esiste una distribuzione invariante, esempio sulla marcia aleatoria semplice simmetrica, esempio sulla marcia aleatoria semplice asimmetrica, il caso di catene irriducibili su spazio degli stati finito, esempio sulla striscia vincente. Stazionarietà di una catena di Markov. Definizione di stato aperiodico, e lemma sull'esistenza degli stati aperiodici.

Lezione 9 (28 Marzo 2023)
Convergenza all'equilibrio per spazio degli stati finito. Condizioni sufficienti perché il processo invertito sia una catena di Markov, definizione di processo reversibile e legge del bilancio dettagliato, equivalenza tra bilancio dettagliato e reversibilità, discussione di due esempi.
Esercizio: dimostrare claims 1, 2, 3 nella dimostrazione del teorema di convergenza all'equilibrio. 

Lezione 10 (30 Marzo 2023, + 30 min)
Marce aleatorie sulle reti, ogni marcia aleatoria sulla rete può essere vista come una catena di Markov reversibile e viceversa. Funzioni armoniche, caratterizzazione e unicità delle estensioni armoniche. Correzione esercizio 6 eserciziario.

Lezione 11 (14 Aprile 2023, + 15 min)
Reti associate a multigrafi, definizione di potenziale, flusso e flusso da A a Z, flusso elettrico. Proprietà del flusso elettrico e proposizione sulla legge dei cicli. Definizione di resistenza effettiva e proprietà di invarianza rispetto alla condizione di bordo. 
Esercizi: 9 (facoltativo), 10, 11, 12 eserciziario.

Lezione 12 (18 Aprile 2023, + 15 min)
Correzione esercizi 7, 8 eserciziario. Interpretazione probabilistica della resistenza effettiva e del potenziale.

Lezione 13 (21 Aprile 2023, + 30 min)
Interpretazioni probabilistiche della resistenza effettiva e del flusso di corrente quando il fulusso è unitario. Parallel law, series law, esempio di applicazione delle leggi di riduzione.
Assegnazione esercizi 13, 14, 15 dell'eserciziario. 

Lezione 14 (28 Aprile 2023, + 15 min)
Glueing, esempio dell'albero binario, trasformazione Star-triangle, altri esempio di grafo finito. Altre leggi di ruduzione: l'aggiunta di "loops" e l'aggiunta di un vertice di grado uno e del corrispondente arco. Definizione di conduttanza e resistenza effettiva su grafi infiniti.
Assegnazione di esercizio in classe e di altri esercizi tratti dal libro Lyon-Peres su leggi di riduzione. 

Lezione 15 (2 Maggio 2023)
Conduttanza e resistenza effettiva su grafi infiniti e proprietà di transienza e ricorrenza. Automorfismi delle reti e proprietà dell'estensione armonica. Grafi a simmetria sferica, resistenza effettiva in grafi a simmetria sferica. 
Assegnazione esercizio su albero regolare. 

Lezione 16 (5 Maggio 2023)
Esercitazione in classe con diversi esercizi sulle reti (albero d-regolare con conduttanze a crescita esponenziale, catena di nascita e morte, grafo a stella con 4 catene di nascita e morte).

Lezione 17 (12 Maggio 2023)
La lezione consisterà nella partecipazione alla cerimonia di conferimento del dottorato Honoris Causa a Ingrid Daubechies.

Lezione 18 (16 Maggio 2023, + 20 min)
Spazio dei nodi e dei cicli, decomposizione ortogonale dei flussi, prima parte del principio di Thomson (aggiunta di archi), principio di Reyleigh.
Esercizio: completare la dimostrazione dell'ortogonalità dello spazio dei flussi e dello spazio dei cicli considerando il caso di un ciclo costituito da un solo arco su un loop.

Lezione 19 (19 Maggio, + 15 min)
corollari, seconda parte del principio di Thomson. Estensione del potenziale e del flusso di corrente a grafi infiniti e ulteriori condizioni necessarie e sufficienti per la ricorrenza.
Esercizi 16, 17, 18 dell'eserciziario.

Lezione 20 (23 Maggio, + 15 min)
Potenziale e flusso su grafi infiniti, criterio di Nash-Williams, proprietà di ricorrenza di Z1 e Z2.
Esercizio 19 dell'eserciziario.

Lezione 21 (26 Maggio, + 15 min)
Metodo dei cammini aleatori, Zd è transiente se d>2, grafi tra Z2 e Z3, algoritmo di Google.

Lezione 22, ultima lezione (6 Giugno, + 15 min)
Cenni sui tempi di Mixing, informazioni su prova scritta e orale, compilazione questionari OPIS.