Lezione 1 (28 Febbraio). Introduzione alle catene di
Markov. Esempi. Catena a due stati.
Lezione 2 (2 Marzo). Esistenza e unicita' della misura
invariante per catene irriducibili. Tempi di visita.
Lezione 3 (). Processo di nascita e morte. Catene reversibili.
Lezione 4 (). Coupon collecting. Passeggiata
aleatoria su ipercubo. Urne di
Ehrenfest. Proiezione di catene di Markov.
Lezione 5 (). Introduzione al metodo Monte
Carlo. Algoritmo di Metropolis. Esempi: colorazioni di
un grafo, modello di Ising.
Lezione 6 (). Dinamica di Glauber. Distanza di variazione
totale. Accoppiamento.
Lezione 7 (). Teorema di convergenza per catene di
Markov irriducibili e aperiodiche. Tempo di mixing.
Lezione 8 (). Teorema ergodico per catene di Markov
irriducibili. Accoppiamento di catene di Markov e
prime stime sul tempo di mixing.
Lezione 9 (). Grand coupling. Esempi. Stima del tempo di
mixing per le colorazioni di un grafo.
Lezione 10 (). Tempi stazionari forti. Stima dall'alto e dal basso del tempo di mixing per il top to random
shuffle.
Lezione 11 (). Tempo di mixing per Random Transpositions.
Lezione 12 (). Analisi spettrale e convergenza
all'equilibrio. Gap spettrale, tempo di
rilassamento.
Lezione 13 (). Tempo di mixing vs. tempo di
rilassamento. Random Walk su n-ciclo. Catene prodotto.
Lezione 14 (). Esempi di stima del tempo di mixing in
termini di autovalori. Forma di Dirichlet. Stima dal basso del tempo di
rilassamento in termini di conduttanza.
Lezione 15 (). Stima dall'alto del tempo di
rilassamento in termini di conduttanza (Cheeger). Esempio della passeggiata
aleatoria asimmetrica, su ipercubo e su toro d-dimensionale.
Lezione 16 (). Catene di Markov a tempo continuo.
Lezione 17 ()
Gap spettrale e tempo di rilassamento per catene a tempo
continuo. Metodo del confronto e metodo dei cammini.
Lezione 18 (). Stime con metodo dei cammini:
passeggiate aletorie simmetriche su grafi e perturbazione locale di
grafi. Processo di Bernoulli-Laplace.
Lezione 19 (). Gap spettrale per il processo di
Bernoulli-Laplace e per il processo di
esclusione su n-ciclo.
Lezione 20 (). Decadimento esponenziale in entropia relativa. Costante di entropia e tempo di mixing.
Lezione 21 (). Disuguaglianze di Sobolev logaritmiche. Relazioni tra gap spettrale, costante entropia e costante di log-Sobolev. Tensorizzazione. Esempi: ipercubo, binomiale. Passaggi al limite: caso gaussiano e poisson.
Lezione 22 (). Modello di Ising su un
grafo. Mixing rapido ad alta temperatura.
Lezione 23 (). Dimensione uno: Mixing rapido per ogni valore della temperatura. Transizione di fase dinamica
per Ising su grafo completo.