L’insegnamento ha lo scopo di presentare gli elementi fondamentali dei processi stocastici e della teoria dei grafi per arrivare allo studio di modelli matematici che descrivono dinamiche su network sia di tipo deterministico che aleatorio. Verranno descritti i principali processi stocastici a tempo discreto e continuo con particolare attenzione alle loro applicazioni ingegneristiche, gli elementi di base della teoria dei grafi combinatoria e algebrica e la teoria delle matrici stocastiche. Verranno poi considerati modelli di dinamiche su grafi sia deterministiche che probabilistiche. Saranno 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.

Conoscenza di elementi teorici di base dei processi stocastici e delle loro principali caratteristiche e proprietà.
Capacità di riconoscere i processi stocastici idonei a modellare sistemi dinamici caratterizzati da evoluzioni non-deterministiche.
Capacità di analizzare modelli stocastici dinamici, e di descrivere grandezze aleatorie ad essi riferibili, quali tempi di attesa o di raggiungimento di stati assorbenti, o condizioni di stazionarietà e relative distribuzioni.
Conoscenza di elementi di base della teoria dei grafi diretti con particolare enfasi sui concetti di connessione e periodo.
Conoscenza della teoria delle matrici stocastiche e substocastiche, delle loro proprietà spettrali e del metodo dell’analogia elettrica.
Capacità di costruire e analizzare modelli matematici deterministici e stocastici per dinamiche su reti che descrivono modelli epidemici, socio-economici, algoritmi inferenziali cooperativi.
Capacità di analizzare le prestazioni di un algoritmo su una rete, la sua complessità e la sua velocità di convergenza con particolare riferimento alle proprietà di scalabilità rispetto al numero di nodi nel grafo.

Una preparazione equivalente a 15 crediti di Probabilità e Statistica Matematica. Sono inoltre richieste le nozioni fondamentali di algebra lineare e analisi

• Introduzione generale ai processi stocastici; filtrazioni; stopping times.
• Martingale a tempo discreto e relative proprietà. Decomposizione di supermartingale e submartingale, Teorema di Doob, convergenza.
• Processi di Poisson: definizioni equivalenti, generalizzazioni (non-omogenei, composti, mixed).
• Processi di rinnovo: distribuzioni di equilibrio, teoremi limite e processi stazionari, numero medio di rinnovi.
• Catene di Markov: matrici di transizione, classificazione degli stati, stazionarietà ed ergodicità, reversibilità. Esempi (Branching processes).
• Processi markoviani a tempo continuo, processi di nascita e morte, equazioni di Kolmogorov, distribuzioni stazionarie.
• Moti browniani: definizione, proprieta', applicazioni.
• Grafi diretti, cammini, circuiti, cicli. Connessione e forte connessione. Periodo di un nodo, grafi aperiodici. Componenti connesse e grafo di condensazione.
• Laplaciano di grafi, forma di Dirichlet, funzioni armoniche.
• Matrici stocastiche e loro utilizzo nelle dinamiche di consenso. Convergenza per le potenze di una matrice stocastica. Proprietà spettrali. Diseguaglianza di Cheeger
• Grafi come circuiti elettrici e collegamento con le matrici stocastiche reversibili.
• Applicazioni: algoritmi per la stima distribuita, dinamiche di opinione.
• Modelli ad agenti interagenti. Interazioni di tipo gossip. Modelli per la diffusione delle epidemie. Modelli per la dinamica delle opinioni. Modelli derivanti dalla teoria dei giochi evolutiva.
• L’approssimazione di campo medio.
• Dinamiche su alberi. Modelli di grafi aleatori.

Esercitazioni in forma tradizionale completeranno le lezioni teoriche.

Parte degli argomenti del corso saranno coperti da dispense disponibili on-line. Altri testi:
• Sheldon N. Ross "Stochastic processes" 2nd ed John Wiley
• Jacod J., Protter P, “Probability essentials”, Springer 2000
• D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (disponibile online).

L’esame consiste di una prova orale da sostenersi a fine corso. Alcune parti dell’esame potranno essere preventivamente superate durante il corso tramite lavori individuali di tipo homework ed in tal modo eliminate dalla prova orale finale.