Processi di diffusione epidemici su grafi aleatori

Indice
Introduzione I
1 Processi stocastici 1
1.1 Catene di Markov a tempo discreto . . . . . . . . . . . . . . . 1
1.2 Catene di Markov a tempo continuo . . . . . . . . . . . . . . . 13
2 Gra aleatori 22
2.1 Il modello di Erd os-Renyi . . . . . . . . . . . . . . . . . . . . 23
2.2 La famiglia G(w) . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.1 Il raggio spettrale della matrice di adiacenza . . . . . . 32
2.3 Il modello di Chung-Lu . . . . . . . . . . . . . . . . . . . . . . 39
3 Fenomeni di diusione su gra 46
3.1 Il modello per l’epidemia . . . . . . . . . . . . . . . . . . . . . 46
3.2 Condizioni di estinzione su gra deterministici . . . . . . . . . 48
3.2.1 Condizione suciente per estinzione rapida . . . . . . . 48
3.2.2 Condizione suciente per estinzione lenta . . . . . . . 51
3.3 Condizioni di estinzione su gra aleatori . . . . . . . . . . . . 57
Conclusioni 65
A Elementi di coupling 67
A.1 Che cos’ e un coupling? . . . . . . . . . . . . . . . . . . . . . . 67
A.2 La Dominanza stocastica . . . . . . . . . . . . . . . . . . . . . 68
A.3 Applicazioni al problema di diusione . . . . . . . . . . . . . . 70
3

INDICE INDICE
A.3.1 Teorema di estinzione rapida 3.2.1 . . . . . . . . . . . . 70
A.3.2 Teorema di estinzione lenta 3.2.5 . . . . . . . . . . . . 76
A.3.3 Dimostrazione del lemma 3.3.2 . . . . . . . . . . . . . . 79
B Disuguaglianze di Cherno 83
Bibliograa 86