Processi Stocastici
A.A. 2021-2022, laurea magistrale in matematica

Testo del primo appello e soluzioni
Testo del secondo appello e qualche risposta
Testo del terzo appello

L'anno accademico 2021-2022 è terminato nel mese di Gennaio 2023 e tale pagina non verrà più aggiornata.
. 

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

• Diario delle lezioni:
  
  Lezione 1  (1.3.2022)
  Organizzazione del corso, introduzione ai problemi trattati nel corso. Matrice stocastica e grafo associato, definizione catena di Markov, caratterizzazione equivalente di una catena di Markov finita.
  
  Lezione 2 (3.3.2022)
  Proprietà di Markov, distribuzione della catena dopo un numero arbitrario di steps steps, esempio, struttura di classi.
  Esercizi assegnati: 1.1.1, 1.1.2, 1.1.5  del Norris.
  
  Lezione 3 (8.3.2022)
  Esempi di classi, caratterizzazione della probabilità di arrivo, esempio, problema della rovina del giocatore.
  Esercizi assegnati: 1.2.1, 1.2.2 del Norris. 
  
  Lezione 4 (10.3.2022)
  Catena di nascita e morte, caratterizzazione del tempo medio di arrivo, proprietà di Markov forte.
  Esercizi assegnati: 1.3.1, 1.3.2, 1.3.4 del Norris e Esercizio 1 dell'eserciziario.
  
  Lezione 5 (15.3.2022)
  Proprietà di Markov forte, esempio sulla sotto-sequenza delle visite ad un certo insieme di stati, problema del collezionista.
  Esercizi assegnati: Esercizio 2 eserciziario.
  
  Lezione 6 (17.3.2022)
  Definizione di stati ricorrenti e transienti,  teorema della dicotomia,  la ricorrenza è una proprietà di classe,  ogni classe ricorrente è chiusa.
  
  Lezione 7 (22.3.2022)
  Discussione esercizio 1 Eserciziario, correzione esercizio su due dadi speciali e loro confronto tramite definizione delle due catene di Markov nello stesso spazio di probabilità. Dimostrazione del fatto che ogni classe chiusa finita è ricorrente. 
  Esercizi 1.5.1 e 1.5.2 del Norris. Esercizi 3 e 4 dell'eserciziario. 
  
  Lezione 8 (24.3.2022)
  Marce aleatorie su Zd (la marcia aleatoria semplice su Z è transiente se è asimmetrica e ricorrente se simmetrica, la marcia aleatoria semplice simmetrica su Zd è transiente se d>2 e ricorrente se d =1,2).
  Esercizi 5, 6, 7 eserciziario (non solo 5 e 6 come ho detto a lezione), esercizio 1.6.1 Norris
  
  Lezione 9 (29.3.2022)
  Altre considerazioni su marce aleatorie su Zd. Definizione di distribuzioni invarianti.  Equilibrio e stazionarietà delle distribuzioni invarianti. Il vettore gamma è una misura invariante.
  Esercizio 8 eserciziario.
  
  Lezione 10 (31.3.2022)
  Ogni misura invariante non nulla ha tutte le coordinate positive. Teorema sull'unicità della misura invariante che ha valore uno su un certo stato in caso di matrice stocastica ricorrente e irriducibile. Definizione di ricorrenza positiva e ricorrenza nulla. Equivalenza tra esistenza di una distribuzione invariante e ricorrenza positiva. Applicazione del teorema: la marcia aleatoria semplice simmetrica su Z è ricorrente nulla.
  Esercizi 9 e 10 eserciziario. 
  
  Lezione 11 (7.4.2022)
  Altri esempi su come dedurre proprietà di ricorrenza dalla caratterizzazione delle misure invarianti. Convergenza verso l'equilibrio, enunciato del teorema per spazi degli stati possibilmente infiniti oppure solo finiti,  dimostrazione nel caso di spazio degli stati finiti (senza dimostrazione claim).
  Esercizi: 1.7.1, 1.7.3, 1.7.5 del Norris, dimostrazione ultimo claim aiutandosi con il libro Levin - Peres.
  Nota: errore nell'ultimo minuto della lezione (nella scelta di n, k e a), corretto sulle note.
  
  Lezione 12 (21.4.2022)
  Condizioni sufficienti affinché il processo invertito sia una catena di Markov,  legge del bilancio dettagliato e invarianza di una distribuzione, la legge del bilancio dettagliato implica la reversibilità e viceversa, esempio di catena non reversibile,  esempio di catena reversibile, esempio della marcia aleatoria semplice sul grafo.
  Esercizio 1.9.1
  
  Lezione 13 (26.04.2022)
  Marce aleatorie sui gruppi, reversibilità e irriducibili, due esempi.
  Esercizi 2.6 e 2.7 del libro Levin and Peres.
  
  Lezione 14 (28.04.2022)
  Enunciato e dimostrazione del teorema ergodico.
  Esercizio 1.10.1 Norris.
  
  Lezione 15 (5.05.2022) (+ 15 min)
  Metodo Monte Carlo, Catena di Metropolis, algoritmo per la ricerca del massimo di una funzione, funzionamento dell'algoritmo di Google.
  
  Lezione 16 (6.5.2022, registrata)
  Correzione esercizio 7.Bis (e 3) 
  Correzione esercizio 6
  Correzione esercizio 1.6.1
  
  Lezione 17 (10.05.2022) (+ 10 min)
  Quattro formulazioni diverse della distanza di variazione totale, esempio, coupling tra distribuzioni.
  
  Lezione 18 (12.05.2022) (+20 min)
  Distanza dalla distribuzione stazionaria, proprietà di tale distanza. Tempo di Mixing per la "striscia vincente" invertita. 
  Esercizio 4.1 su Levin, Peres, due esercizi opzionali.
  
  Lezione 19 (16.05.2022, di recupero)
  Esempio di coupling di catene di Markov, stima dall'alto della distanza dalla stazionarietà utilizzando coupling di catene di Markov, tempo di Mixing della marcia aleatoria simmetrica pigra sul ciclo.
  
  Lezione 20 (17.05.2022) (+5min) 
  tempo di Mixing della striscia vincente, tempo di Mixing della marcia aleatoria simmetrica (pigra) sull'ipercubo. Definizione di marce aleatorie sulle reti, ogni catena di Markov reversibile può essere vista come una marcia aleatoria sulla rete. Caratterizzazione e unicità dell'estensione armonica di una funzione.
  Esercizio 1: dimostrare che i processi (X_t, Y_t) definiti a lezione sono dei couplings di catene di Markov. Esercizio 2: esercizio sulle marce aleatorie sulle reti assegnato a lezione. Esercizio 3: completare dettagli nella dimostrazione dell'ultima proposizione, come spiegato a lezione.
  
  Lezione 21 (19.05.2022) (-30 min)
  Definizione di rete con multigrafo, definizione potenziale, definizione di flusso, definizione di flusso da a a z, definizione di flusso di corrente. Proprietà del flusso di corrente. L'unico flusso  da a a z che soddisfa la legge dei cicli è il flusso di corrente.
  Esercizio: dimostrare due proprietà del flusso di corrente.
  
  Lezione 22 (24.05.2022) (+10 min)
  Resistenza effettiva, proprietà di invarianza rispetto alla condizione di bordo, interpretazione probabilistica della resistenza effettiva. Leggi di riduzione: series law, e parallel law, esempio.
  Esercizio 1: dimostrare che la variabile casuale N definita a lezione ha distribuzione geometrica. Esercizio 2: dimostrare claim nella dimostrazione della parallel law. Esercizio 3: dimostrare series law. 
  
  Lezione 23 (26.05.2022)
  Glueing, analisi dell'albero tramite leggi di riduzione. Definizione di spazio dei flussi, energia del flusso, spazi star e dei cicli, decomposizione ortogonale dello spazio dei flussi. Principio di Thomson.
  Esercizio: analisi della rete definita a lezione attraverso leggi di riduzione.
  Esercizi opzionali: dimostrare la proprietà di glueing, terminare la dimostrazione di ortogonalità dello spazi dei flussi e dei cicli.
  
  Lezione 24 (ultima lezione) (31.05.2022)
  Principio di Rayleigh, monotonia della probabilità di fuga, grafo ottenuto aggiungendo archi a Z3, processi di diramazione.