Lezione 1 (26 settembre). Introduzione alle catene di
Markov. Esempio: catena a due stati.
Lezione 2 (28 settembre). Catene irriducibili, misura
invariante. Tempi di visita. Esistenza e unicita' della misura
invariante per catene irriducibili.
Lezione 3 (3 ottobre). Reversibilita' e
time-reversal. Esempi: passeggiata su
k-ciclo, simmetrica e non. Processi di nascita e morte.
Lezione 4 (6 ottobre). Coupon collecting. Passeggiata
sull'ipercubo. Urne di Ehrenfest. Proiezione di catene di
Markov. Esempi.
Lezione 5 (12 ottobre). Markov chain Monte Carlo. Esempi:
coloring, modello di Ising, problemi di ottimizzazione. Algoritmo di
Metropolis. Dinamica di Glauber.
Lezione 7 (24 ottobre).
Teorema di convergenza per catene di Markov regolari. Esempi
Lezione 8 (26 ottobre).
Tempi di mixing. Teorema ergodico per
catene irriducibili. Catene di Markov a tempo
continuo I.
Lezione 9 (7 novembre). Catene di Markov a tempo
continuo II. Q-matrici e costruzione del processo associato.
Lezione 10 (9 novembre). Q-matrici e misure
reversibili/invarianti. Passeggiate aleatorie su grafi
pesati e random trap model. Accoppiamento per catene di Markov. Stime del tempo
di mixing tramite accoppiamento. Tempo
di mixing per passeggiata aleatoria su k-ciclo.
Lezione 11 (21 novembre).
Stime del tempo di mixing tramite accoppiamento:
passeggiata aleatoria sul toro d-dimensionale, su
ipercubo, dinamica di Metropolis per le colorazioni di un grafo.
Lezione 12 (23 novembre).
Tempi stazionari forti. Esempi. Stima
dall'alto e dal basso del
tempo di mixing per il top-to-random shuffle.
Lezione 13 (28 novembre).
Spettro di una matrice stocastica. Decomposizione spettrale
per matrici reversibili. Catene pigre. Gap spettrale e tempo di
rilassamento. Relazioni tra tempo di mixing e tempo
di rilassamento.
Lezione 14 (30 novembre).
Uso degli autovalori per stima del
tempo di mixing.
Forma di Dirichlet. Stima del tempo di
rilassamento in termini di conduttanza (disuguaglianza di Cheeger).
Lezione 15 (5 dicembre).
Conduttanza per passeggiata aleatoria sul toro e sull'ipercubo, passeggiata
asimmetrica sugli interi. Gap spettrale per catene di Markov a
tempo continuo.
Lezione 16 (7 dicembre). Metodo del confronto. Esempio: passeggiate
aletorie simmetriche su grafi e perturbazione
locale di grafi. Decadimento esponenziale in
entropia relativa. Costante di entropia e tempo di mixing.
Lezione 17 (12 dicembre). Disuguaglianze di Sobolev
logaritmiche. Relazioni tra gap spetrale, costante entropia e
costante di log-Sobolev. Tensorizzazione. Esempi: ipercubo,
binomiale. Passaggi al limite: caso gaussiano e poisson.
Lezione 18 (14 dicembre). Modello di Ising su un grafo. Mixing
rapido ad alta temperatura tramite path coupling. Esempio del grafo completo.
Lezione 19 (19 dicembre).
Modello di Ising: transizione di fase dinamica su grafo
completo. Modello di Ising in dimensione 1: mixing
rapido per ogni valore della temperatura.
Lezione 20 (21 dicembre).
Modello di Ising: transizione di fase dinamica in dimensione 2.