Analisi probabilistica di trasmissione in rete

INTRODUZIONE ii
uno deterministico.
Nello studi e nell’analisi dei grafi random consideremo uno dei seguenti due
modelli, G(n,M) e G(n, p). Il primo e` uno spazio di probabilita` consistente di
tutti i grafi con un dato insieme di n vertici etichettati e M archi, ed ad ogni grafo
e` assegnata la stessa probabilita`. Il secondo modello e` anch’esso uno spazio di
probabilita` consistente di tutti i grafi con un dato insieme di n vertici etichettati
nel quale gli archi sono scelti indipendentemente e con probabilita` p con 0 < p < 1.
In generale M e p sono funzioni di n: M=M(n) e p=p(n). Per ogni numero naturale
n ci sara` uno spazio di probabilita` costituito da grafi con esattamente n vertici,
saremo interessati alle proprieta` di questo spazio per n →∞. Con queste ipotesi
diremo che un elemento di uno dei due modelli di grafo random considerati ha
quasi sempre una proprieta` Q se Pr[Q] → 1 per n →∞.
Un grafo random si puo` immaginare come una configurazione che inizia il suo
sviluppo con nessun arco e evolve acquisendo archi in modo casuale. Tali grafi
subiscono repentini cambiamenti strutturali al crescere del numero degli archi. Il
nostro scopo principale e` determinare in quale fase dell’evoluzione una particolare
proprieta` si manifesta. Erdo`s e Re`nyi dimostrarono che la maggior parte delle
proprieta` dei grafi appaiono quasi improvvisamente. Se scegliamo una funzione
M(n) (p(n)) allora, in molti casi, o quasi ogni grafo G ha la proprieta` Q o quasi
nessuno ha questa proprieta`. La transizione di una proprieta` dall’essere molto
improbabile all’essere molto probabile e` di solito molto rapida. Questo fenomeno
viene descritto in termini di una funzione detta funzione soglia. Piu` precisamente
consideriamo una proprieta` Q monotona crescente, ossia una proprieta` per la
quale il grafo ha Q ogniqualvolta uno dei suoi sottografi ha la proprieta` Q. Per
molte tali proprieta` esiste una funzione Mo(n) (r(n)) detta funzione soglia per Q.
INTRODUZIONE iii
Se M(n) (p(n)) cresce un po` piu` lentamente di Mo (r(n)), allora quasi ogni G non
gode della proprieta` Q, se M(n) cresce un po` piu` velocemente di Mo(n) (r(n)),
allora quasi ogni G ha la proprieta` Q. Analizzeremo con attenzione la funzione
soglia per la connettivita` di un grafo random.
Presentazione del lavoro di tesi.
• Nel primo capitolo sono date le definizioni, formule e risultati di calcolo
della probabilita` di cui avremo bisogno in tutto il lavoro. Sono poi descritti
i modelli di grafo random ed alcuni esempi di funzione soglia. Viene descritto
in breve il paradigma di Poisson ed alcune situazioni nelle quali puo` essere
rigorosamente provato. Sono infine esposti e dimostrati i principali risultati
riguardanti il numero di cricca e il numero cromatico di un grafo random.
• Il secondo capitolo e` dedicato alla descrizione di come la struttura di questi
grafi random cambia durante la loro evoluzione. Analizzeremo in particolare
l’ordine delle sue componenti. Quando il grafo random evolve inizialmente
acquista archi che sono sparsi in piccoli alberi di ordine O(log n), si ha poi un
cambiamento drastico della struttura del grafo detto ”transizione di fase”, di
cui faremo uno studio accurato, in cui le componenti hanno ordine O(n2/3)
queste componenti poi si fondono per formare una componente gigante di
ordine O(n). Verra` analizzata infine, la funzione soglia per la connettivita` del
grafo random molto importante per la realizzazione di reti di comunicazione,
oggetto del capitolo successivo.
• Nel capitolo terzo viene esposta un’analisi probabilistica della trasmissione
INTRODUZIONE iv
in rete, considerando un algoritmo per la trasmissione ottimale con guasti ca-
suali secondo lo schema di trasmissione standard e un algoritmo in parallelo
per la trasmissione randomizzata, in particolare studieremo la trasmissione
randomizzata sull’ipercubo e sui grafi random.
Capitolo 1
Grafi Random
1.1 Nozioni preliminari di probabilita` e notazioni
In questo paragrafo richiamiamo alcune nozioni di calcolo delle probabilita` di
cui avremmo bisogno in seguito.
Uno spazio di probabilita` e` definito da una tripla (Ω,Σ,Pr), dove Ω e` un in-
sieme, Σ e` una σ-algebra di eventi in Ω, Pr e` una misura non negativa su Ω
e Pr(Ω) = 1. Nel caso piu` semplice Ω e` un insieme finito,|Ω| = n, e Σ e` P(Σ),
l’insieme di tutti i sottoinsiemi di Ω. Allora Pr e` determinato dalla funzione
Ω → [0, 1], ω → Pr({ω}), ossia
Pr[A] =
∑
ω∈A
Pr({ω}) A ⊂ Ω
Nel seguito, penseremo a Ω numerabile, |Ω| → ∞ per n →∞.
Sia (Ω,Σ,Pr) uno spazio di probabilita` e X una variabile aleatoria definita su
di esso, denotiamo con E[X] il valore atteso e con Var[X] la sua varianza, definita
1
CAPITOLO 1. GRAFI RANDOM 2
da
Var[X] = E[(X− E[X])2] = E[X2]− (E[X])2.
Proposizione 1.1.1 (Disuguaglianza di Markov) Sia X una variabile aleato-
ria con valore atteso E[X] e t > 0, si ha
Pr[|X| ≥ t] ≤ E[X]
t
.
2
Proposizione 1.1.2 (Disuguaglinza di Chebyshev generalizzata) Sia X
una variabile aleatoria e sia Φ(x) > 0 per x > 0 una funzione monotonamente
crescente, supponia-mo che E[Φ(|X|)] = M esista. Si ha
Pr[|X| ≥ t] ≤ MΦ(t) .
2
Teorema 1.1.1 (Lemma di Borel-Cantelli) Sia {An}n∈IN una successione
di eventi in uno spazio di probabilita`.
Poniamo A := lim
n→+∞ supAn.
Se
+∞∑
n=1
Pr(An) < +∞ ⇒ Pr(A) = 0.
Se {A}n∈IN e` una successione di eventi indipendenti, allora:
se
+∞∑
n=1
Pr(An) = +∞ ⇒ Pr(A) = 1.
2
CAPITOLO 1. GRAFI RANDOM 3
Principio di inclusione-esclusione
Definizione 1.1.1 Data una famiglia {A1, . . . ,An} di parti di un insieme Ω,
che sara` per ipotesi un insieme finito, definiamo i coefficienti
F(k) =
∑
|T|=k
|
⋂
i∈T
Ai| F(o) = |Ω|
dove la somma e` estesa a tutte le k-parti T di n. Le formule equivalenti
|A1 ∪ . . . ∪ An| = F(1) + · · ·+ (−1)nF(n)
|A1 ∩ . . . ∩ An| = F(o) + · · ·+ (−1)nF(n)
costituiscono il principio di inclusione-esclusione.
Sia (Ω,Σ,Pr) uno spazio di probabilita`, sia X una variabile aleatoria semplice
a valori in IN, espressa come somma di funzioni indicatrici X1, . . . ,Xn degli eventi
A1, . . . ,An, ossia si abbia
X = X1 + · · ·+Xn
Definiamo per ogni intero positivo r
F(r) =
∑
Pr[Al1 ∩ . . . ∩ Alr ] =
∑
E[Xl1 · · ·Xlr ] F(o) = 1
dove la somma e` su tutti i distinti 1 ≤ l1 < · · · < lr ≤ n, cioe` su tutti gli r-sottoin-
siemi di {1, . . . , n} ovvero : il coefficiente F(r) e` uguale alla somma delle probabilita`
di tutte le intersezioni ”a k a k” degli n eventi A1, . . . ,An.
Proposizione 1.1.3 (Inclusione-esclusione)
Pr[X = 0] = Pr[A1 ∩ . . . ∩ An] =
n∑
k=0
(−1)kF(k) = 1−
n∑
k=1
(−1)kF(k).
2
CAPITOLO 1. GRAFI RANDOM 4
Proposizione 1.1.4 (Disuguaglianza di Bonferroni) Per ogni s
2s−1∑
j=0
(−1)jF(j) ≤ Pr[X = 0] ≤
2s∑
j=0
(−1)jF(j).
2
Distribuzione binomiale
Sia (Ω,Σ,Pr) uno spazio di probabilita`, sia X una variabile aleatoria definita
su di esso, X e` una variabile aleatoria di Bernoulli con valore atteso p se X puo`
avere solo i due valori, 0 e 1, e Pr(X=1)=p, Pr(X=0)=1-p. Assumiamo 0 < p < 1
e q=1-p.
Sia X1,X2, . . . ,Xn una successione di variabili aleatorie di Bernoulli indipendenti,
ognuna delle quali ha valore atteso p. Allora la variabile aleatoria somma
Sn,p =
n∑
i=1
Xi
soddisfa
Pr[Sn,p = k] =
(
n
k
)
pkqn−k k = 0, 1, . . . , n
e diciamo che Sn,p ha una distribuzione binomiale (o di Bernoulli) con parametri
n e p. Indicheremo cio` con la seguente notazione Sn,p ∼ B(n, p), in seguito, si
scrivera` in questo modo per indicare che una variabile aleatoria ”e` distribuita
come” una binomiale. Poiche` E[Xi] = p e Var[Xi] = pq, la distribuzione binomiale
con parametri n e p ha valore medio E[Sn,p] = np e varianza Var[Sn,p] = npq.
Convergenza della distribuzione binomiale alla distribuzione di Poisson
Se λ e` una costante positiva e p dipende da n in modo tale che pnn → λ per
n → +∞, allora la distribuzione binomiale con parametri n e p tende alla di-
stribuzione di Poisson con valore medio λ.
CAPITOLO 1. GRAFI RANDOM 5
Piu` precisamente consideriamo a tale proposito una successione {pn} in (0,1), e sia
B(n, pn) il valore assunto dalla distribuzione binomiale per la coppia di parametri
(n, pn). Allora se
lim
n→+∞ npn = λ con λ ∈ (0,+∞)
lim
n→+∞B(n, pn) =
λk
k!
e−λ k = 1, 2, . . .
E` utile introdurre le seguenti notazioni, poiche` molti dei nostri risultati saranno
asintotici. Queste stesse notazioni saranno usate per descrivere il tempo asintotico
di esecuzione di un algoritmo.
Definizione 1.1.2 Notazioni asintotiche standard:
1. f(n) = O(g(n)) se e solo se esistono due costanti positive c ed no tali che
|f(n)| ≤ c |g(n)| ∀ n ≥ no
2. f(n) = Ω(g(n)) se e solo se esistono due costanti positive c e no tali che
|f(n)| ≥ c |g(n)| ∀ n ≥ no
3. f(n) = Θ(g(n)) se f(n) = O(g(n)) e f(n) = Ω(g(n))), ossia se e solo se
esistono tre costanti positive c1, c2, no tali che
c1 |g(n)| ≤ f(n) ≤ c2 |g(n)| ∀ n ≥ no
4. f(n) = o(g(n)) se e solo se
lim
n→∞
f(n)
g(n)
= 0
CAPITOLO 1. GRAFI RANDOM 6
5. f(n) ∼ g(n) se e solo se
lim
n→∞
f(n)
g(n)
= 1
Scriveremo in alcuni casi f(n) = (1 + o(1))g(n).
Nei nostri calcoli avremo spesso bisogno della formula di Stirling nella forma
seguente:
n! =
(n
e
)n√
2pin
(
1 + 1
12n
+ Θ
(
1
n2
))
.
Utilizzando la notazione asintotica standard si ha l’espressione piu` usuale della
formula di Stirling:
n! ∼
(n
e
)n√
2pin .
1.2 Modelli di Grafi Random
Lo studio dei Grafi Random combina il calcolo delle probabilita` e la teoria dei
grafi. Divenne materia di studio nel 1960 con l’articolo di Paul Erdo¨s e Alfred
Re´nyi, ”On the Evolution of Random Graphs” [ErR60] .
Molti risultati sui grafi random riguardano grafi random etichettati, in parte
perche` i grafi etichettati sono piu` facili da trattare ma anche perche`, la maggior
parte dei risultati sui grafi random etichettati possono facilmente essere trasferiti
ai grafi random non etichettati.
Nel seguito, consideremo grafi random non diretti, senza cappi e senza archi mul-
tipli.
Definizione 1.2.1 Un grafo etichettato G e` definito dalla coppia (V,E) dove
V = {v1, v2, . . . , vn} e` un insieme finito non vuoto di elementi chiamati nodi (o
vertici) e E e` un sottonsieme delle
(
n
2
)
coppie non ordinate di elementi distinti di
CAPITOLO 1. GRAFI RANDOM 7
V, gli elementi di E vengono chiamati archi (o spigoli). Il numero n di vertici e`
detto ordine di G, mentre il numero M di archi e` detto dimensione di G.
Sia Gn,M l’insieme dei grafi etichettati di ordine n e dimensione M con vertici
l’insieme V, il numero di tali grafi e` il numero di M sottoinsiemi delle N =
(
n
2
)
coppie non ordinate di vertici, ossia
|Gn,M| =
(
N
M
)
con 0 ≤ M ≤ N. Sia Gn l’insieme di tutti i grafi etichettati di ordine n con vertici
l’insieme V, il numero di tali grafi e` il numero totale dei sottoinsiemi sopra descritti
ossia
|Gn| = 2N.
Definizione 1.2.2 Due grafi G = (V,E) e G′ = (V,E′) si dicono isomorfi,
scriveremo G ' G′, se esiste una funzione biunivoca f : V → V′ tale che
(u, v) ∈ E ⇔ (f(u), f(v)) ∈ E′.
La funzione f e` detta un isomorfismo da G a G′. Poiche` un isomorfismo e` una
relazione di equivalenza, i 2N grafi etichettati di ordine n con vertici l’insieme V
sono suddivisi in classi di isomorfismo chiamati grafi non etichettati.
Definizione 1.2.3 Un grafo in cui ogni coppia di nodi distinti ha un arco che
li congiunge viene chiamato grafo completo. Un grafo completo con n nodi
denotato con Kn ha quindi
(
n
2
)
archi; un grafo con n nodi e nessun arco viene
denotato con En.
Nello studio dei grafi random considereremo due modelli che indicheremo
rispettivamente con, G(n,M) e G(n,Pr(arco) = p) o piu` brevemente con G(n, p).
CAPITOLO 1. GRAFI RANDOM 8
Il primo e` composto di tutti i grafi con vertici l’insieme V = {v1, v2, . . . , vn} e
dimensione M, nel quale i grafi hanno la stessa probabilita`. Gli M archi vengono
scelti a caso tra gli N =
(
n
2
)
possibili archi, quindi G(n, p) ha
(N
M
)
elementi.G(n,M)
e` quindi uno spazio di probabilita` composto di tutti i grafi con un dato insieme di n
vertici etichettati e M archi dove a ogni tale grafo e` assegnata la stessa probabilita`
(
N
M
)−1
.
In generale M e` una funzione di n: M=M(n).
In particolare se M=0 abbiamo G(n,M) = {En} e se M=N si ha G(n,M) = {Kn}.
Il secondo modello e` composto di tutti i grafi con vertici l’insieme
V = {v1, v2, · · · , vn} nel quale gli archi sono scelti indipendentemente e con proba-
bilita` p, 0 ≤ p ≤ 1. G(n, p) e` quindi uno spazio di probabilita` sull’insieme dei grafi
sull’insieme dei vertici con probabilita` generata da
Pr[{vi, vj} ∈ G] = p
con G ∈ G(n, p) e 0 ≤ i < j ≤ n. Questo modello ha 2N elementi e se Go ∈ Gn ha
m archi, allora
Pr({Go}) = Pr(G = Go) = pmqN−m
dove G ∈ G(n, p) e q=1-p. Nel modello G(n, p) la probabilita` p puo` essere una
costante ma generalmente dipende da n. In particolare G(n, 1/2) e` esattamente
Gn con tutti i grafi equiprobabili.
Si puo` anche pensare ad un modello dinamico per i grafi random. Al tempo 0
il grafo G non ha nessun arco. Associamo poi agli N =
(
n
2
)
possibili archi, i valori
p1, p2 · · · , pN scelti uniformemente in [0,1], e mutuamente indipendenti, supponia-
mo di ordinarli in modo crescente. Inizialmente tutti i potenziali archi (che pos-
siamo immaginare come una linea di comunicazione) sono ”sconnessi”. Pensiamo
CAPITOLO 1. GRAFI RANDOM 9
a 0 ≤ p ≤ 1 come a un valore che cresce con continuita` da 0 a 1. Quando p = p1
e se p1 6= 0 si crea l’arco ad esso associato, successivamente quando p = p2 e se
p2 6= 0 si crea il nuovo arco associato a p2 e cos`ı via. Certamente quando p=1 vi
sono tutti gli archi. Al tempo p il grafo di tutti chi archi ”accesi” ha distribuzione
G(n, p).
Osserviamo che in questo modo non vi saranno archi che si ”connettono” contem-
poraneamente e che al crescere di p , G(n, p) evolve da vuoto a pieno.
Nel loro articolo, Erdo¨s e Re´nyi denotano con G(n,M) il grafo random con
n vertici e precisamente M archi. Anche questo modello si puo` vedere dinamica-
mente: pensando di iniziare con nessun arco e aggiungendo archi casualmente uno
ad uno fin quando il grafo non diviene pieno. Generalmente, G(n,M) ha proprieta`
molto simili a quelle di G(n, p) con
p ∼ M(
n
2
) .
Erdo¨s e Re´nyi pensarono a un grafo random come a un organismo vivente che si
sviluppa acquisendo piu` e piu` archi come p o M crescono, e dimostrarono che una
certa proprieta` puo` apparire piuttosto improvvisamente in una certa fase dello
sviluppo e in un intorno molto limitato di p.
Notazione: Faremo spesso uso dell’accezione quasi sempre, per indicare che
un evento accade con Pr[An] → 1 per n →∞, diversamente da come solitamente
e` inteso nella letteratura ossia Pr[An] = 1 per tutti i valori di n tranne al piu` un
numero finito.
CAPITOLO 1. GRAFI RANDOM 10
1.3 Funzione soglia
Chiameremo un sottoinsieme Q di Gn una proprieta` dei grafi di ordine n se
G ∈ Q, H ∈ Gn e G ' H (Definizione 1.2.2) implica che H ∈ Q. Quindi l’affermazione
”G soddisfa Q” e` allora equivalente a ”G ∈ Q”. Cos`ı, ad esempio, la proprieta` di
essere connesso e` l’insieme {G ∈ Gn : G e` connesso}.
Definizione 1.3.1 Una proprieta` Q sara` detta monotona crescente o sem-
plicemente monotona se ogniqualvolta G ∈ Q e G ⊂ H allora anche H ∈ A.
Ad esempio la proprieta` di contenere un sottografo proprio, per esempio un
triangolo, un grafo completo o un ciclo di Hamilton, e` monotona crescente.
Data una qualunque proprieta` Q del grafo, si indica con Pr[G(n, p)| = Q] la proba-
bilita` che G(n, p) soddisfi Q. Quando Q e` monotona, Pr[G(n, p)| = Q] e` una fun-
zione monotona di p.
Esempio: Sia A l’evento ”G(n, p) e` senza triangoli”. Per ogni insieme S di
tre vertici di G(n, p), sia AS l’evento che S e` un triangolo e sia XS la sua funzione
indicatrice si ha che
E[XS] = Pr[AS] = p3
sia X il numero dei triangoli contenuti in G(n, p) cosicche`:
X =
∑
|S|=3
XS
ossia la somma su tutti gli insiemi S di tre vertici.
Per la linearita` del valore atteso si ha
E[X] =
∑
|S|=3
E[XS] =
(
n
3
)
p3 ∼ n
3p3
6
CAPITOLO 1. GRAFI RANDOM 11
affinche` E[X] = Θ(1) dovrebbe essere p=c/n, con c costante positiva.
Allora
lim
n→∞E[X] = limn→∞
(
n
3
)
p3 = c
3
6
poniamo
m =
(
n
3
)
s = p3.
Se gli XS fossero mutuamente indipendenti allora, poiche` X ha distribuzione
binomiale B(m, s) viene approssimata per n ”grande” e p ”piccolo” dalla di-
stribuzione di Poisson.
Quindi
lim
n→∞Pr[G(n, p)| = A] = limn→∞Pr[X = 0] = e
−c3/6
.
Poiche`
lim
c→0 e
−c3/6 = 1
lim
c→∞ e
−c3/6 = 0.
Quando p = 10−6/n e` quindi molto improbabile che G(n, p) ha triangoli, mentre
quando p = 106/n e` molto probabile che ne` abbia.
Nel punto di vista dinamico , il primo triangolo appare quasi sempre per
p = Θ(1/n).
Quando p(n) À n−1 per esempio, p(n) = n−.9 allora G(n, p) avra` quasi sempre
triangoli, ossia la probabilita` che contenga un triangolo tende a 1 per n che tende
a infinito. Similmente quando p(n) ¿ n−1 per esempio, p(n) = 1/n log n allora
G(n, p) quasi sempre non conterra` triangoli.
In seguito indicheremo con ’log’ il logaritmo naturale e con ”lg” il logaritmo in
base 2.