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”.
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 minuti scheda docente materiale didattico
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’
An 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).
Mutuazione: 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 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, 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 minuti scheda docente materiale didattico
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’
An 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).
Mutuazione: 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