Véletlenszerű grafikon

A matematika , a véletlen gráf egy grafikon , amely által generált véletlenszerű folyamat . A véletlenszerű grafikonok első modelljét Erdős Paul és Rényi Alfréd népszerűsítette az 1959 és 1968 között megjelent cikksorozatban.

Erdős és Rényi két alapmodellje

Erdős és Rényi modellje valójában két modellt hoz össze, formailag különbözőek, de szorosan kapcsolódnak egymáshoz. Mindkét modellben

a csúcsok halmaza ${1, 2, 3, ..., n },$ amelyet a következők jelölnek ; ${\ displaystyle \ [\! [n] \!]}$
a potenciálisan jelen lévő élek az $n ( n -1) / 2$ kételemes részei ; Ezeknek az éleknek a halmazát néha megjegyzik , $J-$ t azonban tipográfiai kényelem és a Harris-egyenlőtlenségről szóló cikkel való összhang érdekében meg kell jegyezni . ${\ displaystyle \ [\! [n] \!]}$ ${\ displaystyle {[\! [n] \!] \ select 2}.}$
így a véletlenszerű gráf irányítatlan , és nincs hurka vagy több éle .

A binomiális véletlenszerű gráf

Ebben a modellben gyakran az $n$ $($ $n$ $-1) / 2$ él mindegyike $p$ valószínűséggel van jelen, $1-$ $p$ valószínűséggel hiányzik , függetlenül a többi él állapotától. A $p$ $= 0,5$ esetet Erdős már 1947-ben tanulmányozta. Az élek $N$ $p$ száma követi az $n$ $($ $n$ $-1) / 2$ és $p$ paraméterek binomiális eloszlását . ${\ displaystyle \ mathbb {G} (n, p),}$ ${\ displaystyle \ mathbb {G} (n, p)}$

Az egységes véletlenszerű grafikon

Ebben a gyakran megjegyzett modellben az M élek egy részhalmazát egységesen választják ki a lehetséges $n$ $($ $n -$ $1) / 2$ él közül. Amikor egy grafikon G a n pontú M élek, a valószínűsége, hogy a G adják ${\ displaystyle \ mathbb {G} (n, M),}$

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

Ezt a modellt tanulmányozzák elsősorban Erdős és Rényi által 1959 és 1968 között megjelent alapvető cikkek sorozatában. ${\ displaystyle \ mathbb {G} (n, M)}$

A két véletlenszerű folyamat grafikonértékekkel

Kiindulhatunk egy élek nélküli, ezért teljesen leválasztott gráfról, és hozzáadhatunk egy véletlenszerűen rajzolt élt egységesen, majd még egyet stb. , csere nélkül. Így egyre növekvő szekvenciát kapunk (az élek halmazának beillesztése szempontjából) $1 +$ $n$ $($ $n$ $-1) / 2$ véletlen gráfból, amely diszkrét időfolyamatot képez, a gráfhalmaz értékeivel. . A szekvencia minden eleme egy egységes véletlenszerű gráf, amelyet az előző szakasz definiált. Ennek a konstrukciónak az az előnye, hogy különböző véletlenszerű, különböző M paraméterű grafikonokat látunk egymás mellett , ugyanazon a valószínűsített téren, és így képesek összehasonlítani jellemzőiket, nem átlagként vagy törvényileg, hanem a valószínűsített tér minden ω eleméhez . tekinthető. Ez lehetővé teszi az összekapcsolódással az érvelést. ${\ displaystyle \ {\ mathbb {G} (n, M) \} _ {0 \ leq M \ leq n (n-1) / 2},}$
Azt is társítani minden éle e a J valószínűségi változó $T e$ , az az él súlyát úgy, hogy a család $( T e ) e \in J$ egy családi valószínűségi változók IID, például egy egységes jogi on l ' intervallum [0, 1]. Ezután jelöljük azt a gráfot, amelyet azok az élek alkotnak, amelyek súlya kisebb, mint p . Minden élnél ez valószínűséggel történik ${\ displaystyle \ mathbb {G} (n, p)}$

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

Így egyre nagyobb véletlenszerű gráfcsaládot kapunk, amely folyamatos időfolyamatot képez, az értékekkel a gráfhalmazban. Ez a család növekszik az élek halmazának beillesztése szempontjából: egy e él benne van, mivel a gráfcsalád minden egyes eleme binomiális véletlen gráf, amelyet korábban definiáltunk.

{\ 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. A gráf csúcsait úgy tudjuk elképzelni, mint n szigetet egy tónál, amely kommunikál a gyaloghidak ( e élek) segítségével, amelyek a megfelelő $T e$ mélységekbe merülneka víz felszíne alatt. Ha a tó fokozatosan kiürül a vizéből, látni fogjuk, hogy a hidak fokozatosan kialakulnak, és a kapcsolódó összetevők egyre több szigetet hoznak létre.

Kapcsolatok a két modell között

A Central Limit tétel vagy Hoeffding egyenlőtlensége alapján a binomiális eloszlás nagyon a várakozása köré koncentrálódik. Pontosabban az élek száma $N p$ egy véletlen gráf törvény tehát nagyon közel , különösen, ha ez utóbbi mennyiség nagy előtt n : sőt, ${\ displaystyle \ mathbb {G} (n, p)}$ ${\ displaystyle {\ hat {M}} = \ bal \ lfloor p \ {n \ select 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}}.}

Sőt, annak a feltételes eloszlása, hogy tudjuk, hogy $N$ $p$ $= M$ pontosan ezért van, ha $M$ közel van , vagy ekvivalensen, ha ${\ displaystyle \ \ mathbb {G} (n, p)}$ ${\ displaystyle \ mathbb {G} (n, M).}$ ${\ hat {M}}$

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

általánosan elfogadott (és gyakran kimutatható), hogy a két modell , és nagyon hasonló tulajdonságokkal rendelkeznek. ${\ displaystyle \ mathbb {G} (n, p)}$ ${\ displaystyle \ mathbb {G} (n, M)}$

Továbbhaladva, Jelöljük $T ( k )$ a k -edik értéke a szekvencia egyszer ezt az utolsó szekvencia van elhelyezve emelkedő sorrendben: a szekvencia az úgynevezett szekvenciáját rendstatisztikák szekvencia Amikor p veszi a véletlen értéket $T$ $($ $M$ $)$ , akkor pontosan alátámasztása korábbi megfigyelésekkel, vegye figyelembe, hogy $a T$ $($ $M$ $)$ nagyon közel van , abban az értelemben, hogy ennek következtében a híres eredményeit Donsker és Kolmogorov a valószínűsége, ${\ displaystyle (T_ {e}) _ {e \ J} -ben}$ ${\ displaystyle (T _ {(k)}) _ {1 \ leq e \ leq n (n-1) / 2}}$ ${\ displaystyle (T_ {e}) _ {e \ J-ben.}$ ${\ 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)}

elégedett

{\ 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}),}

Az 1 st és 4 -én feltételek jönnek a farok eloszlásának a Rayleigh és Kolmogorov törvények , rendre: Összefoglalva, a szuprémum (ha M változik) a hibák nagyságrendű 1 / n . ${\ displaystyle | T _ {(M)} - 2M / n (n-1) |}$

Rend és növekedés

A grafikon az élek J halmazának részeként tekinthető meg , tehát a valószínűségi tér itt Ω a J összes része , amely időnként azonosítani tudja a ${0,1} J értéket$ . Ez az azonosítás különösen akkor hasznos, amikor Harris egyenlőtlenségét akarjuk alkalmazni .

Az inklúzió részleges sorrend reláció az Ω-on.
Szokás szerint az Ω-on definiált X térkép , valós értékekkel, növekszik, ha

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

Egy része egy az Ω azt mondják, hogy egyre nagyobb , ha

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

Ezzel egyenértékűen azt mondják, hogy az Ω A része növekszik, ha a mutató funkciója növekszik.

Az alkalmazás vagy alkatrész bomlási tulajdonságának analóg meghatározása van.

Példák:

A grafikon tulajdonságai és paraméterei között

az összekapcsoltság növekszik, azaz az a része egy az Ω alkotja az összes csatlakoztatott grafikonok, egyre nagyobb része Ω: ha hozzá egy él egy összefüggő gráf, a grafikon így kapott még csatlakoztatva;
csökken a síkosság : ha egy síkot elveszítünk egy élről, akkor az így kapott gráf továbbra is sík;
a kromatikus szám növekszik;
a stabilitás száma csökken;
a háromszög nélküli tulajdonság csökken.

A következő egyenlőtlenségek vannak bennünk:

Harris-egyenlőtlenség - A binomiális véletlenszerű gráf keretében

vagyis két véletlen változó, X és Y, amelyek Ω-ra nőnek. Így

{\ displaystyle \ mathbb {E} [XY] \ geq \ mathbb {E} \ bal [X \ jobb] \ mathbb {E} [Y] \,;}

vagyis két növekvő Ω A és B rész . Így

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

Megjegyzések:

Ez azt jelenti, hogy pozitív összefüggés van az érintett változók között, mivel az első egyenlőtlenséget a kovariancia segítségével a következő formában tudjuk megfogalmazni :

{\ displaystyle {\ text {Cov}} \ bal (X, Y \ jobb) \ \ geq \ 0.}

Az egyenlőtlenség a csökkenő változók vagy részek esetében is érvényes, de az egyenlőtlenségek jelentése akkor változik, ha az érintett változóknak vagy részeknek ellentétes jelentése van az egyhangúsággal.

Kapcsolódás

A csatlakozási küszöb

Tétel (Erdős, Rényi, 1960) - Legyen $a n = np ( n ) - ln n$ , vagy ismét:

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

Ha akkor ${\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}$ ${\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ ~ related} \ right) = 1.}$
Ha akkor ${\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ ~ related} \ right) = 0.}$

Azt mondjuk, hogy az $ln ( n ) / n$ egy keskeny küszöbérték a kapcsolati tulajdonságra, a szűkség arra utal, hogy a tulajdonság akkor is elégedett, ha szigorúan kevésbé gyorsan hajlamos a végtelenbe, mint $év$ ${\ displaystyle \ ln n.}$

Demonstráció

Adunk magunknak egy véletlenszerű G n gráfot törvényszerűséggel és egy véletlenszerű gráfot a törvénnyel. A tétel a kettős-exponenciális tételből következik , amely maga következik az elkülönített pontok következő szakaszban végzett felsorolásából . A kapcsolat egyre növekvő tulajdonság , ezért amint n elég nagy ahhoz ${\ displaystyle \ mathbb {G} \ bal (p (n), n \ jobb)}$ ${\ displaystyle {\ tilde {G}} _ {n}}$ ${\ displaystyle \ mathbb {G} \ bal ({\ tilde {p}} (n), n \ jobb).}$

{\ 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),}

nekünk is van

{\ displaystyle \ mathbb {P} \ balra (G_ {n} \ mathrm {~ ~ kapcsolódó} \ jobbra) \ geq \ mathbb {P} \ balra ({\ tilde {G}} _ {n} \ mathrm { ~ a ~ kapcsolatos} \ helyes).}

Sőt, még akkor is, ha ugyanazokat az iid azonos változókat kell létrehozni és használni ugyanazon az Ω valószínűségi téren, amint azt a „A két véletlenszerű folyamat gráfértékekkel” szakaszban jelezzük , Ω összes ω- jára $G_ {n}$ ${\ displaystyle {\ tilde {G}} _ {n}}$ ${\ displaystyle (U_ {e}) _ {e \ J} -ben}$

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

ebből kifolyólag

{\ displaystyle \ left \ {{\ tilde {G}} _ {n} (\ omega) {\ text {is related}} \ right \} \ Rightarrow \ left \ {G_ {n} (\ omega) \ mathrm {~ ~ kapcsolatos} \ helyes \},}

és

{\ displaystyle \ mathbb {P} \ balra ({\ tilde {G}} _ {n} \ mathrm {~ ~ kapcsolódó} \ jobbra) \ leq \ mathbb {P} \ balra (G_ {n} \ mathrm { ~ a ~ kapcsolatos} \ helyes).}

Ha ebből következik, bármely valós c szám esetén ${\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}$

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

vagy akár

{\ displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ ~ related} \ right) \ geq \ sup \ bal \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ right \} \ = \ 1.}

Másrészt, ha ekkor n elég nagyra, akkor minden ω -ra és ${\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ displaystyle G_ {n} (\ omega) \ subset {\ tilde {G}} _ {n} (\ omega),}$

{\ displaystyle \ mathbb {P} \ balra ({\ tilde {G}} _ {n} \ mathrm {~ ~ kapcsolódó} \ jobbra) \ geq \ mathbb {P} \ balra (G_ {n} \ mathrm { ~ a ~ kapcsolatos} \ helyes).}

Így bármely c valós szám esetén

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

Elszigetelt pontok felsorolása

Könnyebb (nagyobb valószínűséggel), hogy sikerül vágás a n - 1 közötti kapcsolatokat egy pont és annak komplementere, mint a k ( n - k ) közötti kapcsolatokat egy csoportja K pontok és annak komplementere, mert a függvény $F ( k ) = A k ( n - k )$ nagyon gyorsan növekszik 1 körül, ezért a k növekedésével sokkal több élt kell kivágni, és sokkal kisebb a valószínűsége, hogy mindegyiket sikeresen levágja. Következésképpen, ha a p paramétert a fentiekben választjuk meg , a G ( n , p ) gráf „szinte csak” nem lesz összekapcsolva, ha vannak elkülönített pontjai abban az értelemben, hogy a kapcsolat valószínűsége nagyon közel van a annak valószínűsége, hogy nincsenek elszigetelt pontok, ami megközelítőleg $egyenlő az$ $e$ $-e$ $-$ $c-vel.$ Valójában a következő eredményt kapjuk: ${\ displaystyle \ mathbb {P} \ bal (X_ {n} = 0 \ jobb),}$

Elszigetelt pontok (Erdős, Rényi, 1960). - Tegyük fel, hogy

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

Ekkor a gráf izolált pontjainak $X n$ száma törvényben konvergál az $e$ $-$ $c$ paraméter Poisson-eloszlásához . ${\ displaystyle G \ bal ({\ tilde {p}} (n), n \ jobb)}$

Demonstráció

A következőkben azt rövidíti a mi póz ${\ displaystyle G \ bal ({\ tilde {p}} (n), n \ jobb)}$ ${\ displaystyle {\ tilde {G}} _ {n},}$

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

Let $X n legyen$ száma izolált pontok Tudjuk, hogy ${\ displaystyle {\ tilde {G}} _ {n}.}$

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

vagy

{\ displaystyle Y_ {i} = 1 _ {\ mathrm {a ~ csúcs ~} i \ mathrm {~ is ~ isol {\ akut {e}}}}.}

Használjuk a faktoriális pillanatok módszerét. Let $I n , A lennie$ a beállított injekciókat a Minden $[\! [1, n] \!]$ $NÁL NÉL.$ ${\ displaystyle r \ geq 1,}$

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

Az előző összeg feltételei valóban megjelennek a bővítésben, de ezen kifejezéseken kívül ez a bővítés sok más, nyilvánvalóan ütköző kifejezést hoz fel. Valóban, akár ${\ displaystyle \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}}$ ${\ displaystyle (Y_ {1} + Y_ {2} + \ pont + Y_ {n}) _ {r},}$

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

Így

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

ebből kifolyólag

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

Sőt, szimmetria alapján,

{\ 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},}

ahol $r ( n -1)$ az E csúcsából potenciálisan eredő élek száma , és ahol $r ( r -1) / 2$ az E két csúcsa közötti élek száma , azaz. azokat, amelyeket duplán számolunk az összes $r-ben ( n -1)$ . Így

{\ displaystyle {\ begin {aligned} \ 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)} \\ & = \ balra (n (1 - {\ tilde {p}} (n)) ^ {n-1} \ jobbra) ^ {r} \\ & \ simeq \ mu ^ {r} . \ end {igazítva}}}

Ezért a pillanatok módszerével $X n$ törvényben konvergál a Poisson-eloszláshoz μ paraméterrel , és

{\ displaystyle \ lim \ mathbb {P} \ bal (X_ {n} = 0 \ jobb) \ = \ \ mathrm {e} ^ {- \ mu} \ = \ \ mathrm {e} ^ {- \ mathrm { e} ^ {- c}}.}

Ez a tétel egy feltűnő illusztráció a Fish paradigma , hogy amikor sok lehetőséget, hogy tartsa egy esemény ritka ( azaz d. Nem valószínű), akkor az összes ritka események valóban megfigyelhető követ Poisson törvény .

A kettős exponenciális tétel

Erdős és Rényi pontosabb eredményre vezetnek, mint a keskeny küszöbérték:

Kettős exponenciális tétel (Erdős, Rényi, 1960) - Tegyük fel, hogy

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

Így

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

Demonstráció Ha nincs elkülönített pont, és akkor kevés az esély arra, hogy ez más, mint összekapcsolt (vö. Spencer, 10 előadás véletlenszerű grafikonokon ). Valójában legyen B része a bírónak , és k legyen a bíborosa. Jelöljük a " B a kapcsolódó komponens " eseményt . Az esemény a

k

k

-2

valószínűségi részhalmaz (nem diszjunkt) egyesülésének tekinthető

{\ 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)},}

ami a következő növekedéshez vezet:

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

Itt jelöljük az összekapcsolt gráf lehetséges átfedő fáinak számát, amelynek csúcsai a B elemei lennének , vagy egyenértékű módon akár egy k -1 élből álló család lehetséges választási lehetőségeinek számát, amely a B halmazt összefüggésbe hozza . Ezenkívül annak a valószínűsége, hogy a figyelembe vett átfogó fa k -1 széle valóban jelen van, és annak a valószínűsége, hogy nincs olyan él, amely összeköti a B csúcsát a B c csúcsával , olyan, hogy B , vagyis nem csak kapcsolódik , de a grafikon összekapcsolt részei között is maximális. ${\ displaystyle k ^ {k-2}}$ ${\ displaystyle {\ tilde {p}} (n) ^ {k-1}}$ ${\ displaystyle (1 - {\ tilde {p}} (n)) ^ {k (nk)}}$

Az esemény

{\ displaystyle D_ {n} = \ {X_ {n} = 0 \ mathrm {~ mais ~} {\ tilde {G}} _ {n} \ mathrm {~ n} ^ {\ prime} \ mathrm {est ~ nem ~ kapcsolódó} \}}

ellenőrzött

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

Sőt, feltételezve, D n , több csatlakoztatott komponensek, ezért a legkisebb közülük (abban az értelemben, a csúcsok száma) van a legtöbb n / 2 csúcsú, de ez a legkisebb csatlakoztatott komponens legalább két csúcsot, mivel $X$ $n$ $= 0$ . Így ${\ displaystyle {\ tilde {G}} _ {n}}$

{\ displaystyle {\ begin {aligned} \ 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 \ válassza 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 {igazítva}}}

Azonban $α > 0$ ,

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

amint

{\ displaystyle \ ln n \ geq \ max \ balra [c + \ varepsilon (n) \ ,, (- 2c-2 \ varepsilon (n) +4 {\ tilde {p}} (n)) / \ alfa \ jobbra.]

Ahogy a 2-nél nagyobb méretű csatlakoztatott komponens sokkal kevésbé valószínű, mint az 1-es méretű csatlakoztatott komponens, a 3-nál nagyobb méretű csatlakoztatott komponens sokkal kevésbé valószínű, mint egy 2-es méretű csatlakoztatott komponens, ami

Tulajdonság - Amikor n végtelenbe hajlik

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

Néhány kissé fájdalmas számítás - anélkül, hogy őszintén szólva nehéz lenne - vezet ehhez az eredményhez.

Demonstráció

Az $u 2 ( n )$ esetében fent megadott határ nemcsak felső határ , hanem valójában az $u 2 ( n )$ nagyságrendjét adja meg . Ami az összeg fennmaradó részét illeti, ketté kell vágnunk, mielőtt mind a két darabot növelnénk:

{\ displaystyle {\ begin {aligned} {\ frac {u_ {k + 1}} {u_ {k}}} & = (nk) \, (1 + {\ tfrac {1} {k}}) ^ { k-2} \, {\ tilde {p}} (n) \ szer (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \\ & = (nk) \, ( e + {\ hat {\ varepsilon}} (k)) \, {\ tilde {p}} (n) \ szer (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ \ & \ leq {\ hat {c}} \, \ ln n \ (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ end {igazítva}}}

vagy

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

Azért és ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}$ ${\ displaystyle k \ leq \ beta n,}$

{\ displaystyle {\ begin {aligned} {\ 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 {igazított}}}

amint

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

Ezért n elég nagy esetén gyorsabban csökken, mint egy exponenciális oksor, amikor és amikor ${\ 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.}

Sőt, találunk c és ρ pozitív, oly módon, hogy az összes ${\ displaystyle 0 <\ alfa <1/4,}$ ${\ displaystyle n \ geq 1,}$

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

Azért és ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}$ ${\ displaystyle k \ geq \ beta n,}$

{\ displaystyle {\ begin {aligned} {\ 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 {igazítva}}}

amint n elég nagy. Ezért elég és közel 0,5-re, elég közel 1-re, ${\ displaystyle n / 2 \ geq k \ geq \ beta n,}$ $\ béta$ ${\ displaystyle (1-2 \ beta) / \ gamma}$

{\ displaystyle {\ begin {aligned} - \ 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 { igazítva}}}

és

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

Ebből kifolyólag

{\ displaystyle \ lim _ {n} \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ is ~ related} \ right) = \ lim _ {n} \ mathbb {P } \ bal (X_ {n} = 0 \ jobb).}

Jelöljük $T n-vel$ az első t pillanatot, ahol a gráf kapcsolódik: ${\ displaystyle \ mathbb {G} \ bal (t, n \ jobb)}$

{\ displaystyle T_ {n} \ = \ \ inf \ bal \ {t \ geq 0 \ | \ \ mathbb {G} (t, n) \ mathrm {~ ~ kapcsolódó} \ jobb \},}

úgy hogy

{\ displaystyle \ left \ {\ mathbb {G} \ left (t, n \ right) \ mathrm {~ is ~ related} \ 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 {~ ~ related} \ right \}.}

Ezután láthatjuk a kettős exponenciális tételt a $T n$ aszimptotikus tágulásának eredményeként : ha $Z n$ a következő összefüggés határozza meg:

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

akkor a kettős-exponenciális tétel kimondja, hogy $Z n$ a jogban konvergál a Gumbel terjesztése felé , amelyet Landau jelölésének valószínűségi változatában lefordíthat :

{\ displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ \ Theta \ balra ({\ frac {1} {n}} \ jobbra).}

A végtelen véletlenszerű grafikon

Erdős és Rényi a binomiális modellt egy megszámlálhatatlan végtelen gráf esetére általánosították , megmutatva, hogy ezután ( szinte biztosan ) nyertünk egy univerzalitási tulajdonságokkal rendelkező grafikont (amely részlegesen minden véges vagy megszámlálható gráfot tartalmaz ); ezt a gráfot többször újra felfedezték, és leggyakrabban Rado gráf néven ismerik .

Lásd is

Megjegyzések

Az első, 1959-ben megjelent cikk a "Véletlenszerű grafikonokról I", Publ. Math. Debrecen 6, 290.
(in) Erdős P. , " Néhány megjegyzés a grafikonok elméletéhez " , Bull. Keserű. Math. Soc. , vol. 53, n o 4,1947, P. 292-294 ( online olvasás ). Ezt a cikket gyakran úgy tekintik, hogy jelöli a „véletlenszerű módszer” születését a nem véletlenszerű grafikonok, különösen a Ramsey-elmélet tanulmányozásához .
A háttér, lásd (in) Mr. Karoński Rucinski és A., "eredete az elmélet véletlen gráfok" , in The Mathematics of Erdős Pál , Berlin, Springer al. - Algoritmusok Combin. „( N o 13),1997, P. 311-336.
További részletek: Janson, Łuczak és Ruciński 2000 , fejezet. 2, "Exponenciálisan kis valószínűségek".
Lásd Janson, Łuczak és Ruciński 2000 , 1.4. Szakasz, „Aszimptotikus egyenértékűség”, 1. o. 14.
View (in) Galen R. Shorack és Jon A. Wellner , Empirikus folyamatok a statisztikai alkalmazásokkal , SIAM ,2009. szeptember, 998 p. ( ISBN 978-0-89871-684-9 , online olvasás ), 3.8. szakasz, „Az eloszlások korlátozása a nullhipotézis alatt”, p. 142. o. 18., „A standardizált kvantilis folyamat”, p. 637.
Janson, Łuczak és Rucinski 2000 , Th. 6,7, p. 144.
Lásd a cikk " bijekciót de Joyal ", vagy Martin Aigner és Günter M. Ziegler, Isteni okoskodásaikban , 2 nd edition, 2006, p. 195-201, Cayley képlete a fák számára .

Bibliográfia

(en) Bollobás Béla , Random Graphs , Cambridge University Press,2001. január, 2 nd ed. ( 1 st ed. 1985), 516 p. ( ISBN 978-0-521-79722-1 , online olvasás ).
en) Svante Janson (en) , Tomasz Łuczak és Andrzej Ruciński, Random Graphs , Wiley-Interscience,2000. május, 1 st ed. , 333 p. , keménytáblás ( ISBN 978-0-471-17541-4 ).
(en) Joel Spencer (en) , „Kilenc előadás véletlenszerű grafikonokról” , a Saint-Liszt valószínűségének nyári iskolájában XXI-1991, 3. rész , Springer, coll. "Előadási jegyzetek a matematikából. „( N o 1541)1993, P. 293-347.

Kapcsolódó cikk

Valószínűségek bevezetése a gráfelméletben

Külső hivatkozás

Laurent Massoulié, Hálózatok: elosztott irányítás és feltörekvő jelenségek , 2015