Tilfældig graf
I matematik er en tilfældig graf en graf , der genereres ved en tilfældig proces . Den første model af tilfældige grafer blev populariseret af Paul Erdős og Alfréd Rényi i en række artikler offentliggjort mellem 1959 og 1968.
De to grundlæggende modeller af Erdős og Rényi
Erdős og Rényis model samler faktisk to modeller, formelt forskellige, men nært beslægtede. I begge modeller
- sættet med hjørner er {1, 2, 3, ..., n } angivet med følgende ; [[ikke]]{\ displaystyle \ [\! [n] \!]}
- de potentielt tilstedeværende kanter er n ( n –1) / 2 to-element dele af ; sæt af disse kanter bemærkes undertiden, men det vil blive bemærket J for typografisk bekvemmelighed og for overensstemmelse med artiklen om Harris ulighed . [[ikke]]{\ displaystyle \ [\! [n] \!]}([[ikke]]2).{\ displaystyle {[\! [n] \!] \ vælg 2}.}
- den tilfældige graf er således ikke-rettet og har ingen sløjfer eller flere kanter .
Binomial tilfældig graf
I denne model er hver af n ( n –1) / 2 kanter ofte til stede med sandsynlighed p , fraværende med sandsynlighed 1- p , uanset status for de andre kanter. Tilfældet p = 0,5 blev studeret ved Erdős så tidligt som 1947. Antallet N p kanter følger binomial fordeling af parametre n ( n -1) / 2 og p .
G(ikke,s),{\ displaystyle \ mathbb {G} (n, p),}G(ikke,s){\ displaystyle \ mathbb {G} (n, p)}
Den ensartede tilfældige graf
I denne model, der ofte bemærkes, vælger vi ensartet en delmængde af M- kanter blandt n ( n -1) / 2 mulige kanter. Når en graf G med n hjørner har M- kanter, er sandsynligheden for G givet ved
G(ikke,M),{\ displaystyle \ mathbb {G} (n, M),}
P(G) = 1((ikke2)M).{\ displaystyle \ mathbb {P} (G) \ = \ {\ frac {1} {{n \ vælg 2} \ vælg M}}.}
Dette er den model , der hovedsageligt studeres i rækken af sædvanlige artikler, der blev offentliggjort af Erdős og Rényi mellem 1959 og 1968.
G(ikke,M){\ displaystyle \ mathbb {G} (n, M)}
De to tilfældige processer med grafværdier
- Vi kan starte fra en graf uden kanter, derfor helt afbrudt og tilføje en kant, der er trukket tilfældigt ensartet, derefter en anden osv. uden udskiftning. Vi opnår således en stigende sekvens (i betydningen inddragelse af kantsættet) på 1 + n ( n –1) / 2 tilfældige grafer, der danner en diskret tidsproces med værdier i sæt af grafer . Hvert udtryk i sekvensen er en ensartet tilfældig graf defineret i det foregående afsnit. En fordel ved denne konstruktion er at se forskellige tilfældige grafer med forskellige parametre M sameksistere på det samme probabiliserede rum og således være i stand til at sammenligne deres karakteristika, ikke som et gennemsnit eller i lov, men for hvert element prob af det probabiliserede rum overvejes. Dette gør det muligt at ræsonnere ved kobling.{G(ikke,M)}0≤M≤ikke(ikke-1)/2,{\ displaystyle \ {\ mathbb {G} (n, M) \} _ {0 \ leq M \ leq n (n-1) / 2},}
- Vi kan også associere med hver kant e af J en stokastisk variabel T e , vægten af kanten, så familien ( T e ) e ∈ J er en familie af stokastiske variable IID, for eksempel med en ensartet lovgivning på l ' interval [0, 1]. Vi betegner derefter grafen dannet af de kanter, hvis vægt er mindre end p . For hver kant sker dette med sandsynlighedG(ikke,s){\ displaystyle \ mathbb {G} (n, p)}
P(Te≤s) = s.{\ displaystyle \ mathbb {P} (T_ {e} \ leq p) \ = \ p.}
Vi opnår således en voksende familie af tilfældige grafer, der danner en kontinuerlig tidsproces med værdier i sættet med grafer. Denne familie vokser i betydningen af inkluderingen af kantsættet: en kant e til stede i er også til stede i, da Hver betegnelse i familien af grafer er en
tilfældig tilfældig graf, der er defineret tidligere.
{G(ikke,s)}0≤s≤1,{\ displaystyle \ {\ mathbb {G} (n, p) \} _ {0 \ leq p \ leq 1},}G(ikke,s){\ displaystyle \ mathbb {G} (n, p)}G(ikke,s+ε), ε>0,{\ displaystyle \ mathbb {G} (n, p + \ varepsilon), \ \ varepsilon> 0,}{Te≤s} ⇒ {Te≤s+ε}.{\ displaystyle \ {T_ {e} \ leq p \} \ \ Rightarrow \ \ {T_ {e} \ leq p + \ varepsilon \}.}Metafor. Vi kan forestille os hjørnerne på grafen som n øer ved en sø, der kommunikerer ved hjælp af gangbroer (kamme e ), nedsænket på respektive dybder T e under vandoverfladen. Hvis søen gradvist tømmer sit vand, vil vi se broerne gradvist dukke op, og relaterede komponenter, der grupperer flere og flere øer, dannes.
Forbindelser mellem de to modeller
I kraft af Central Limit Theorem eller Hoeffdings ulighed er binomialoven meget koncentreret omkring dens forventning. Mere præcist antallet af kanter N p af en tilfældig lov graf er derfor meget tæt på , især hvis denne sidste mængde er stor foran n : ja,
G(ikke,s){\ displaystyle \ mathbb {G} (n, p)}M^=⌊s (ikke2)⌋{\ displaystyle {\ hat {M}} = \ venstre \ lfloor p \ {n \ vælg 2} \ højre \ rfloor}M^{\ displaystyle {\ hat {M}}}
∀t>0,P(|IKKEs-M^|≥tikke) ≤ 2e-2t2.{\ displaystyle \ forall t> 0, \ qquad \ mathbb {P} \ left (\ left | N_ {p} - {\ hat {M}} \ right | \ geq tn \ right) \ \ leq \ 2 \, \ mathrm {e} ^ {- 2t ^ {2}}.}
Desuden betingede fordeling af at vide, at N p = M er netop af denne grund, hvis M er tæt på , eller, ækvivalent, hvis
G(ikke,s){\ displaystyle \ \ mathbb {G} (n, p)}G(ikke,M).{\ displaystyle \ mathbb {G} (n, M).}M^{\ displaystyle {\ hat {M}}}
s≃2Mikke(ikke-1),{\ displaystyle p \ simeq {\ frac {2M} {n (n-1)}},}
Det er generelt accepteret (og ofte demonstreret), at de to modeller og har meget lignende egenskaber.
G(ikke,s){\ displaystyle \ mathbb {G} (n, p)}G(ikke,M){\ displaystyle \ mathbb {G} (n, M)}
Går længere, lad T ( k ) betegne den k 'te værdi af sekvensen , når denne sidste sekvens er anbragt i stigende rækkefølge: sekvensen kaldes sekvensen af ordens statistik af sekvensen Når p tager tilfældig værdi T ( M ) , så er det nøjagtigt
For at bekræfte de tidligere observationer skal du bemærke, at T ( M ) er meget tæt på i den forstand , at sandsynligheden for , at en konsekvens af berømte resultater fra Donsker og Kolmogorov er
(Te)e∈J{\ displaystyle (T_ {e}) _ {e \ i J}}(T(k))1≤e≤ikke(ikke-1)/2{\ displaystyle (T _ {(k)}) _ {1 \ leq e \ leq n (n-1) / 2}}(Te)e∈J.{\ displaystyle (T_ {e}) _ {e \ i J}.}G(ikke,T(M)){\ displaystyle \ mathbb {G} (n, T _ {(M)})}G(ikke,M).{\ displaystyle \ mathbb {G} (n, M).}2M/ikke(ikke-1),{\ displaystyle 2M / n (n-1),}
φikke(x)=P(sup1≤M≤ikke(ikke-1)/2{|T(M)-2Mikke(ikke-1)|}≥x2ikke){\ displaystyle \ varphi _ {n} (x) = \ mathbb {P} \ left (\ sup _ {1 \ leq M \ leq n (n-1) / 2} \ left \ {| T _ {(M )} - {\ tfrac {2M} {n (n-1)}} | \ højre \} \ geq {\ tfrac {x {\ sqrt {2}}} {n}} \ højre)}
tilfreds
eksp(-2x2) ≤ lim infikkeφikke(x) ≤ lim supikkeφikke(x) ≤ 2∑r=1+∞(-1)r-1eksp(-2r2x2),{\ 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}),}
den 1 st og 4 th vilkår bliver halerne af fordelingen af Rayleigh og Kolmogorov love henholdsvis: i Sammenfattende supremum (når M varierer) af fejlene er af størrelsesordenen 1 / n .
|T(M)-2M/ikke(ikke-1)|{\ displaystyle | T _ {(M)} - 2M / n (n-1) |}
Orden og vækst
En graf kan ses som en del af sættet J kanter, så sandsynligheden plads er her w alle dele af J , som undertiden kan identificere {0,1} J . Denne identifikation er især nyttig, når vi vil anvende Harris ' ulighed .
- Inklusion er en partiel orden forhold på Ω.
- Som sædvanlig siges et kort X defineret på Ω med reelle værdier at stige, hvis
{ω≤ω′}⇒{x(ω)≤x(ω′)}.{\ displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \} \ quad \ Rightarrow \ quad \ {X (\ omega) \ leq X (\ omega ^ {\ prime}) \}.}
- En del A af Ω siges at stige, hvis
{ω≤ω′ og ω∈PÅ}⇒{ω′∈PÅ}.{\ displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \ {\ text {et}} \ \ omega \ i A \} \ quad \ Rightarrow \ quad \ {\ omega ^ {\ prime} \ i A \}.}
Tilsvarende siges en del A af Ω at stige, hvis dens
indikatorfunktion stiger.
- Henfaldsegenskaben for en applikation eller del har en analog definition.
Eksempler:
Blandt egenskaberne og parametrene for en graf,
- den forbundethed er stigende, dvs. del A af Ω, der består af alle de tilsluttede grafer, er en stigende del af Ω: hvis vi tilføjer en kant til en tilsluttet graf, er den således opnåede graf stadig forbundet;
- den planhed er faldende: hvis vi fjerner en kant fra en plan graf, den således opnåede kurve er stadig plant;
- det kromatiske antal stiger;
- det antal stabilitet er faldende;
- den trekantfrie egenskab er faldende.
Vi har følgende ulighed:
Harris ulighed - inden for rammerne af den binomiale tilfældige graf ,
- det vil sige to tilfældige variabler X og Y stigende på Ω. Så
E[xY]≥E[x]E[Y];{\ displaystyle \ mathbb {E} [XY] \ geq \ mathbb {E} \ left [X \ right] \ mathbb {E} [Y] \,;}
- det vil sige to stigende dele A og B af Ω. Så
P(PÅ∩B)≥P(PÅ)P(B).{\ displaystyle \ mathbb {P} (A \ cap B) \ geq \ mathbb {P} (A) \ mathbb {P} (B).}
Bemærkninger:
- Dette svarer til at sige, at der er en positiv sammenhæng mellem de pågældende variabler, da vi kan omformulere den første ulighed i følgende form ved hjælp af kovariansen :
Cov(x,Y) ≥ 0.{\ displaystyle {\ text {Cov}} \ venstre (X, Y \ højre) \ \ geq \ 0.}
- Ulighed gælder også for faldende variabler eller dele, men betydningen af uligheder ændres, når de involverede variabler eller dele har modsatte betydninger af monotoni.
Forbindelse
Forbindelsestærsklen
Sætning (Erdős, Rényi, 1960) - Lad a n = np ( n ) - ln n , eller igen:
s(ikke) = lnikkeikke+påikkeikke.{\ displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}}.}
- Hvis sålimikkepåikke=+∞,{\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}limikkeP(G(s(ikke),ikke) est vs.oikkeikkeexe)=1.{\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ er ~ relateret} \ right) = 1.}
- Hvis sålimikkepåikke=-∞,{\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}limikkeP(G(s(ikke),ikke) est vs.oikkeikkeexe)=0.{\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ er ~ relateret} \ right) = 0.}
Vi siger, at ln ( n ) / n er en smal tærskel for tilslutningsegenskaben, hvor snæverheden henviser til det faktum, at ejendommen er tilfreds, selvom den har tendens til uendelig strengt mindre endpåikke{\ displaystyle a_ {n}}lnikke.{\ displaystyle \ ln n.}
Demonstration
Vi giver os selv en tilfældig graf G n med lovgivningen og en tilfældig graf med loven. Sætningen følger dobbelt-eksponentielle teorem , som selv følger af tælling af isolerede punkter udført i det følgende afsnit. Forbindelse er en voksende egenskab , så snart n er stor nok til det
G(s(ikke),ikke){\ displaystyle \ mathbb {G} \ left (p (n), n \ right)}G~ikke{\ displaystyle {\ tilde {G}} _ {n}}G(s~(ikke),ikke).{\ displaystyle \ mathbb {G} \ left ({\ tilde {p}} (n), n \ right).}
s(ikke) = lnikkeikke+påikkeikke≥lnikkeikke+vs.ikke+ε(ikke)ikke = s~(ikke),{\ 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),}
vi har også
P(Gikke est vs.oikkeikkeexe)≥P(G~ikke est vs.oikkeikkeexe).{\ displaystyle \ mathbb {P} \ left (G_ {n} \ mathrm {~ er ~ relateret} \ right) \ geq \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm { ~ er ~ relateret} \ højre).}
Faktisk har vi selv for at konstruere og bruge de samme ensartede iid-variabler på det samme sandsynlighedsrum Ω som beskrevet i afsnit "De to værdier til tilfældige processer" , for alle ω af Ω,
Gikke{\ displaystyle G_ {n}}G~ikke{\ displaystyle {\ tilde {G}} _ {n}}(Ue)e∈J{\ displaystyle (U_ {e}) _ {e \ i J}}
Gikke(ω)⊃G~ikke(ω),{\ displaystyle G_ {n} (\ omega) \ supset {\ tilde {G}} _ {n} (\ omega),}
derfor
{G~ikke(ω) er relateret}⇒{Gikke(ω) est vs.oikkeikkeexe},{\ displaystyle \ left \ {{\ tilde {G}} _ {n} (\ omega) {\ text {er relateret}} \ højre \} \ Rightarrow \ venstre \ {G_ {n} (\ omega) \ mathrm {~ er ~ relateret} \ right \},}
og
P(G~ikke est vs.oikkeikkeexe)≤P(Gikke est vs.oikkeikkeexe).{\ displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ er ~ relateret} \ right) \ leq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ er ~ relateret} \ højre).}
Hvis det følger heraf, for ethvert reelt tal c ,
limikkepåikke=+∞,{\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}
lim infikkeP(G(s(ikke),ikke) est vs.oikkeikkeexe)≥e-e-vs.,{\ displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ er ~ relateret} \ right) \ geq \ mathrm { e} ^ {- \ mathrm {e} ^ {- c}},}
eller endda
lim infikkeP(G(s(ikke),ikke) est vs.oikkeikkeexe)≥sup{e-e-vs.|vs.∈R} = 1.{\ displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ er ~ relateret} \ right) \ geq \ sup \ venstre \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ i \ mathbb {R} \ højre \} \ = \ 1.}
På den anden side, hvis så for n tilstrækkeligt stort, vil vi have for alle ω , og
limikkepåikke=-∞,{\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}Gikke(ω)⊂G~ikke(ω),{\ displaystyle G_ {n} (\ omega) \ subset {\ tilde {G}} _ {n} (\ omega),}
P(G~ikke est vs.oikkeikkeexe)≥P(Gikke est vs.oikkeikkeexe).{\ displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ er ~ relateret} \ right) \ geq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ er ~ relateret} \ højre).}
Således for ethvert reelt tal c ,
lim supikkeP(G(s(ikke),ikke) est vs.oikkeikkeexe)≤inf{e-e-vs.|vs.∈R} = 0.{\ displaystyle \ limsup _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ er ~ relateret} \ right) \ leq \ inf \ venstre \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ i \ mathbb {R} \ højre \} \ = \ 0.}
Tælling af isolerede punkter
Det er lettere (mere sandsynligt) at lykkes med at skære n - 1 forbindelserne mellem et punkt og dets komplement end k ( n - k ) forbindelserne mellem en gruppe af k punkter og dets komplement, fordi funktionen f ( k ) = k ( n - k ) stiger meget hurtigt omkring 1, derfor, når k stiger, mange flere kanter at skære og en meget lavere sandsynlighed for at klippe dem alle med succes. Som et resultat, med valget af parameteren p, der er lavet ovenfor, vil grafen G ( n , p ) ikke være "næsten kun" forbundet, hvis den har isolerede punkter, i den forstand at sandsynligheden for at blive forbundet er meget tæt på sandsynligheden for ikke at have isolerede punkter, hvilket er omtrent lig med e –e - c Faktisk har vi følgende resultat:
P(xikke=0),{\ displaystyle \ mathbb {P} \ left (X_ {n} = 0 \ right),}
Isolerede punkter (Erdős, Rényi, 1960). -
Antag det
s~(ikke) = lnikkeikke+vs.ikke+ε(ikke)ikke.{\ displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {ikke}}.}
Derefter konvergerer antallet X n af isolerede punkter i grafen i lov mod en Poisson-fordeling af parameter e - c .
G(s~(ikke),ikke){\ displaystyle G \ left ({\ tilde {p}} (n), n \ right)}
Demonstration
I det følgende forkortes vi , og vi udgør
G(s~(ikke),ikke){\ displaystyle G \ left ({\ tilde {p}} (n), n \ right)}G~ikke,{\ displaystyle {\ tilde {G}} _ {n},}
μ=e-vs..{\ displaystyle \ mu = \ mathrm {e} ^ {- c}.}
Lad X n være antallet af isolerede punkter i Vi ved det
G~ikke.{\ displaystyle {\ tilde {G}} _ {n}.}
xikke=Y1+Y2+⋯+Yikke,{\ displaystyle X_ {n} = Y_ {1} + Y_ {2} + \ prikker + Y_ {n},}
eller
Yjeg=1le sommet jeg est jegsole´.{\ displaystyle Y_ {i} = 1 _ {\ mathrm {the ~ vertex ~} i \ mathrm {~ is ~ isol {\ acute {e}}}}.}
Lad os bruge metoden til faktuelle øjeblikke. Lad jeg n , A være sættet med injektioner af i For alle[[1,ikke]]{\ displaystyle [\! [1, n] \!]}PÅ.{\ displaystyle A.}r≥1,{\ displaystyle r \ geq 1,}
(xikke)r=(Y1+Y2+⋯+Yikke)r=∑φ∈jegr,[[1,ikke]] ∏jeg=1rYφ(jeg).{\ displaystyle (X_ {n}) _ {r} = (Y_ {1} + Y_ {2} + \ prikker + Y_ {n}) _ {r} = \ sum _ {\ varphi \ i I_ {r, [\! [1, n] \!]}} \ \ Prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}.}
Betingelserne for det foregående beløb forekommer faktisk i udvidelsen af, men bortset fra disse vilkår bringer denne udvidelse mange andre udtryk, der tilsyneladende kolliderer. Faktisk enten
∏jeg=1rYφ(jeg){\ displaystyle \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}}(Y1+Y2+⋯+Yikke)r,{\ displaystyle (Y_ {1} + Y_ {2} + \ prikker + Y_ {n}) _ {r},}
E={på∈[[1,ikke]]|Ypå=1}.{\ displaystyle E = \ left \ {a \ i [\! [1, n] \!] \, | \, Y_ {a} = 1 \ right \}.}
Så
∀φ∈jegr,[[1,ikke]],∏jeg=1rYφ(jeg)=1φ∈jegr,E,{\ displaystyle \ forall \, \ varphi \ i I_ {r, [\! [1, n] \!]}, \ qquad \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i) } = 1 _ {\ varphi \ i I_ {r, E}},}
derfor
∑φ∈jegr,[[1,ikke]] ∏jeg=1rYφ(jeg) = |jegr,E| = (|E|)r = (xikke)r.{\ displaystyle \ sum _ {\ varphi \ i I_ {r, [\! [1, n] \!]}} \ \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ = \ | I_ {r, E} | \ = \ (| E |) _ {r} \ = \ (X_ {n}) _ {r}.}
Desuden ved symmetri,
E[∏jeg=1rYφ(jeg)] = E[∏jeg=1rYjeg]=(1-s~(ikke))r(ikke-1)-r(r-1)/2,{\ 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},}
hvor r ( n -1) er antallet af kanter, der potentielt kan være resultatet af et toppunkt på E , og hvor r ( r -1) / 2 er antallet af kanter mellem to hjørner af E , dvs. dem, der tælles dobbelt i det samlede r ( n -1) . Så
E[(xikke)r]=(ikke)r(1-s~(ikke))r(ikke-1)-r(r-1)/2≃ikker(1-s~(ikke))r(ikke-1)=(ikke(1-s~(ikke))ikke-1)r≃μr.{\ 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 {justeret}}}
Så ved metoden for øjeblikke konvergerer X n i lov til en Poisson-fordeling med parameter μ , og
limP(xikke=0) = e-μ = e-e-vs..{\ displaystyle \ lim \ mathbb {P} \ left (X_ {n} = 0 \ right) \ = \ \ mathrm {e} ^ {- \ mu} \ = \ \ mathrm {e} ^ {- \ mathrm { e} ^ {- c}}.}
Denne sætning er en slående illustration af fiskeparadigmet , at når det giver mange muligheder for at observere en sjælden begivenhed ( dvs. d. Usandsynligt), så følger det samlede antal sjældne begivenheder faktisk en Poisson-lov .
Den dobbelteksponentielle sætning
Erdős og Rényi udleder et mere præcist resultat end den smalle tærskelegenskab:
Dobbelteksponentiel sætning (Erdős, Rényi, 1960) -
Antag det
s~(ikke) = lnikkeikke+vs.ikke+ε(ikke)ikke.{\ displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {ikke}}.}
Så
limikkeP(G(s~(ikke),ikke) est vs.oikkeikkeexe)=e-e-vs..{\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left ({\ tilde {p}} (n), n \ right) \ mathrm {~ er ~ relateret} \ right ) = e ^ {- e ^ {- c}}.}
Demonstration
Hvis er uden isoleret punkt, og så er der ringe chance for, at det er andet end forbundet (jf. Spencer, 10 forelæsninger om tilfældige grafer ). Lad B faktisk være en del af og lad k være dets kardinal. Lad os betegne begivenheden " B er en sammenhængende komponent i ". Begivenheden kan ses som den (ikke-sammenhængende) forening af
k k -2 undergrupper af sandsynligheder
xikke=0,{\ displaystyle X_ {n} = 0,} G~ikke{\ displaystyle {\ tilde {G}} _ {n}}G~ikke{\ displaystyle {\ tilde {G}} _ {n}}[[1,ikke]]{\ displaystyle [\! [1, n] \!]}VSB{\ displaystyle {\ mathcal {C}} _ {B}} G~ikke{\ displaystyle {\ tilde {G}} _ {n}}VSB{\ displaystyle {\ mathcal {C}} _ {B}}s~(ikke)k-1(1-s~(ikke))k(ikke-k),{\ displaystyle {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)},}
hvilket fører til følgende stigning:
P(VSB) ≤ kk-2s~(ikke)k-1(1-s~(ikke))k(ikke-k).{\ displaystyle \ mathbb {P} ({\ mathcal {C}} _ {B}) \ \ leq \ k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)}.}
Her angiver antallet af mulige spændende træer for en tilsluttet graf, hvis hjørner ville være elementerne i B , eller endda på en ækvivalent måde antallet af mulige valg af en familie af k- 1 kanter, der gør sættet B relateret. Endvidere er sandsynligheden for at k -1 kanter af spanning tree betragtede faktisk er til stede, og er sandsynligheden for at nogen kant forbinde et toppunkt B til en toppunkt B c er til stede, således at B dvs. ikke kun er forbundet , men også maksimal blandt de tilsluttede dele af grafen.
kk-2{\ displaystyle k ^ {k-2}}s~(ikke)k-1{\ displaystyle {\ tilde {p}} (n) ^ {k-1}}(1-s~(ikke))k(ikke-k){\ displaystyle (1 - {\ tilde {p}} (n)) ^ {k (nk)}}
Begivenheden
Dikke={xikke=0 mpåjegs G~ikke ikke′est spås vs.oikkeikkeexe}{\ displaystyle D_ {n} = \ {X_ {n} = 0 \ mathrm {~ mais ~} {\ tilde {G}} _ {n} \ mathrm {~ n} ^ {\ prime} \ mathrm {est ~ ikke ~ relateret} \}}
afkrydset
Dikke⊂⋃2≤|B|≤ikke/2VSB.{\ displaystyle D_ {n} \ subset \ bigcup _ {2 \ leq | B | \ leq n / 2} {\ mathcal {C}} _ {B}.}
I henhold til den hypotese D n , har flere sammenhængskomponenter derfor den mindste af dem (i betydningen antallet af knuder) har højst n / 2 vertices, men dette mindste tilsluttede komponent har mindst to toppunkter, idet X n = 0 . Så
G~ikke{\ displaystyle {\ tilde {G}} _ {n}}
P(Dikke)≤∑2≤|B|≤ikke/2P(VSB)≤∑2≤k≤ikke/2(ikkek)kk-2s~(ikke)k-1(1-s~(ikke))k(ikke-k)≤∑2≤k≤ikke/2uk.{\ 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 \ vælg 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 {justeret}}}
For α > 0 er
u2≤ikke-1+alnikke{\ displaystyle {\ begin {align} u_ {2} & \ leq n ^ {- 1+ \ alpha} \, \ ln n \ end {align}}}
så snart
lnikke≥maks[vs.+ε(ikke),(-2vs.-2ε(ikke)+4s~(ikke))/a].{\ displaystyle \ ln n \ geq \ max \ left [c + \ varepsilon (n) \ ,, (- 2c-2 \ varepsilon (n) +4 {\ tilde {p}} (n)) / \ alpha \ højre].}
Ligesom en tilsluttet komponent med størrelse større end 2 er meget mindre sandsynlig end en tilsluttet komponent i størrelse 1, er en tilsluttet komponent med størrelse større end 3 meget mindre sandsynlig end en tilsluttet komponent i størrelse 2, hvilket resulterer i gennemgående
Ejendom -
Når n har tendens til uendelig
u2(ikke) ≫ ∑3≤k≤ikke/2uk(ikke).{\ displaystyle u_ {2} (n) \ \ gg \ \ sum _ {3 \ leq k \ leq n / 2} u_ {k} (n).}
Nogle lidt smertefulde beregninger uden at være ærligt vanskelige fører til dette resultat.
Demonstration
Ovenstående grænse for u 2 ( n ) er ikke kun en øvre grænse , men giver faktisk størrelsesorden u 2 ( n ) . Hvad angår resten af summen, skal vi skære den i to, før hver af de to stykker øges:
uk+1uk=(ikke-k)(1+1k)k-2s~(ikke)×(1-s~(ikke))ikke-2k-1=(ikke-k)(e+ε^(k))s~(ikke)×(1-s~(ikke))ikke-2k-1≤vs.^lnikke (1-s~(ikke))ikke-2k-1{\ 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 {justeret}}}
eller
∀ikke,k,vs.^≥(e+ε^(k))ikkes~(ikke)lnikke.{\ displaystyle \ forall n, k, \ quad {\ hat {c}} \ geq (e + {\ hat {\ varepsilon}} (k)) \, {\ frac {n {\ tilde {p}} ( n)} {\ ln n}}.}
For og0<β<(1-γ)/2<0,5,{\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}k≤βikke,{\ displaystyle k \ leq \ beta n,}
uk+1uk≤vs.^lnikke eksp[-s~(ikke)(ikke-2k-1)]≤vs.^ikke-γlnikke,{\ displaystyle {\ begin {align} {\ frac {u_ {k + 1}} {u_ {k}}} & \ leq {\ hat {c}} \, \ ln n \ \ exp \ left [- { \ tilde {p}} (n) (n-2k-1) \ højre] \\ & \ leq {\ hat {c}} n ^ {- \ gamma} \ ln n, \ slut {justeret}}}
så snart
lnikke≥s~(ikke)+(vs.+ε(ikke))(2β-1)1-2β-γ.{\ displaystyle \ ln n \ geq {\ frac {{\ tilde {p}} (n) + (c + \ varepsilon (n)) (2 \ beta -1)} {1-2 \ beta - \ gamma} }.}
Derfor falder for n stort nok hurtigere end en eksponentiel rækkefølge af grund når og
uk{\ displaystyle u_ {k}}vs.^ikke-γlnikke,{\ displaystyle {\ hat {c}} n ^ {- \ gamma} \ ln n,}2≤k≤1+βikke,{\ displaystyle 2 \ leq k \ leq 1+ \ beta n,}
∑k=21+βikkeuk ≤ u21-vs.^ikke-γlnikke ≤ 2ikke-1+alnikke.{\ 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.}
Desuden for vi kan finde c og ρ positive, således at det for alle0<a<1/4,{\ displaystyle 0 <\ alpha <1/4,}ikke≥1,{\ displaystyle n \ geq 1,}
uikke/2≤vs.ρikkeikke-aikke.{\ displaystyle {\ begin {align} u_ {n / 2} & \ leq c \, \ rho ^ {n} \, n ^ {- \ alpha n}. \ end {align}}}
For og0<β<(1-γ)/2<0,5,{\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}k≥βikke,{\ displaystyle k \ geq \ beta n,}
uk-1uk≤dlnikke eksp[s~(ikke)(ikke-2k+1)]≤dikke(1-2β)2/γlnikke≤dikke(1-2β)2/γ,{\ displaystyle {\ begin {align} {\ frac {u_ {k-1}} {u_ {k}}} & \ leq {\ frac {d} {\ ln n}} \ \ exp \ left [{\ tilde {p}} (n) (n-2k + 1) \ højre] \\ & \ leq {\ frac {d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}} { \ ln n}} \\ & \ leq d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}, \ end {justeret}}}
så snart n er stort nok. Derfor for og tæt nok på 0,5, tæt nok på 1,
ikke/2≥k≥βikke,{\ displaystyle n / 2 \ geq k \ geq \ beta n,}β{\ displaystyle \ beta}(1-2β)/γ{\ displaystyle (1-2 \ beta) / \ gamma}
-a+((1-2β)3/2γ)<0,ukuikke/2≤d(1-2β)ikke/2ikkeikke(1-2β)3/2γ,uk≤vs.ρ~ikkeikke(-a+((1-2β)3/2γ))ikke,{\ 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 { justeret}}}
og
∑k=βikkeikke/2uk ≤ vs.ρ^ikkeikke(-a+((1-2β)3/2γ))ikke ≪ u2.{\ 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}.}
Derfor
limikkeP(G~ikke est vs.oikkeikkeexe)=limikkeP(xikke=0).{\ displaystyle \ lim _ {n} \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ er ~ relateret} \ right) = \ lim _ {n} \ mathbb {P } \ venstre (X_ {n} = 0 \ højre).}
Lad os ved T n angive det første øjeblik t, hvor grafen er forbundet:
G(t,ikke){\ displaystyle \ mathbb {G} \ venstre (t, n \ højre)}
Tikke = inf{t≥0 | G(t,ikke) est vs.oikkeikkeexe},{\ displaystyle T_ {n} \ = \ \ inf \ left \ {t \ geq 0 \ | \ \ mathbb {G} (t, n) \ mathrm {~ er ~ relateret} \ right \},}
så det
{G(t,ikke) est vs.oikkeikkeexe}⇒{Tikke≤t}⇒{∀ε>0,G(t+ε,ikke) est vs.oikkeikkeexe}.{\ displaystyle \ left \ {\ mathbb {G} \ left (t, n \ right) \ mathrm {~ er ~ relateret} \ right \} \ quad \ Rightarrow \ quad \ left \ {T_ {n} \ leq t \ højre \} \ quad \ Rightarrow \ quad \ left \ {\ forall \ varepsilon> 0, \ quad \ mathbb {G} \ left (t + \ varepsilon, n \ right) \ mathrm {~ er ~ relateret} \ right \}.}
Vi kan så se den dobbeltstrengede eksponentiel teorem som følge på den asymptotiske ekspansion af T n : hvis Z n er defineret ved det følgende forhold:
Tikke = lnikkeikke + Zikkeikke,{\ displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ {\ frac {Z_ {n}} {n}},}
derefter hævder den dobbelteksponentielle sætning , at Z n konvergerer i loven mod distributionen af Gumbel , som i en sandsynlig version af noteringen af Landau kunne oversættes med:
Tikke = lnikkeikke + Θ(1ikke).{\ displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ \ Theta \ left ({\ frac {1} {n}} \ right).}
Den uendelige tilfældige graf
Erdős og Rényi generaliserede binomialmodellen til tilfældet med en tællbar uendelig graf , hvilket viser, at vi derefter ( næsten sikkert ) opnåede en graf med universalitetsegenskaber (der især indeholder en hvilken som helst endelig eller tællbar graf som en undergraf ); denne graf er blevet genopdaget flere gange og er oftest kendt som Rado-grafen .
Se også
Bemærkninger
-
Den første artikel, der blev offentliggjort i 1959 , er "On Random Graphs I", Publ. Matematik. Debrecen 6, 290.
-
(in) P. Erdős , " Nogle bemærkninger til teorien om grafer " , Bull. Bitter. Matematik. Soc. , Vol. 53, nr . 4,1947, s. 292-294 ( læs online ). Denne artikel anses ofte for at markere fødslen af den "probabilistiske metode" til undersøgelse af ikke-tilfældige grafer, især for Ramsey-teorien .
-
For baggrund, se (in) Mr. Karoński Ruciński og A., "Oprindelsen til teorien om tilfældige grafer" , i The Mathematics of Paul Erdős , Berlin, Springer al. “Algoritmer kombineres. "( Nr . 13),1997, s. 311-336.
-
For flere detaljer, se Janson, Łuczak og Ruciński 2000 , kap. 2, "Eksponentielt små sandsynligheder".
-
Se Janson, Łuczak og Ruciński 2000 , afsnit 1.4, “Asymptotisk ækvivalens”, s. 14.
-
Se (in) Galen R. Shorack og Jon A. Wellner , Empiriske processer med applikationer til statistik , SIAM ,september 2009, 998 s. ( ISBN 978-0-89871-684-9 , læs online ), afsnit 3.8, “Begrænsning af distributioner under nulhypotesen”, s. 142 og kap. 18, “Den standardiserede kvantilproces”, s. 637.
-
Janson, Łuczak og Ruciński 2000 , Th. 6.7, s. 144.
-
Se artiklen ” bijection de Joyal ”, eller Martin Aigner og Günter M. Ziegler, Guddommelige ræsonnementer , 2 nd edition, 2006, s. 195-201, Cayleys formel for antallet af træer .
Bibliografi
-
(en) Béla Bollobás , tilfældige grafer , Cambridge University Press,Januar 2001, 2 nd ed. ( 1 st ed. 1985), 516 s. ( ISBN 978-0-521-79722-1 , læs online ).
-
(en) Svante Janson (en) , Tomasz Łuczak og Andrzej Ruciński, tilfældige grafer , Wiley-Interscience,Maj 2000, 1 st ed. , 333 s. , indbundet ( ISBN 978-0-471-17541-4 ).
-
(en) Joel Spencer (en) , "Ni forelæsninger om tilfældige grafer" , i Summer School of Probability of Saint-Flour XXI-1991, Part 3 , Springer, coll. "Forelæsningsnotater i matematik. "( Nr . 1541)1993, s. 293-347.
Relateret artikel
Introduktion af sandsynligheder i grafteori
Eksternt link
Laurent Massoulié, Networks: distribueret kontrol og nye fænomener , 2015
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">