Curriculum
Mutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
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
Non ci sono testi in italianoModalità Frequenza
FacoltativaModalità Valutazione
Colloquio orale di circa 45 minutiMutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
Programma
1. Passeggiate aleatorie e Catene di Markov. Successioni di variabili aleatorie.Passeggiate aleatorie. Catene di Markov a tempo discreto. Misura invariante, timereversal e reversibilit`a.
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. Convergenza in norma L2. Gap spettrale e stime
dei tempi di rilassamento. Disuguaglianza di Cheeger.
5. Catene di Markov a tempo continuo. Processo di Poisson. Q-matrici e probabilit`a di transizione a tempo continuo. Generatore infinitesimale di una catena di
Markov a tempo continuo. Costruzione esplicita e rappresentazione grafica.
6. Conduttanza e metodo dei cammini. Metodo della ‘comparazione’. Gap spettrale per il processo di Bernoulli-Laplace
e per il processo di esclusione sul toro d-dimensionale. Convergenza all’equilibrio in
termini di entropia e disuguaglianze di Sobolev logaritmiche.
7. 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’. Algoritmi per la ‘simulazione perfetta’
Testi Adottati
Markov Chains and Mixing Times, by D. Levine, Y. Peres and E. Wilmer, AMS 2009 - disponibile online pdfAn introduction to Markov processes, by D. Stroock, Springer 2013
Markov Chains, by J.R. Norris, Cambridge University Press 2006
Lectures on finite Markov chains, by L. Saloff-Coste, Lecture Notes in Math. 1665, pp.301-413 (1997).
Modalità Erogazione
lezioni alla lavagnaModalità Valutazione
esame orale sul programma svolto a lezioneMutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
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
Non ci sono testi in italianoModalità Frequenza
FacoltativaModalità Valutazione
Colloquio orale di circa 45 minutiMutuazione: 20410441 CP420-INTRODUZIONE AI PROCESSI STOCASTICI in Scienze Computazionali LM-40 MARTINELLI FABIO, CAPUTO PIETRO
Programma
1. Passeggiate aleatorie e Catene di Markov. Successioni di variabili aleatorie.Passeggiate aleatorie. Catene di Markov a tempo discreto. Misura invariante, timereversal e reversibilit`a.
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. Convergenza in norma L2. Gap spettrale e stime
dei tempi di rilassamento. Disuguaglianza di Cheeger.
5. Catene di Markov a tempo continuo. Processo di Poisson. Q-matrici e probabilit`a di transizione a tempo continuo. Generatore infinitesimale di una catena di
Markov a tempo continuo. Costruzione esplicita e rappresentazione grafica.
6. Conduttanza e metodo dei cammini. Metodo della ‘comparazione’. Gap spettrale per il processo di Bernoulli-Laplace
e per il processo di esclusione sul toro d-dimensionale. Convergenza all’equilibrio in
termini di entropia e disuguaglianze di Sobolev logaritmiche.
7. 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’. Algoritmi per la ‘simulazione perfetta’
Testi Adottati
Markov Chains and Mixing Times, by D. Levine, Y. Peres and E. Wilmer, AMS 2009 - disponibile online pdfAn introduction to Markov processes, by D. Stroock, Springer 2013
Markov Chains, by J.R. Norris, Cambridge University Press 2006
Lectures on finite Markov chains, by L. Saloff-Coste, Lecture Notes in Math. 1665, pp.301-413 (1997).
Modalità Erogazione
lezioni alla lavagnaModalità Valutazione
esame orale sul programma svolto a lezione