Lezione 1 (28 febbraio). Introduzione alle catene di
Markov. Esempi. Catena a due stati.
Lezione 2 (6 marzo). Passeggiate aleatorie su grafi. Catene di Markov irriducibili.
Lezione 3 (7 marzo). Esistenza e unicita' della misura
invariante per catene irriducibili. Catene reversibili.
Lezione 4 (13 marzo). Processo di nascita e morte. Coupon collecting. Passeggiata
aleatoria su ipercubo. Urne di
Ehrenfest. Proiezione di catene di Markov.
Lezione 5 (14 marzo). Introduzione al metodo Monte
Carlo. Algoritmo di Metropolis. Esempi: colorazioni di
un grafo, modello di Ising. Dinamica di Glauber.
Lezione 6 (20 marzo). Distanza di variazione
totale. Accoppiamento. Esempi.
Lezione 7 (21 marzo). Teorema di convergenza per catene di
Markov irriducibili e aperiodiche. Tempo di mixing. Teorema ergodico per catene di Markov
irriducibili.
Lezione 8 (27 marzo). Accoppiamento di catene di Markov e
prime stime sul tempo di mixing per passeggiate aletorie.
Lezione 9 (28 marzo). Grand coupling. Esempi. Stima del tempo di
mixing per le colorazioni di un grafo.
Lezione 10 (4 aprile). Tempi stazionari forti. Stima
dall'alto e dal basso del tempo di mixing per top to random
shuffle.
Lezione 11 (9 aprile). Tempo di mixing per Random Transpositions.
Lezione 12 (11 aprile). Analisi spettrale e convergenza
all'equilibrio. Gap spettrale, tempo di
rilassamento.
Lezione 13 (24 aprile). Tempo di mixing vs. tempo di
rilassamento. Random Walk su n-ciclo. Catene prodotto. Esempi di stima del tempo di mixing in
termini di autovalori.
Lezione 14 (30 aprile). Forma di Dirichlet e principio
variazionale per il gap spettrale. Conduttanza e disuguaglianza di
Cheeger. Stime dal basso e dall'alto per il tempo di rilassamento.
Esempio della passeggiata
aleatoria asimmetrica, su ipercubo e su toro d-dimensionale.
Lezione 15 (2 maggio). Processo di Poisson. Catene di Markov a
tempo continuo I.
Lezione 16 (8 maggio). Catene di Markov a tempo continuo II.
Lezione 17 (9 maggio)
Rappresentazione grafica e accoppiamento per catene di Markov a tempo
conitnuo. Gap spettrale e tempo di rilassamento per catene a tempo
continuo.
Lezione 18 (22 maggio). Metodo del confronto e metodo dei cammini.
Stime con metodo dei cammini:
passeggiate aletorie simmetriche su grafi e perturbazione locale di
grafi. Processo di Bernoulli-Laplace.
Lezione 19 (23 maggio). Gap spettrale per il processo di
Bernoulli-Laplace e per il processo di
esclusione su n-ciclo.
Lezione 20 (29 maggio). Decadimento esponenziale in entropia relativa. Costante di entropia e tempo di mixing.
Lezione 21 (30 maggio). 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 (1 giugno). Modello di Ising su un
grafo. Mixing rapido ad alta temperatura. Transizione di fase dinamica
su grafo completo.