Lezione 1 (19 settembre). Introduzione alle catene di
Markov. Esempio: catena a due stati. Catene irriducibili, misura
invariante.
Lezione 2 (21 settembre). Tempi di visita. Esistenza e unicita' della misura
invariante per catene irriducibili.
Lezione 3 (26 settembre). Reversibilita' e
time-reversal. Esempi: passeggiata su
n-ciclo, simmetrica e non. Processi di nascita e morte.
Lezione 4 (28 settembre). Coupon collecting. Passeggiata
sull'ipercubo. Urne di Ehrenfest. Proiezione di catene di
Markov. Esempi.
Lezione 5 (3 ottobre). Markov chain Monte Carlo. Esempi:
coloring, modello di Ising, problemi di ottimizzazione. Algoritmo di
Metropolis. Dinamica di Glauber.
Lezione 6 (5 ottobre). Variazione totale. Accoppiamento. Esempi.
Teorema di convergenza per catene di Markov irriducibili e
aperiodiche.
Lezione 7 (10 ottobre). Tempi di mixing. Teorema ergodico per
catene irriducibili.
Lezione 8 (12 ottobre). Catene di Markov a tempo
continuo. Q-matrici e costruzione della catena di Markov associata.
Lezione 9 (17 ottobre). Q-matrici e misure
reversibili/invarianti. Passeggiate aleatorie su grafi
pesati e random trap model. Accoppiamento per catene di Markov. Tempo
di mixing per passeggiata aleatoria su k-ciclo.
Lezione 10 (19 ottobre). Stime del tempo
di mixing tramite accoppiamento: passeggiata aleatoria sul toro, su
ipercubo, dinamica di Metropolis per le colorazioni di un grafo.
Lezione 11 (26 ottobre, lezione di Daniele Piras). Stime dal
basso del tempo
di mixing tramite 'bottleneck ratio'. Esempi.
Lezione 12 (7 novembre). Tempi stazionari forti. Esempi. Stima
dall'alto e dal basso del
tempo di mixing per il top-to-random shuffle.
Lezione 13 (9 novembre). Trasposizioni aleatorie: Stima
dall'alto del tempo di
mixing tramite accoppiamento e tramite tempo stazionario forte.
Lezione 14 (14 novembre). Trasposizioni aleatorie: Stima
dal basso del tempo di
mixing. Spettro di una matrice stocastica. Decomposizione spettrale
per matrici reversibili. Catene pigre. Gap spettrale e tempo di
rilassamento.
Lezione 15 (16 novembre). Relazioni tra tempo di mixing e tempo
di rilassamento. Catene prodotto. Uso degli autovalori per stima del
tempo di mixing. Esempi: passeggiata aleatoria sul toro e sull'ipercubo.
Lezione 16 (21 novembre). Forma di Dirichlet. Stima del tempo di
rilassamento in termini di conduttanza (disuguaglianza di Cheeger).
Esempi: passeggiata aleatoria sul toro e sull'ipercubo, passeggiata
asimmetrica sugli interi.
Lezione 17 (23 novembre). Gap spettrale per catene di Markov a
tempo continuo. Metodo del confronto e metodo dei cammini. Esempio: passeggiate
aletorie simmetriche su grafi e perturbazione
locale di grafi.
Lezione 18 (28 novembre). Gap spettrale per la passeggiata di
Bernoulli-Laplace. Processo di esclusione.
Lezione 19 (30 novembre). Metodo dei cammini per processo di
esclusione su reticolo d-dimensionale. Decadimento esponenziale in
entropia relativa. Costante di entropia e tempo di mixing.
Lezione 20 (5 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 21 (7 dicembre). Modello di Ising su un grafo. Mixing
rapido ad alta temperatura. Transizione di fase dinamica su grafo
completo.
Lezione 22 (12 dicembre). Modello di Ising in dimensione 1: mixing
rapido per ogni valore della temperatura. Transizione di fase
dinamica in dimensione 2.
Lezione 23 (14 dicembre). Algoritmo di Propp e Wilson per la simulazione
perfetta: iterazione di mappe aleatorie; accoppiamento nel
futuro e accoppiamento dal passato; esempio del modello di Ising ferromagnetico.