Processi stocastici/Dinamiche su network (Dinamiche su Network)Conoscenze di: - elementi di base della teoria (topologica e algebrica) dei grafi diretti e indiretti con particolare enfasi sui concetti di centralità , connettività , periodo di un nodo, flussi su rete; - teoria delle matrici stocastiche e sub-stocastiche, delle loro proprietà spettrali e del loro uso nei modelli matematici deterministici e stocastici per dinamiche su reti; - nozioni fondamentali di ottimizzazione convessa di flussi su rete, della teoria dei giochi competitivi e delle relative dinamiche evolutive; - principali modelli di grafi aleatori e delle loro proprietà elementari. Capacità di: - costruire e comparare modelli matematici per sistemi interconnessi che nascono in reti sociali, economiche, biologiche e infrastrutturali; - applicare nozioni di base della teoria dei grafi topologica e algebrica, dei processi di Markov, della teoria dei giochi e dei sistemi dinamici per analizzare le reti ed i sistemi dinamici definiti su di esse; - individuare e valutare proprietà delle reti quali centralità , connettività , comportamenti emergenti, scalabilità ; - costruire algoritmi di tipo cooperativo su reti, di valutarne la velocità di convergenza e la complessità e di implementarli su moderne piattaforme per la simulazione numerica. Processi stocastici/Dinamiche su network (Processi stocastici)Al termine dell’insegnamento si chiederà allo studente di: - conoscere le definizioni di processi di conteggio, processi di Poisson omogenei e non omogenei, catene di Markov a tempo discreto e continuo, martingale, moto browniano. - conoscere le definizioni dei principali oggetti matematici associati ai processi stocastici elencati sopra, quali tempi di arresto, distribuzioni stazionarie, probabilita' di transizione, classificazione degli stati, etc; - conoscere gli enunciati dei teoremi base della teoria dei processi stocastici e comprenderne il significato; - conoscere le dimostrazioni di alcuni teoremi base della teoria dei processi stocastici e comprenderne i passaggi; - comprendere le modalità di sviluppo della teoria dei processi stocastici e relazionarla alle esigenze applicative: perché è stato enunciato un certo teorema? Come puo essere applicato ad un modello matematico concreto? - applicare la teoria base dei processi stocastici per risolvere esercizi; - applicare la teoria base dei processi stocastici in maniera critica per costruire, analizzare e confrontare modelli matematici di dinamiche aleatorie; - saper dimostrare in autonomia nuovi risultati pertinenti la teoria dei processi stocastici, ed essere eventualmente in grado di contribuire al suo sviluppo.
Processi stocastici/Dinamiche su network (Dinamiche su Network)L’insegnamento ha lo scopo di presentare gli elementi fondamentali della teoria dei grafi per arrivare allo studio di modelli matematici che descrivono dinamiche su network sia di tipo deterministico che aleatorio. Vengono descritti gli elementi di base della teoria dei grafi topologica e algebrica la teoria delle matrici stocastiche e alcuni elementi dei processi Markoviani Vengono poi considerati modelli di dinamiche su grafi sia deterministiche che probabilistiche. Sono infine discusse varie applicazioni: algoritmi su reti per stime e inferenze distribuite, modelli per la dinamica delle opinioni e modelli epidemici, modelli di teoria dei giochi.Processi stocastici/Dinamiche su network (Processi stocastici)I processi stocastici vengono utilizzati come modelli matematici negli scenari più disparati, dalla biologia alla finanza, dalla gestione di magazzino allo studio del traffico su internet, dalla medicina alla blockchain, dalla meteorologia all'ecologia. Questo corso, pur non potendo entrare nel dettaglio delle varie applicazioni, si pone l'obiettivo di fornire un'introduzione rigorosa alla teoria dei processi stocastici, con lo scopo di fornire le basi matematiche per la comprensione, la progettazione e l'analisi di tali modelli. Verranno definite ed esplorate formalmente le principali classi di processi stocastici, tra cui i processi di conteggio, i processi di Poisson, le catene di Markov, le martingale e il moto Browniano. Attraverso lo studio delle loro proprietà fondamentali, gli studenti acquisiranno sia una comprensione teorica che strumenti pratici per costruire e analizzare modelli di sistemi dinamici aleatori.
Processi stocastici/Dinamiche su network (Dinamiche su Network)1. Teoria dei grafi (topologica e algebrica) - Elementi di teoria dei grafi: cammini, cicli, connettività , distanza, diametro. Esempi. Grafi indiretti: proprietà ed esempi (completo, alberi, ciclo, griglie). Proprietà combinatorie degli alberi. Grafi bipartiti e loro proprietà . Circuiti euleriani. Componenti connesse di un grafo e concetto di condensation graph. Periodo di un nodo. Caratterizzazione dell'aperiodicità e relative proprietà . - Matrice dei pesi di un grafo e sue potenze. Matrici di grafi aperiodici. Matrice stocastica e Laplaciano associati ad un grafo. Il teorema di Perron-Frobenius. Proprietà spettrale delle matrici stocastiche. Centralità (degree, eigenvector, Bonacich, Pagerank, Katz). - Matrici stocastiche reversibili. Forma di Dirichlet. Formulazione variazionale per il calcolo del secondo autovalore di una matrice reversibile. Conduttanza e stima di Cheeger. Esempi. - Connettività e flussi su rete: teorema di Menger e teorema del massimo flusso / minimo taglio. 2. Dinamiche averaging e di flusso lineari - Modello di averaging distribuito e sistemi compartimentali per reti chiuse e con ingressi esogeni. - Teoremi di convergenza, ruolo della centralità , matrici bi-stocastiche. - Applicazioni: stima distribuita su reti, algoritmo Metropolis, dinamiche di opinioni (modello di De Groot), saggezza delle folle, modelli di influenza in reti sociali, dinamiche lineari di flusso su rete, algoritmi distribuiti per il calcolo della centralità . - Stima dei tempi di convergenza per matrici stocastiche reversibili: ruolo del secondo autovalore. Spettro di matrici circolanti e prodotto di Kronecker di matrici. Calcolo di spettri di matrici associate a grafi notevoli: grafo completo, anelli, griglie, ipercubi, stelle. - Matrici sub-stocastiche e loro proprietà . Velocità di convergenza per averaging distribuito e sistemi compartimentali con ingressi. - Sistemi dinamici positivi e monotoni: definizione e proprietà di base. 4. Catene di Markov - Richiami sui processi Markoviani a tempo discreto: stati assorbenti, tempi e probabilità di assorbimento, tempi di ritorno, teorema di Kac, catene ergodiche, misure invarianti. - Esempi notevoli: catene reversibili e catene di nascita e morte, cammini casuali su grafi. Processi di ramificazione (Galton-Watson): probabilità di estinzione, soglia di criticità , processi supercritici e subcritici. - Processi markoviani a tempo continuo e loro rappresentazioni, processi di nascita e morte a tempo continuo, equazioni di Kolmogorov, distribuzioni invarianti ed equazioni di bilancio. - Coupling, distanza variazionale, mixing time. 5. Ottimizzazione di flussi su reti - Ottimizzazione di flussi su reti con costi convessi separabili: condizioni necessarie e sufficienti per ottimalità , dualità , interpretazione dei moltiplicatori di Lagrange come costi marginali - Reti elettriche: interpretazione delle leggi di Ohm e Kirchoff, nozione di resistenza effettiva, principio variazionale di Rayleigh. Applicazioni alle catene di Markov reversibili e ai modelli di influenza su reti sociali indirette. - Ottimizzazione del traffico su rete: ottimo di sistema, equilibrio di Wardrop, prezzo di anarchia, uso di incentivi e disincentivi. Applicazioni alle reti di trasporto. 6. Teoria evolutiva dei giochi - Introduzione alla teoria dei giochi non cooperativi. Giochi in forma strategica, nozione di best response, strategie dominanti, equilibri di Nash. Esempi classici. - Giochi potenziali, giochi di congestione. - Giochi su reti. Esempi: majority, minority, colorazione di grafi. - Analisi delle dinamiche best response e noisy best response. 7. Modelli epidemici e di interazione a coppie - Modelli di interazione di tipo pairwise. - Algoritmi gossip di averaging. - Modelli epidemici (SI, SIS, SIR), voter model. - Calcolo di probabilità e tempi di assorbimento su topologie semplici (completo, linea, stella). - Modelli ergodici (noisy voter model, SIS con mutazioni spontanee). 8. Limiti di campo medio - Modelli di interazione su grafi completi con matrice di transizione di tipo anonimo. Esempi. Processo delle frequenze empiriche. - Limite idrodinamico: Teorema di Kurtz e descrizione deterministica tramite ODE. - Limite idrodinamico di modelli binari: voter, SIS, majority, k-majority. - Modelli ergodici: la relazione tra misura invariante e punti di equilibrio della ODE. - Esempi multidimensionali: SIR, SIRS. Modelli eterogenei. 9. Grafi aleatori - Grafo aleatorio di Erdos-Renyi: definizione, proprietà elementari, distribuzione dei gradi, approssimazione con il processo di ramificazione, soglia di connettività , soglia per l’esistenza di una componente gigante. - Modello di grafo casuale con distribuzione dei gradi assegnata (configuration model): proprietà elementari, approssimazione con il processo di ramificazione, soglie per connessione ed esistenza di una componente gigante. - Modelli avanzati di grafi aleatori: preferential attachment, small world. - Limite idrodinamico per dinamiche senza memoria su grafi aleatori con distribuzione dei gradi fissata.Processi stocastici/Dinamiche su network (Processi stocastici)- Definizione di processi stocastici e loro principali caratterizzazioni e proprietà . - Processi di conteggio e renewal. - Processi di Poisson: definizioni equivalenti, risultati notevoli, processi di Poisson non omogenei. - Catene di Markov a tempo discreto e loro proprietà , matrici di transizione, equazioni di Chapman-Kolmogorov, classificazione degli stati, convergenza in distribuzione e teorema ergodico per catene irriducibili, esistenza e unicità di distribuzioni stazionarie, connessioni fra i tempi medi di ritorno e la distribuzione stazionaria. - Catene di Markov a tempo continuo e loro rappresentazioni, equazioni di Kolmogorov, distribuzioni stazionarie ed equazioni di bilancio. - Esempi notevoli: catene reversibili e catene di nascita e morte, elementi di teoria delle code, reti di Jackson. - Martingale e le loro proprietà , teorema di decomposizione di Doob, teoremi di arresto di Doob, teoremi di convergenza di Doob, disuguaglianza di Azuma-Hoeffding, esempi di applicazioni. - Moto Browniano (o processo di Wiener): definizione e risultati base.
Processi stocastici/Dinamiche su network (Dinamiche su Network)Modalita di esame: Prova orale obbligatoria; Elaborato progettuale individuale; Processi stocastici/Dinamiche su network (Processi stocastici)Modalita di esame: Prova orale obbligatoria; Elaborato scritto individuale; Elaborato progettuale in gruppo;
Processi stocastici/Dinamiche su network (Dinamiche su Network)Exam: Compulsory oral exam; Individual project; Processi stocastici/Dinamiche su network (Processi stocastici)Exam: Compulsory oral exam; Individual essay; Group project;
... Processi stocastici/Dinamiche su network (Dinamiche su Network)La verifica dell’apprendimento consiste nelle seguenti parti: 1. Tre homework (HW1, HW2 e HW3) che vengono assegnati, rispettivamente, alla fine dei mesi di Ottobre, Novembre e Dicembre (prima delle vacanze natalizie). I primi due consistono di esercizi teorici ed applicativi ed hanno lo scopo di verificare l’assimilazione da parte dello studente delle teorie sviluppate nel modulo e a valutarne lo sviluppo delle capacità di modellizzazione matematica. Il terzo homework, oltre ad una parte strutturalmente simile ai primi due, prevede un progetto di tipo simulativo/numerico ed ha lo scopo di valutare le capacità progettuali dello studente. I tempi di consegna sono di due settimane per HW1 e HW2 e di tre per HW3. 2. Una prova orale finale che consiste di due parti: 2a) Discussione degli homework HW1, HW2, HW3 al fine di valutare la capacità critica dello studente rispetto al lavoro svolto. 2b) Presentazione da parte del candidato di un argomento teorico trattato nel corso e di eventuali relativi esempi di applicazione. L' argomento in questione viene scelto dalla commissione e comunicato al candidato, a cui vengono lasciati 30 minuti per la preparazione della risposta, e durante i quali possono essere consultati libri ed appunti. Scopo di questa seconda parte è la valutazione delle conoscenze teoriche di base acquisite e la capacità dello studente di presentarle in modo autonomo ed efficace. Punteggi: I punteggi massimi per gli homework, a seguito della discussione di cui a 2a), sono 4 per HW1 e HW2 ciascuno e di 6 per HW3. Nel caso in cui le consegne siano avvenute in ritardo i massimi scendono a 3 e 5 rispettivamente. Il punteggio massimo della prova 2b) è pari a 18. Al termine delle due prove il punteggio viene sommato: se esso è non superiore a 30, esso costituisce il voto finale, se è superiore il voto finale è 30 e lode. Processi stocastici/Dinamiche su network (Processi stocastici)- È prevista una prova orale obbligatoria. Durante la prova, il candidato dovrà discutere un argomento teorico trattato nel corso, con relative applicazioni. Verranno valutati i seguenti aspetti: . la conoscenza di definizioni e teoremi, incluse le relative dimostrazioni; . la comprensione della teoria; . la capacità di applicare la teoria in esercizi pratici o teorici; . la capacità espositiva e di presentazione. L'argomento principale dell'esame sarà scelto dalla commissione e comunicato al candidato, il quale avrà a disposizione 30 minuti per prepararsi. Durante questo tempo sarà possibile consultare libri e appunti. Al termine della prova orale verrà assegnato un punteggio massimo di 31 (equivalente a 30 e lode). - Oltre alla prova orale obbligatoria, lo studente può partecipare, in maniera facoltativa, alla seguente attività : . Ogni settimana, lo studente risponderà in autonomia a dei quiz pubblicati sulla pagina Moodle del corso. I quiz saranno preparati, alternativamente, dal docente o dagli studenti stessi (tramite un lavoro di gruppo svolto in classe, vedi sotto). . Ogni due settimane, gli studenti lavoreranno in gruppo per un'ora e mezza per risolvere esercizi o preparare i quiz basati sui contenuti del corso. Gli studenti che risponderanno ad almeno il 90% dei quiz settimanali e parteciperanno ad almeno il 70% delle attività di gruppo riceveranno un punto bonus, che verrà aggiunto al punteggio ottenuto nella prova orale.
Processi stocastici/Dinamiche su network (Dinamiche su Network)Parte degli argomenti del corso saranno coperti da dispense che verranno rese disponibili agli studenti tramite il Portale della Didattica. Processi stocastici/Dinamiche su network (Processi stocastici)Si consiglia di studiare il materiale del corso tramite slide con note rilasciate dal docente, e videoregistrazioni delle lezioni. Come ulteriore spunto per lo studio della materia si consigliano i seguenti libri, che pero' non verranno seguiti fedelmente dal docente e la cui lettura non è obbligatoria: - R. Durrett, "Essentials of Stochastic Processes", Springer, 2021 (online available). - D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times", AMS, 2008 (online available). - S.M. Ross, "Introduction to Probability Models", Elsevier, 2010. - J.M. Steele "Stochastic Calculus and Financial Applications", Springer, 2000.