Incontri settimanali su
Algoritmi Probabilistici e Catene di Markov
RAMC (Randomized Algorithms and Markov Chains) č un gruppo di studio che si riunisce settimanalmente per discutere
di argomenti relativi a "probabilità e computazione". Gli obiettivi per
l'anno accademico 2009-2010 sono i seguenti:
1. Fornire a tutti i partecipanti gli strumenti matematici necessari per
l'analisi di algoritmi probabilistici, con numerosi esempi tratti
principalmente dal libro "Probability and Computing: Randomized
Algorithms and Probabilistic Analysis" di Michael Mitzenmacher e Eli
Upfal;
2. Studiare in modo sistematico e approfondito il libro di recente
pubblicazione "Markov Chains and Mixing Times" di David Levin, Yuval
Peres e Elizabeth Wilmer.
Avvisi
Programma preliminare (pdf)
Richiami di probabilitā discreta: eventi, probabilitā condizionata, indipendenza. Algoritmi probabilistici per rompere la simmetria: il problema Contention Resolution.
Variabili aleatorie, speranza matematica, distribuzioni binomiale e geometrica: il problema del Coupon Collector.
Stime del discostamento dalla media: disuguaglianza di Markov, varianza e covarianza di una v.a., disuguaglianza di Chebyshev, disuguaglianze di Chernoff. Applicazioni: un algoritmo probabilistico approssimante per MAX-Cut, la soglia di connettivitā per i Geometric Random Graph, il Permutation Routing sugli ipercubi.
Problemi di tipo Balls into Bins. Il paradosso dei compleanni. La distribuzione di Poisson. Il metodo probabilistico: il conteggio di base, la media, la tecnica sample and modify. Derandomizzazione. Il metodo del momento secondo. Il Lemma Locale di Lovasz. Applicazioni: un algoritmo probabilistico approssimante per MAX-Sat, Independent sets, funzioni soglia nei Random Graph, condizioni sufficienti per la soddisfacibilità di una formula k-SAT.
Catene di Markov, definizioni ed esempi: la rovina del giocatore, catene di nascita e morte, passeggiate aleatorie. Irriducibilitā, aperiodicitā, distribuzioni stazionarie.
Distanza fra distribuzioni, Mixing Time. Teorema di convergenza, Coupling. Metodi Markov Chain Monte Carlo per il sampling da una distribuzione fissata, catene di Metropolis e di Glauber: Random Colorings, il modello Ising. Raggiungere l'equilibrio: Card Shuffling. Tecniche di lower bound per il mixing time.
Diario degli incontri
- 29 set 09: Algoritmi probabilistici per rompere la simmetria: il problema Contention Resolution ([KT05]: 13.1). Von Neumann unbiasing.
- 6 ott 09: Richiami di probabilità discreta: eventi, probabilità condizionata, indipendenza, variabili aleatorie, speranza matematica ([GS97]: 1.2, 4.1, 6.1). Il problema del Coupon Collector ([MU05]: 2.4)
-
13 ott 09: Varianza e covarianza di una v.a. Stime del discostamento dalla media: disuguaglianze di Markov e Chebyshev. La legge dei grandi numeri. ([MU05]: 3.1, 3.2, 3.3) Esempio: analisi di un algoritmo probabilistico 2-approssimante per Max-Cut.
-
20 ott 09: Pairwise independence e la varianza di una somma di v.a. ([MU05]: 13.2) Chernoff bounds. ([MU05]: 4.2)
-
27 ott 09: Applicazioni dei Chernoff bounds. Problemi del tipo Balls into Bins, esempio: Load Balancing ([KT05]: 13.10)
-
3 nov 09: Il Metodo Probabilistico: il conteggio di base, la media, la tecnica sample and modify ([MU05]: 6.1, 6.2, 6.4)
-
10 nov 09: Il Lemma Locale di Lovász. Applicazioni: condizioni sufficienti per la soddisfacibilità di formule k-sat e per l'esistenza di edge-disjoint paths ([MU05]: 6.7)
-
17 nov 09: Catene di Markov, definizioni ed esempi. Random mapping representation. ([LPW08]: 1.1, 1.2)
-
24 nov 09: Irriducibilità e aperiodicità ([LPW08]: 1.3, 1.4)
-
1 dic 09: Distribuzioni stazionarie: esistenza e unicità. Catene reversibili ([LPW08]: 1.5, 1.6)
-
8 dic 09: Festa
-
15 dic 09: L'incontro non si è svolto per mancanza di partecipanti.
-
12 gen 10: Classificazione degli stati ([LPW08]: 1.7). La rovina del giocatore e il coupon collector ([LPW08]: 2.1, 2.2)
-
19 gen 10: Proiezioni di catene: Urne di Ehrenfest e passeggiate aleatorie sull'ipercubo. L'urna di Polya. ([LPW08]: 2.3, 2.4)
-
26 gen 10: Catene di nascita e morte. Random walk su gruppi, catene transitive. ([LPW08]: 2.5, 2.6)
-
2 mar 10: Total variation distance e Coupling ([LPW08]:4.1, 4.2).
-
16 mar 10: Il teorema di convergenza per catene finite irriducibili e aperiodiche. Distanza dalla stazionaria. Mixing time. ([LPW08]: 4.3, 4.4, 4.5)
| Testi di riferimento |
|
| [MU05] |
 |
| Michael Mitzenmacher, Eli Upfal |
| Probability and Computing: Randomized Algorithms and Probabilistic Analysis |
| Cambridge University Press, 2005 |
|
| [LPW08] |
 |
| David A. Levin, Yuval Peres, Elizabeth L. Wilmer |
| Markov Chains and Mixing Times |
| American Mathematical Society, 2008 |
| Una versione elettronica di questo libro è liberamente scaricabile qui |
| Testi di supporto |
|
| [KT05] |
 |
| Jon Kleinberg, Eva Tardos |
| Algorithm Design |
| Addison-Wesley, 2005 |
|
|
| [GS97] |
 |
| Charles M. Grinstead, J. Laurie Snell |
| Introduction to Probability |
| American Mathematical Society, 1997 |
| Una versione elettronica di questo libro è liberamente scaricabile qui |
Altri riferimenti
Contatti
Francesco Pasquale
pasquale@dia.unisa.it
Ultimo aggiornamento: Martedì 16 Marzo 2010