Grafico casuale

In matematica , un grafico casuale è un grafico generato da un processo casuale . Il primo modello di grafici casuali è stato reso popolare da Paul Erdős e Alfréd Rényi in una serie di articoli pubblicati tra il 1959 e il 1968.

I due modelli base di Erdős e Rényi

Il modello di Erdős e Rényi riunisce infatti due modelli, formalmente diversi, ma strettamente correlati. In entrambi i modelli,

l'insieme dei vertici è ${1, 2, 3, ..., n }$ denotato da quanto segue ; ${\ displaystyle \ [\! [n] \!]}$
gli archi potenzialmente presenti sono le $n ( n -1) / 2$ parti a due elementi di ; a volte si nota l'insieme di questi margini , tuttavia si noterà $J$ per comodità tipografica e per coerenza con l'articolo sulla disuguaglianza di Harris . ${\ displaystyle \ [\! [n] \!]}$ ${\ displaystyle {[\! [n] \!] \ scegli 2}.}$
quindi, il grafo casuale è non orientato e non ha loop o bordi multipli .

Il grafico casuale binomiale

In questo modello, spesso ciascuno degli $archi n$ $($ $n$ $-1) / 2$ è presente con probabilità $p$ , assente con probabilità $1-$ $p$ , indipendentemente dallo stato degli altri archi. Il caso $p$ $= 0,5 è$ stato studiato da Erdős già nel 1947. Il numero $N$ $p$ di archi segue la distribuzione binomiale dei parametri $n$ $($ $n$ $-1) / 2$ e $p$ . ${\ displaystyle \ mathbb {G} (n, p),}$ ${\ displaystyle \ mathbb {G} (n, p)}$

Il grafico casuale uniforme

In questo modello, spesso notato, un sottoinsieme di M archi viene scelto uniformemente tra i possibili archi $n$ $($ $n$ $-1) / 2$ . Quando un grafo G con n vertici ha M archi, la probabilità di G è data da ${\ displaystyle \ mathbb {G} (n, M),}$

{\ displaystyle \ mathbb {P} (G) \ = \ {\ frac {1} {{n \ scegli 2} \ scegli M}}.}

Questo è il modello studiato principalmente nella serie di articoli fondamentali pubblicati da Erdős e Rényi tra il 1959 e il 1968. ${\ displaystyle \ mathbb {G} (n, M)}$

I due processi casuali con i valori del grafico

Possiamo partire da un grafo senza spigoli, quindi completamente scollegato, e aggiungere uno spigolo disegnato a caso in modo uniforme, poi un altro, ecc. , senza sostituzione. Otteniamo così una sequenza crescente (nel senso dell'inclusione dell'insieme di archi), di $1 +$ $n$ $($ $n$ $-1) / 2$ grafi casuali, che forma un processo a tempo discreto con valori nell'insieme dei grafici . Ogni termine nella sequenza è un grafico casuale uniforme definito nella sezione precedente. Un vantaggio di questa costruzione è quello di vedere coesistere diversi grafi casuali con parametri M differenti , sullo stesso spazio probabilizzato, e quindi poter confrontare le loro caratteristiche, non come media o in diritto, ma per ogni elemento prob dello spazio probabilizzato considerato. Ciò rende possibile ragionare per accoppiamento. ${\ displaystyle \ {\ mathbb {G} (n, M) \} _ {0 \ leq M \ leq n (n-1) / 2},}$
Possiamo anche associare ad ogni arco e di J una variabile casuale $T e$ , il peso del bordo, in modo che la famiglia $( T e ) e \in J$ sia una famiglia di variabili casuali iid, ad esempio con legge uniforme su l ' intervallo [0, 1]. Indichiamo quindi il grafico formato dai bordi il cui peso è inferiore a p . Per ogni bordo, questo avviene con probabilità ${\ displaystyle \ mathbb {G} (n, p)}$

{\ displaystyle \ mathbb {P} (T_ {e} \ leq p) \ = \ p.}

Si ottiene così una famiglia crescente, di grafi casuali, che forma un processo temporale continuo, con valori nell'insieme dei grafici. Questa famiglia è in aumento nel senso dell'inclusione dell'insieme di archi: un arco e presente in è presente anche in poiché Ogni termine della famiglia di grafi è un grafo casuale binomiale definito in precedenza.

{\ displaystyle \ {\ mathbb {G} (n, p) \} _ {0 \ leq p \ leq 1},}

{\ displaystyle \ mathbb {G} (n, p)}

{\ displaystyle \ mathbb {G} (n, p + \ varepsilon), \ \ varepsilon> 0,}

{\ displaystyle \ {T_ {e} \ leq p \} \ \ Rightarrow \ \ {T_ {e} \ leq p + \ varepsilon \}.}

Metafora. Possiamo immaginare i vertici del grafo come n isole su un lago, comunicanti con l'ausilio di passerelle (bordi e ), sommerse alle rispettive profondità $T e$ sotto la superficie dell'acqua. Se il lago si svuota gradualmente delle sue acque, vedremo gradualmente emergere i ponti e si formeranno le relative componenti che riuniscono sempre più isole.

Collegamenti tra i due modelli

In virtù del teorema del limite centrale , o disuguaglianza di Hoeffding , la distribuzione binomiale è molto concentrata attorno alla sua aspettativa. Più precisamente, il numero di archi $N p$ di un grafo di legge aleatoria è quindi molto vicino a specialmente se quest'ultima quantità è grande davanti a n : infatti, ${\ displaystyle \ mathbb {G} (n, p)}$ ${\ displaystyle {\ hat {M}} = \ left \ lfloor p \ {n \ scegli 2} \ right \ rfloor}$ ${\ hat {M}}$

{\ displaystyle \ forall t> 0, \ qquad \ mathbb {P} \ left (\ left | N_ {p} - {\ hat {M}} \ right | \ geq tn \ right) \ \ leq \ 2 \, \ mathrm {e} ^ {- 2t ^ {2}}.}

Inoltre, la distribuzione condizionale di sapere che $N$ $p$ $= M$ è precisamente Per questo motivo, se $M$ è vicino a , o, in modo equivalente, se ${\ displaystyle \ \ mathbb {G} (n, p)}$ ${\ displaystyle \ mathbb {G} (n, M).}$ ${\ hat {M}}$

{\ displaystyle p \ simeq {\ frac {2M} {n (n-1)}},}

è generalmente accettato (e spesso dimostrato) che i due modelli e abbiano proprietà molto simili. ${\ displaystyle \ mathbb {G} (n, p)}$ ${\ displaystyle \ mathbb {G} (n, M)}$

Andando oltre, sia $T ( k )$ il valore k -esimo della sequenza una volta che quest'ultima sequenza è disposta in ordine crescente: la sequenza è chiamata la sequenza delle statistiche di ordine della sequenza Quando p assume il valore casuale $T$ $($ $M$ $)$ , quindi è esattamente Per corroborare le osservazioni precedenti, notare che $T$ $($ $M$ $)$ è molto vicino a nel senso che, come conseguenza dei famosi risultati di Donsker e Kolmogorov , la probabilità ${\ displaystyle (T_ {e}) _ {e \ in J}}$ ${\ displaystyle (T _ {(k)}) _ {1 \ leq e \ leq n (n-1) / 2}}$ ${\ displaystyle (T_ {e}) _ {e \ in J}.}$ ${\ displaystyle \ mathbb {G} (n, T _ {(M)})}$ ${\ displaystyle \ mathbb {G} (n, M).}$ ${\ displaystyle 2M / n (n-1),}$

{\ Displaystyle \ varphi _ {n} (x) = \ mathbb {P} \ left (\ sup _ {1 \ leq M \ leq n (n-1) / 2} \ left \ {| T _ {(M )} - {\ tfrac {2M} {n (n-1)}} | \ right \} \ geq {\ tfrac {x {\ sqrt {2}}} {n}} \ right)}

soddisfatto

{\ Displaystyle \ exp (-2x ^ {2}) \ \ leq \ \ liminf _ {n} \ varphi _ {n} (x) \ \ leq \ \ limsup _ {n} \ varphi _ {n} (x ) \ \ leq \ 2 \ sum _ {r = 1} ^ {+ \ infty} (- 1) ^ {r-1} \ exp (-2r ^ {2} x ^ {2}),}

il 1 ° e 4 th termini essendo le code della distribuzione dei Rayleigh e Kolmogorov leggi , rispettivamente: in sintesi, l'estremo superiore (quando M varia) degli errori è dell'ordine di 1 / n . ${\ displaystyle | T _ {(M)} - 2M / n (n-1) |}$

Ordine e crescita

Un grafico può essere visto come una parte del set J di bordi, quindi lo spazio probabilità è qui Ohm tutte le parti di J , che a volte può identificare ${0,1} J$ . Questa identificazione è particolarmente utile quando vogliamo applicare la disuguaglianza di Harris .

L'inclusione è una relazione di ordine parziale su Ω.
Come al solito, una mappa X definita su Ω, con valori reali, si dice crescente se

{\ displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \} \ quad \ Rightarrow \ quad \ {X (\ omega) \ leq X (\ omega ^ {\ prime}) \}.}

Si dice che una parte A di Ω sia crescente se

{\ displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \ {\ text {e}} \ \ omega \ in A \} \ quad \ Rightarrow \ quad \ {\ omega ^ {\ prime} \ in A \}.}

Allo stesso modo, si dice che una parte A di Ω aumenta se la sua funzione di indicatore è in aumento.

La proprietà di decadimento di un'applicazione o di una parte ha una definizione analoga.

Esempi:

Tra le proprietà e i parametri di un grafico,

la connessione sta aumentando, ad es. la parte A di Ω composta da tutti i grafi connessi, è una parte crescente di Ω: se aggiungiamo un arco a un grafo connesso, il grafo così ottenuto è ancora connesso;
la planarità è in diminuzione: se togliamo uno spigolo da un grafo planare, il grafo così ottenuto è ancora planare;
il numero cromatico è in aumento;
il numero di stabilità sta diminuendo;
la proprietà senza triangolo sta diminuendo.

Abbiamo la seguente disuguaglianza:

Disuguaglianza di Harris - Nel quadro del grafo casuale binomiale ,

vale a dire due variabili casuali X e Y crescenti su Ω. Allora

{\ Displaystyle \ mathbb {E} [XY] \ geq \ mathbb {E} \ sinistra [X \ destra] \ mathbb {E} [Y] \,;}

vale a dire due parti crescenti A e B di Ω. Allora

{\ Displaystyle \ mathbb {P} (A \ cap B) \ geq \ mathbb {P} (A) \ mathbb {P} (B).}

Appunti:

Ciò equivale a dire che esiste una correlazione positiva tra le variabili interessate, poiché possiamo riformulare la prima disuguaglianza nella seguente forma utilizzando la covarianza :

{\ displaystyle {\ text {Cov}} \ sinistra (X, Y \ destra) \ \ geq \ 0.}

La disuguaglianza vale anche per variabili o parti decrescenti, ma il significato delle disuguaglianze cambia quando le variabili o le parti coinvolte hanno significati opposti di monotonia.

Connettività

La soglia di connettività

Teorema (Erdős, Rényi, 1960) - Poniamo $a n = np ( n ) - ln n$ , o ancora:

{\ displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}}.}

Se allora ${\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}$ ${\ Displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ è ~ correlato} \ right) = 1.}$
Se allora ${\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ Displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ è ~ correlato} \ right) = 0.}$

Diciamo che $ln ( n ) / n$ è una soglia stretta per la proprietà di connettività, ristrettezza riferita al fatto che la proprietà è soddisfatta anche se tende all'infinito strettamente meno rapidamente di $anno$ ${\ displaystyle \ ln n.}$

Dimostrazione

Ci diamo un grafo aleatorio G n con legge e un grafo aleatorio con legge Il teorema segue dal teorema del doppio esponenziale , che a sua volta deriva dall'enumerazione di punti isolati effettuata nella sezione seguente. La connettività è una proprietà in aumento , quindi, non appena n è sufficientemente grande ${\ Displaystyle \ mathbb {G} \ left (p (n), n \ right)}$ ${\ displaystyle {\ tilde {G}} _ {n}}$ ${\ displaystyle \ mathbb {G} \ left ({\ tilde {p}} (n), n \ right).}$

{\ displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}} \ quad \ geq \ quad {\ frac { \ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {n}} \ = \ {\ tilde {p}} (n),}

abbiamo anche

{\ displaystyle \ mathbb {P} \ left (G_ {n} \ mathrm {~ è ~ correlato} \ right) \ geq \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm { ~ è ~ correlato} \ right).}

Infatti, anche se ciò significa costruire e usare la stessa uniforme variabili IID , sullo stesso spazio Ω probabilized, come indicato nella sezione “I due processi casuali con valori grafico” , si ha, per tutti ω di Ω, $G_ {n}$ ${\ displaystyle {\ tilde {G}} _ {n}}$ ${\ displaystyle (U_ {e}) _ {e \ in J}}$

{\ displaystyle G_ {n} (\ omega) \ supset {\ tilde {G}} _ {n} (\ omega),}

pertanto

{\ displaystyle \ left \ {{\ tilde {G}} _ {n} (\ omega) {\ text {è correlato}} \ right \} \ Rightarrow \ left \ {G_ {n} (\ omega) \ mathrm {~ è ~ correlato} \ right \},}

{\ displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ è ~ correlato} \ right) \ leq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ è ~ correlato} \ right).}

Se ne consegue che, per qualsiasi numero reale c , ${\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}$

{\ displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ è ~ correlato} \ right) \ geq \ mathrm { e} ^ {- \ mathrm {e} ^ {- c}},}

o anche

{\ Displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ è ~ correlato} \ right) \ geq \ sup \ sinistra \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ destra \} \ = \ 1.}

D'altra parte, se allora, per n sufficientemente grande, avremo, per tutti ω , e ${\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ displaystyle G_ {n} (\ omega) \ subset {\ tilde {G}} _ {n} (\ omega),}$

{\ displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ è ~ correlato} \ right) \ geq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ è ~ correlato} \ right).}

Quindi, per qualsiasi numero reale c ,

{\ displaystyle \ limsup _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ è ~ correlato} \ right) \ leq \ inf \ sinistra \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ destra \} \ = \ 0.}

Enumerazione di punti isolati

È più facile (più probabile) riuscire a tagliare le n - 1 connessioni tra un punto e il suo complemento, rispetto alle k ( n - k ) connessioni tra un gruppo di k punti e il suo complemento, perché la funzione $f ( k ) = k ( n - k )$ aumenta molto rapidamente intorno a 1, quindi, all'aumentare di k , molti più bordi da tagliare e una probabilità molto inferiore di tagliarli tutti con successo. Come corollario, con la scelta del parametro p fatta sopra, il grafo G ( n , p ) risulterà non connesso “quasi solo” se ha punti isolati, nel senso che la probabilità di essere connesso è molto vicina a la probabilità di non avere punti isolati, che è approssimativamente $uguale a$ $e$ $-e$ $-$ $c$ Infatti, abbiamo il seguente risultato: ${\ displaystyle \ mathbb {P} \ sinistra (X_ {n} = 0 \ destra),}$

Punti isolati (Erdős, Rényi, 1960). - Supponi che

{\ displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {non}}.}

Allora il numero $X n$ di punti isolati del grafo converge di diritto verso una distribuzione di Poisson del parametro $e$ $-$ $c$ . ${\ displaystyle G \ sinistra ({\ tilde {p}} (n), n \ destra)}$

Dimostrazione

In ciò che segue, abbreviamo in e ci poniamo ${\ displaystyle G \ sinistra ({\ tilde {p}} (n), n \ destra)}$ ${\ displaystyle {\ tilde {G}} _ {n},}$

{\ displaystyle \ mu = \ mathrm {e} ^ {- c}.}

Sia $X n$ il numero di punti isolati di Lo sappiamo ${\ displaystyle {\ tilde {G}} _ {n}.}$

{\ displaystyle X_ {n} = Y_ {1} + Y_ {2} + \ dots + Y_ {n},}

{\ displaystyle Y_ {i} = 1 _ {\ mathrm {il ~ vertice ~} i \ mathrm {~ è ~ isol {\ acute {e}}}}.}

Usiamo il metodo dei momenti fattoriali. Sia $I n , A$ l'insieme delle iniezioni di in For all $[\! [1, n] \!]$ $A.$ ${\ displaystyle r \ geq 1,}$

{\ displaystyle (X_ {n}) _ {r} = (Y_ {1} + Y_ {2} + \ dots + Y_ {n}) _ {r} = \ sum _ {\ varphi \ in I_ {r, [\! [1, n] \!]}} \ \ Prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}.}

I termini della somma precedente appaiono effettivamente nell'espansione di ma, a parte questi termini, questa espansione fa emergere molti altri termini che apparentemente entrano in conflitto. In effetti, neanche ${\ displaystyle \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}}$ ${\ displaystyle (Y_ {1} + Y_ {2} + \ dots + Y_ {n}) _ {r},}$

{\ displaystyle E = \ left \ {a \ in [\! [1, n] \!] \, | \, Y_ {a} = 1 \ right \}.}

Allora

{\ displaystyle \ forall \, \ varphi \ in I_ {r, [\! [1, n] \!]}, \ qquad \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i) } = 1 _ {\ varphi \ in I_ {r, E}},}

pertanto

{\ Displaystyle \ sum _ {\ varphi \ in I_ {r, [\! [1, n] \!]}} \ \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ = \ | I_ {r, E} | \ = \ (| E |) _ {r} \ = \ (X_ {n}) _ {r}.}

Inoltre, per simmetria,

{\ displaystyle \ mathbb {E} \ left [\ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ right] \ = \ \ mathbb {E} \ left [\ prod _ { i = 1} ^ {r} Y_ {i} \ right] = (1 - {\ tilde {p}} (n)) ^ {r (n-1) -r (r-1) / 2},}

dove $r ( n -1)$ è il numero di archi potenzialmente risultanti da un vertice di E , e dove $r ( r -1) / 2$ è il numero di archi tra due vertici di E , cioè. quelli che vengono contati il doppio nel totale $r ( n -1)$ . In tal modo

{\ displaystyle {\ begin {align} \ mathbb {E} \ left [(X_ {n}) _ {r} \ right] & = (n) _ {r} (1 - {\ tilde {p}} ( n)) ^ {r (n-1) -r (r-1) / 2} \\ & \ simeq n ^ {r} (1 - {\ tilde {p}} (n)) ^ {r (n -1)} \\ & = \ left (n (1 - {\ tilde {p}} (n)) ^ {n-1} \ right) ^ {r} \\ & \ simeq \ mu ^ {r} . \ end {allineato}}}

Pertanto, con il metodo dei momenti, $X n$ converge di diritto a una distribuzione di Poisson con parametro μ , e

{\ Displaystyle \ lim \ mathbb {P} \ left (X_ {n} = 0 \ right) \ = \ \ mathrm {e} ^ {- \ mu} \ = \ \ mathrm {e} ^ {- \ mathrm { e} ^ {- c}}.}

Questo teorema è un esempio lampante del paradigma Fish , che, quando presenta molte opportunità di osservare un evento raro ( cioè d. Improbabile), il numero totale di eventi rari effettivamente osservati segue una legge di Poisson .

Il teorema del doppio esponenziale

Erdős e Rényi deducono un risultato più preciso rispetto alla proprietà della soglia stretta:

Teorema della doppia esponenziale (Erdős, Rényi, 1960) - Supponi che

{\ displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {non}}.}

Allora

{\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left ({\ tilde {p}} (n), n \ right) \ mathrm {~ è ~ correlato} \ right ) = e ^ {- e ^ {- c}}.}

Dimostrazione Se è senza punto isolato, e quindi ci sono poche possibilità che sia qualcosa di diverso da connesso (cfr. Spencer, 10 lezioni su grafici casuali ). Infatti, sia B una parte di e sia k il suo cardinale. Indichiamo l'evento " B è una componente connessa di ". L'evento può essere visto come l'unione (non disgiunta) di

k

k

-2

sottoinsiemi di probabilità

{\ displaystyle X_ {n} = 0,}

{\ displaystyle {\ tilde {G}} _ {n}}

{\ displaystyle {\ tilde {G}} _ {n}}

[\! [1, n] \!]

{\ displaystyle {\ mathcal {C}} _ ​​{B}}

{\ displaystyle {\ tilde {G}} _ {n}}

{\ displaystyle {\ mathcal {C}} _ ​​{B}}

{\ displaystyle {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)},}

che porta al seguente aumento:

{\ displaystyle \ mathbb {P} ({\ mathcal {C}} _ ​​{B}) \ \ leq \ k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)}.}

Indica qui il numero di possibili spanning tree per un grafo connesso i cui vertici sarebbero gli elementi di B , o anche, in modo equivalente, il numero di possibili scelte di una famiglia di k -1 archi che rende correlato l'insieme B. Inoltre, è la probabilità che gli spigoli k -1 dello spanning tree considerato siano effettivamente presenti, ed è la probabilità che non sia presente alcun arco che collega un vertice di B ad un vertice di B c , tale che B cioè non solo connesso , ma anche massima tra le parti connesse del grafico. ${\ displaystyle k ^ {k-2}}$ ${\ displaystyle {\ tilde {p}} (n) ^ {k-1}}$ ${\ displaystyle (1 - {\ tilde {p}} (n)) ^ {k (nk)}}$

L'evento

{\ displaystyle D_ {n} = \ {X_ {n} = 0 \ mathrm {~ mais ~} {\ tilde {G}} _ {n} \ mathrm {~ n} ^ {\ prime} \ mathrm {est ~ non ~ correlato} \}}

controllato

{\ displaystyle D_ {n} \ subset \ bigcup _ {2 \ leq | B | \ leq n / 2} {\ mathcal {C}} _ ​​{B}.}

Infatti, sotto l'ipotesi D n , ha più componenti connesse, quindi la più piccola di esse (nel senso del numero di vertici) ha al massimo n / 2 vertici, ma questa più piccola componente connessa ha almeno due vertici, poiché $X$ $n$ $= 0$ . In tal modo ${\ displaystyle {\ tilde {G}} _ {n}}$

{\ displaystyle {\ begin {align} \ mathbb {P} (D_ {n}) & \ leq \ sum _ {2 \ leq | B | \ leq n / 2} \ mathbb {P} ({\ mathcal {C }} _ {B}) \\ & \ leq \ sum _ {2 \ leq k \ leq n / 2} {n \ scegli k} k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)} \\ & \ leq \ sum _ {2 \ leq k \ leq n / 2} u_ {k}. \ end {allineato}}}

Tuttavia, per $α > 0$ ,

{\ displaystyle {\ begin {allineato} u_ {2} & \ leq n ^ {- 1+ \ alpha} \, \ ln n \ end {allineato}}}

non appena

{\ Displaystyle \ ln n \ geq \ max \ left [c + \ varepsilon (n) \ ,, (- 2c-2 \ varepsilon (n) +4 {\ tilde {p}} (n)) / \ alpha \ a destra].}

Proprio come un componente connesso di dimensione maggiore di 2 è molto meno probabile di un componente connesso di dimensione 1, un componente connesso di dimensione maggiore di 3 è molto meno probabile di un componente connesso di dimensione 2, il che si traduce in

Proprietà - Quando n tende all'infinito

{\ Displaystyle u_ {2} (n) \ \ gg \ \ sum _ {3 \ leq k \ leq n / 2} u_ {k} (n).}

Alcuni calcoli un po 'dolorosi, senza essere francamente difficili, portano a questo risultato.

Dimostrazione

Il limite dato sopra per $u 2 ( n )$ non è solo un limite superiore, ma di fatto fornisce l'ordine di grandezza di $u 2 ( n )$ . Per quanto riguarda il resto della somma, dobbiamo tagliarla in due prima di aumentare ciascuno dei due pezzi:

{\ displaystyle {\ begin {align} {\ frac {u_ {k + 1}} {u_ {k}}} & = (nk) \, (1 + {\ tfrac {1} {k}}) ^ { k-2} \, {\ tilde {p}} (n) \ times (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \\ & = (nk) \, ( e + {\ hat {\ varepsilon}} (k)) \, {\ tilde {p}} (n) \ times (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ \ & \ leq {\ hat {c}} \, \ ln n \ (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ end {allineato}}}

{\ displaystyle \ forall n, k, \ quad {\ hat {c}} \ geq (e + {\ hat {\ varepsilon}} (k)) \, {\ frac {n {\ tilde {p}} ( n)} {\ ln n}}.}

Per e ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}$ ${\ displaystyle k \ leq \ beta n,}$

{\ displaystyle {\ begin {align} {\ frac {u_ {k + 1}} {u_ {k}}} & \ leq {\ hat {c}} \, \ ln n \ \ exp \ left [- { \ tilde {p}} (n) (n-2k-1) \ right] \\ & \ leq {\ hat {c}} n ^ {- \ gamma} \ ln n, \ end {allineato}}}

non appena

{\ displaystyle \ ln n \ geq {\ frac {{\ tilde {p}} (n) + (c + \ varepsilon (n)) (2 \ beta -1)} {1-2 \ beta - \ gamma} }.}

Pertanto, per n sufficientemente grande, diminuisce più velocemente di una sequenza esponenziale della ragione quando e ${\ displaystyle u_ {k}}$ ${\ displaystyle {\ hat {c}} n ^ {- \ gamma} \ ln n,}$ ${\ displaystyle 2 \ leq k \ leq 1+ \ beta n,}$

{\ displaystyle \ sum _ {k = 2} ^ {1+ \ beta n} u_ {k} \ \ leq \ {\ frac {u_ {2}} {1 - {\ hat {c}} n ^ {- \ gamma} \ ln n}} \ \ leq \ 2n ^ {- 1+ \ alpha} \, \ ln n.}

Inoltre, per possiamo trovare c e ρ positiva, in modo tale che, per tutti ${\ displaystyle 0 <\ alpha <1/4,}$ ${\ displaystyle n \ geq 1,}$

{\ displaystyle {\ begin {allineato} u_ {n / 2} & \ leq c \, \ rho ^ {n} \, n ^ {- \ alpha n}. \ end {allineato}}}

Per e ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}$ ${\ displaystyle k \ geq \ beta n,}$

{\ displaystyle {\ begin {align} {\ frac {u_ {k-1}} {u_ {k}}} & \ leq {\ frac {d} {\ ln n}} \ \ exp \ left [{\ tilde {p}} (n) (n-2k + 1) \ right] \\ & \ leq {\ frac {d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}} { \ ln n}} \\ & \ leq d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}, \ end {allineato}}}

non appena n è abbastanza grande. Pertanto, per e abbastanza vicino a 0,5, abbastanza vicino a 1, ${\ displaystyle n / 2 \ geq k \ geq \ beta n,}$ $\beta$ ${\ displaystyle (1-2 \ beta) / \ gamma}$

{\ displaystyle {\ begin {align} - \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma) & <0, \\ {\ frac {u_ {k}} {u_ {n / 2}}} & \ leq d ^ {(1-2 \ beta) n / 2} n ^ {n (1-2 \ beta) ^ {3} / 2 \ gamma}, \\ u_ {k} & \ leq c \, {\ tilde {\ rho}} ^ {n} \, n ^ {(- \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma)) n}, \ end { allineato}}}

{\ Displaystyle \ sum _ {k = \ beta n} ^ {n / 2} u_ {k} \ \ leq \ c \, {\ hat {\ rho}} ^ {n} \, n ^ {(- \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma)) n} \ \ ll \ u_ {2}.}

Perciò

{\ displaystyle \ lim _ {n} \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ è ~ correlato} \ right) = \ lim _ {n} \ mathbb {P } \ sinistra (X_ {n} = 0 \ destra).}

Indichiamo con $T n$ il primo istante t in cui il grafo è connesso: ${\ Displaystyle \ mathbb {G} \ left (t, n \ right)}$

{\ displaystyle T_ {n} \ = \ \ inf \ left \ {t \ geq 0 \ | \ \ mathbb {G} (t, n) \ mathrm {~ è ~ correlato} \ right \},}

così che

{\ displaystyle \ left \ {\ mathbb {G} \ left (t, n \ right) \ mathrm {~ è ~ correlato} \ right \} \ quad \ Rightarrow \ quad \ left \ {T_ {n} \ leq t \ right \} \ quad \ Rightarrow \ quad \ left \ {\ forall \ varepsilon> 0, \ quad \ mathbb {G} \ left (t + \ varepsilon, n \ right) \ mathrm {~ è ~ correlato} \ right \}.}

Possiamo quindi vedere il teorema del doppio esponenziale come risultato sull'espansione asintotica di $T n$ : se $Z n$ è definito dalla seguente relazione:

{\ displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ {\ frac {Z_ {n}} {n}},}

quindi il teorema del doppio esponenziale afferma che $Z n$ converge di diritto verso la distribuzione di Gumbel , che potrebbe essere tradotta, in una versione probabilistica della notazione di Landau , da:

{\ displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ \ Theta \ left ({\ frac {1} {n}} \ right).}

L'infinito grafico casuale

Erdős e Rényi hanno generalizzato il modello binomiale al caso di un grafo infinito numerabile , mostrando che abbiamo quindi ottenuto ( quasi sicuramente ) un grafo che possiede proprietà di universalità (contenente in particolare qualsiasi grafo finito o numerabile come sottografo ); questo grafico è stato riscoperto più volte ed è più spesso noto come il grafico Rado .

Vedi anche

Appunti

Il primo articolo, pubblicato nel 1959 , è "On Random Graphs I", Publ. Matematica. Debrecen 6, 290.
(in) P. Erdős , " Alcune osservazioni sulla teoria dei grafi " , Bull. Amaro. Matematica. Soc. , vol. 53, n o 4,1947, p. 292-294 ( leggi in linea ). Questo articolo è spesso considerato come segno della nascita del "metodo probabilistico" per lo studio dei grafi non casuali, in particolare per la teoria di Ramsey .
Per lo sfondo, vedere (in) Mr. Karoński Ruciński e A., "Le origini della teoria dei grafi casuali" , in The Mathematics of Paul Erdős , Berlino, Springer al. "Algorithms Combin. "( N o 13),1997, p. 311-336.
Per maggiori dettagli, vedi Janson, Łuczak e Ruciński 2000 , cap. 2, "Probabilità esponenzialmente piccole".
Vedi Janson, Łuczak e Ruciński 2000 , sezione 1.4, "Equivalenza asintotica", p. 14.
Visualizza (in) Galen R. Shorack e Jon A. Wellner , Empirical Processes With Applications to Statistics , SIAM ,settembre 2009, 998 p. ( ISBN 978-0-89871-684-9 , leggi online ), sezione 3.8, "Limitazione delle distribuzioni nell'ipotesi nulla", p. 142 e cap. 18, "Il processo quantile standardizzato", p. 637.
Janson, Łuczak e Rucinski 2000 , Th. 6.7, p. 144.
Vedi l'articolo " Bijection de Joyal ", o Martin Aigner e Günter M. Ziegler, Divine Reasonings , 2 ° edizione, 2006, p. 195-201, la formula di Cayley per il numero di alberi .

Bibliografia

(en) Béla Bollobás , Random Graphs , Cambridge University Press,Gennaio 2001, 2 ° ed. ( 1 a ed. 1985), 516 p. ( ISBN 978-0-521-79722-1 , leggi in linea ).
(en) Svante Janson (en) , Tomasz Łuczak e Andrzej Ruciński, Random Graphs , Wiley-Interscience,Maggio 2000, 1 ° ed. , 333 p. , cartonato ( ISBN 978-0-471-17541-4 ).
(en) Joel Spencer (en) , "Nine lectures on random graphs" , in Summer School of Probability of Saint-Flour XXI-1991, Part 3 , Springer, coll. "Appunti delle lezioni in matematica. "( N o 1541)1993, p. 293-347.

Articolo correlato

Introduzione delle probabilità nella teoria dei grafi

Link esterno

Laurent Massoulié, Reti: controllo distribuito e fenomeni emergenti , 2015