Acquisire una solida preparazione di base negli aspetti principali della teoria dei processi stocastici con particolare riguardo ai processi di Markov e alle loro applicazioni (metodo Monte Carlo e simulated annealing), della teoria delle passeggiate aleatorie e dei modelli più semplici di sistemi di particelle interagenti.
Curriculum
scheda docente materiale didattico
Successioni di variabili aleatorie. Passeggiate aleatorie. Catene di Markov a tempo discreto e tempo continuo. Misura invariante, time-reversal e reversibilita'
2. Esempi e modelli classici.
Passeggiate aleatorie su grafi. Processi di nascita e morte. Processi di esclusione. Metodo Monte Carlo: algoritmi di tipo Metropolis e dinamiche di Glauber per il modello di Ising, colorazioni di un grafo e altri sistemi interagenti.
3. Convergenza all'equilibrio I. Distanza in variazione, tempi di mixing. Teoremi ergodici. Tecniche di accoppiamento. Tempi stazionari forti. Applicazioni al problema del “coupon collector” e al mescolamento di un mazzo di carte.
4. Convergenza all'equilibrio II. Gap spettrale e stime dei tempi di rilassamento. Disuguaglianza di Cheeger, conduttanza e metodo dei cammini. Metodo della “comparazione”. Gap spettrale per il processo di esclusione sul toro d-dimensionale. Convergenza all'equilibrio in termini di entropia e disuguaglianze di Sobolev logaritmiche. Esempi.
5. Altri argomenti scelti. Dinamica di Glauber per il modello di Ising: transizione di fase dinamica per il modello di campo medio e per il modello su reticolo. Il fenomeno del “cut- off”. Disuguaglianze di Sobolev logaritmiche e convergenza all'equilibrio. Algoritmi per la “simulazione perfetta”.
Programma
1. Passeggiate aleatorie e Catene di MarkovSuccessioni di variabili aleatorie. Passeggiate aleatorie. Catene di Markov a tempo discreto e tempo continuo. Misura invariante, time-reversal e reversibilita'
2. Esempi e modelli classici.
Passeggiate aleatorie su grafi. Processi di nascita e morte. Processi di esclusione. Metodo Monte Carlo: algoritmi di tipo Metropolis e dinamiche di Glauber per il modello di Ising, colorazioni di un grafo e altri sistemi interagenti.
3. Convergenza all'equilibrio I. Distanza in variazione, tempi di mixing. Teoremi ergodici. Tecniche di accoppiamento. Tempi stazionari forti. Applicazioni al problema del “coupon collector” e al mescolamento di un mazzo di carte.
4. Convergenza all'equilibrio II. Gap spettrale e stime dei tempi di rilassamento. Disuguaglianza di Cheeger, conduttanza e metodo dei cammini. Metodo della “comparazione”. Gap spettrale per il processo di esclusione sul toro d-dimensionale. Convergenza all'equilibrio in termini di entropia e disuguaglianze di Sobolev logaritmiche. Esempi.
5. Altri argomenti scelti. Dinamica di Glauber per il modello di Ising: transizione di fase dinamica per il modello di campo medio e per il modello su reticolo. Il fenomeno del “cut- off”. Disuguaglianze di Sobolev logaritmiche e convergenza all'equilibrio. Algoritmi per la “simulazione perfetta”.
Testi Adottati
D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).Bibliografia Di Riferimento
[1] O. Haggstrom, Finite Markov chains and algorithmic applications.. Cambridge Univ. Press, (2002). [2] J. Norris, Markov chains. Cambridge Univ. Press, (2008). [3] L. Saloffe-Coste, Lectures on finite Markov chains.. Springer Lecture Notes in Math. 1665, (1997).Modalità Valutazione
Colloquio orale di circa 45 minuti scheda docente materiale didattico
Successioni di variabili aleatorie. Passeggiate aleatorie. Catene di Markov a tempo discreto e tempo continuo. Misura invariante, time-reversal e reversibilita'
2. Esempi e modelli classici.
Passeggiate aleatorie su grafi. Processi di nascita e morte. Processi di esclusione. Metodo Monte Carlo: algoritmi di tipo Metropolis e dinamiche di Glauber per il modello di Ising, colorazioni di un grafo e altri sistemi interagenti.
3. Convergenza all'equilibrio I. Distanza in variazione, tempi di mixing. Teoremi ergodici. Tecniche di accoppiamento. Tempi stazionari forti. Applicazioni al problema del “coupon collector” e al mescolamento di un mazzo di carte.
4. Convergenza all'equilibrio II. Gap spettrale e stime dei tempi di rilassamento. Disuguaglianza di Cheeger, conduttanza e metodo dei cammini. Metodo della “comparazione”. Gap spettrale per il processo di esclusione sul toro d-dimensionale. Convergenza all'equilibrio in termini di entropia e disuguaglianze di Sobolev logaritmiche. Esempi.
5. Altri argomenti scelti. Dinamica di Glauber per il modello di Ising: transizione di fase dinamica per il modello di campo medio e per il modello su reticolo. Il fenomeno del “cut- off”. Disuguaglianze di Sobolev logaritmiche e convergenza all'equilibrio. Algoritmi per la “simulazione perfetta”.
Mutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO
Programma
1. Passeggiate aleatorie e Catene di MarkovSuccessioni di variabili aleatorie. Passeggiate aleatorie. Catene di Markov a tempo discreto e tempo continuo. Misura invariante, time-reversal e reversibilita'
2. Esempi e modelli classici.
Passeggiate aleatorie su grafi. Processi di nascita e morte. Processi di esclusione. Metodo Monte Carlo: algoritmi di tipo Metropolis e dinamiche di Glauber per il modello di Ising, colorazioni di un grafo e altri sistemi interagenti.
3. Convergenza all'equilibrio I. Distanza in variazione, tempi di mixing. Teoremi ergodici. Tecniche di accoppiamento. Tempi stazionari forti. Applicazioni al problema del “coupon collector” e al mescolamento di un mazzo di carte.
4. Convergenza all'equilibrio II. Gap spettrale e stime dei tempi di rilassamento. Disuguaglianza di Cheeger, conduttanza e metodo dei cammini. Metodo della “comparazione”. Gap spettrale per il processo di esclusione sul toro d-dimensionale. Convergenza all'equilibrio in termini di entropia e disuguaglianze di Sobolev logaritmiche. Esempi.
5. Altri argomenti scelti. Dinamica di Glauber per il modello di Ising: transizione di fase dinamica per il modello di campo medio e per il modello su reticolo. Il fenomeno del “cut- off”. Disuguaglianze di Sobolev logaritmiche e convergenza all'equilibrio. Algoritmi per la “simulazione perfetta”.
Testi Adottati
D. Levine, Y. Peres, E. Wilmer, Markov chains and mixing times.. AMS bookstore, (2009).Bibliografia Di Riferimento
[1] O. Haggstrom, Finite Markov chains and algorithmic applications.. Cambridge Univ. Press, (2002). [2] J. Norris, Markov chains. Cambridge Univ. Press, (2008). [3] L. Saloffe-Coste, Lectures on finite Markov chains.. Springer Lecture Notes in Math. 1665, (1997).Modalità Valutazione
Colloquio orale di circa 45 minuti