A Barabási-Albert féle véletlen fa szélessége

Szakdolgozat

Katona Zsolt Témavezető: Móri Tamás

Eötvös Lóránd Tudományegyetem Természettudományi Kar

1. Bevezetés

Dolgozatomban véletlen gráfokkal azon belül is véletlen fákkal foglalkozom. A véletlen gráfok elméletét Erdős és Rényi alapozta meg az 1960-as évek elején, miután Erdősnek sikerült véletlen módszerekkel megoldani extremális gráfelméleti problémákat. Ezzel a módszerrel ugyanis be lehet bizonyítani bizonyos konstrukciók létezését anélkül, hogy konkrétan megadnánk őket, sőt sok esetben nem is ismerjük őket.

Az első ilyen megoldás Szele [17] nevéhez fűződik, aki 1943-ban belátta, hogy van olyan n csúcsú turnament (teljes gráf, minden éle valamelyik irányban irányítva), amelyben legalább n!/2^{n−1} Hamilton-kör van, hiszen ha az éleket egymástól függetlenül irányítjuk azonos valószínűséggel a két irányba, akkor n!/2^{n−1} a Hamilton körök számának várható értéke. 1947-ben pedig Erdős látta be [8] hasonló módszerrel, hogy az R(k) Ramsey-szám legalább 2^{k/2}.

A véletlen gráf modellek egymástól függetlenül több szerzőnél jelentek meg, először az Erdős-Rényi féle modell, G(n, m). Eszerint az összes n csúcsú m élű gráf közül választunk azonos valószínűséggel. Nagyon a hasonló az először Gilbert [10] által bevezetett gráf G(n, p), ahol n csúcs között húzzuk be a lehetséges éleket egymástól függetlenül azonos p valószínűséggel. (Ha például p = 1/2, akkor az összes n csúcsú gráf közül választottunk azonos valószínűséggel.) Az elmélet felépítése, azonban egyértelműen Erdős és Rényi érdeme a két alapvető modell tekintetében. Ezeket a modelleket természetesen sok irányban lehet általánosítani.

Az informatika fejlődésével párhuzamosan nőtt az érdeklődés a véletlen gráfok iránt és olyan kifejezetten számítógépes alkalmazású modellek születtek mint például a bináris keresőfa, ami alkalmas valamilyen módon rendezett adat tárolására. Ez egy épített fa, tehát egy gyökér csúcsból indulunk, amit kezdetben nevezzünk külső csúcsnak. A következő lépésben kössünk hozzá két új csúcsot egy-egy éllel, most az új csúcsok lesznek külsők a gyökér belsővé válik. Minden további lépésben a külső pontok közül választunk egyet egyforma valószínűséggel és belsővé tesszük úgy, hogy két új külső pontot kötünk hozzá.

Az internet világméretűvé válása nyomán felmerült a kérdés, hogy milyen a struktúrája. Sokan (fizikusok, informatikusok) kezdték vizsgálni a World Wide Web (WWW), azaz interneten elérhető oldalak irányított gráfját melynek éleit az egymásra való hivatkozások határozzák meg. Az eddigi véletlen gráf modellek nem támasztották alá elméletileg a mérési eredményeket, ennek nyomán alkotott Barabási Albert-László és Albert Réka egy új véletlen gráf modellt [1].

2. A Barabási-Albert modell

A WWW mellett számos területen találkozhatunk olyan gráfokkal melyek komplex struktúráját nehéz leírni [1]. Ilyen például az a genetikus hálózat, melynek csúcsai fehérjék, élei pedig a köztük létrejövő kémiai reakciók. Hasonlóan hatalmas hálózatot alkot az idegrendszer, melynek csúcsai az idegsejtek, élei pedig a köztük kapcsolatot létesítő axonok, illetve bizonyos társadalomtudományokban felmerülő szervezeti kapcsolatok hálózatai.

A hálózatok nagy mérete miatt teljes leírásuk reménytelen, az interneten becslések szerint legalább 8 · 10^{8} oldal van. Így merül fel, hogy valamilyen véletlen gráffal lehetne modellezni ezeket a hálózatokat. Első megközelítésként a fokszámeloszlást lehet vizsgálni, azaz a P (k) := P (d_{i} = k) érétékek sorozatát k = 0, 1, 2, ... esetén, ahol d_{i} az i. csúcs fokszáma. Találtak olyan gráfokat, ahol fel tudták jegyezni a fokszámok tapasztalati eloszlását, ilyen például a filmszínészek gráfja, mely azt írja le, hogy ki kivel szerepelt együtt. Azt találták [1], hogy az eloszlás farka P (k) ∼ k^{−γ} alakú, ahol γ = 2, 3 ± 0.1. Másik ilyen példa az USA nyugati elektromos hálózata 4941 csúccsal (erőművek, transzformátorok, alállomások), itt szintén P (k) ∼ k^{−γ′}, ahol a kitevő −4 körül van. A WWW teljes fokszámeloszlását ugyan nem lehet leírni, de bizonyos programok segítségével egy területét igen. Az nd.edu vizsgálata [3] során arra jutottak, hogy az irányított gráf (egy hivatkozásnak iránya van) fokszámeloszlása mind a be-, mind a kifokszámok tekintetében ismét P (k) ∼ k^{−γ}, különbőző, 2, 1 és 2, 45-ös γ értékekkel, ki- illetve befokszám esetén. Érdekes példa még a tudományos publikációk hivatkozási gráfja is, itt γ értéke 3 körüli.

Tehát ezekben a példákban mind hasonló fokszámeloszlást figyeltünk meg, vajon megfelel-e ez az Erdős-Rényi féle véletlen gráf modellnek? Ha n csúcs között a lehetséges éleket egymástól függetlenül, p valószínűséggel húzzuk be, akkor a fokszámeloszlás n növelésével aszimptotikusan Poisson np paraméterrel[4]:

P (k) ∼ e^{−np} \frac{(np)^{k}}{k!} .

A G(n, m) modellben a fokszámeloszlás aszimptotikusan szintén Poisson, \frac{2m}{n} várható értékkel.

Látható, hogy k-ban mindkét esetben exponenciálisan csökken a nagy fokú pontok aránya, ráadásul a paraméter függ a csúcsok számától. Így ez a modell nem felel meg a mérési eredménynek. Másik probléma a hagyományos modellel, hogy a míg a vizsgált hálózatok folyamatosan nőnek, és egy új csúcsot nem teljesen véletlenszerűen kötünk az eddigiekhez (hanem valamilyen tulajdonsága alapján), addig az Erdős-Rényi modellben rögzített a csúcsok száma.

Egy új modell a Watts és Strogatz által bevezetett [18] "kicsi világ" hálózat. A gráf N csúcsa egy egyenesen helyezkedik el sorban és minden szomszéd és másodszomszéd között vezet egy él. Ezek után minden élet p valószínűséggel újra kötünk, azaz az egyik végét átkötjük egy véletlenül választott csúcshoz (egyenletes eloszlás szerint), azzal a megkötéssel, hogy nem keletkezzen többszörös és hurokél. p = 0 esetén a gráf változatlan marad és így az átlagos távolság lineáris függvénye N-nek, míg p = 1 esetén minden élet újra kötünk, ekkor az átlagos távolság logaritmikus függvénye N-nek. A fokszámeloszlás az előbbi esetben nyilván konstans 4, míg ha p → 1, akkor tart ahhoz az Erdős-Rényi féle modelléhez, ahol p = 4/N valószínűséggel húzzuk be az éleket.

A Barabási Albert-László és Albert Réka által bevezetett [1] új modell alapja, hogy új csúcsokat veszünk a gráfhoz és már meglévő csúcsokhoz azok fokszámával arányos valószínűséggel kötjük. A nem teljesen precízen leírt eljárás szerint kezdetben tekintsünk m_{0} csúcsot és minden lépésben vegyünk egy új csúcsot a gráfhoz m ≤ m_{0} éllel. Ezeket az éleket kössük már meglévő csúcsokhoz a csúcsokon

Π(i) = \frac{d_{i}}{∑_{j} d_{j}}

valószínűség-eloszlás szerint. Így t lépés után m_{0} + t csúcs és mt éle lesz a gráfnak. A szerzők, akik fizikusok számítógéppel mérték a modell szerint létrehozott gráf tulajdonságait és azt találták, hogy P (k) ∼ k^{−γ} alakú a fokszámeloszlás γ = 2, 9 ± 0, 1 paraméterrel.

Ezen felül [2]-ban a következőképpen érvelnek γ = 3 mellett. Legyen d_{i} a v_{i} csúcs fokszáma, a t időpontban, amikor a gráfnak t + m_{0} csúcsa és mt éle van. Ha egy új csúcsot adunk hozzá, akkor md_{i}/2mt a valószínűsége, hogy hozzákötjük v_{i}-hez, tehát a fokszámot az idő folytonos függvényeként értelmezve,

\frac{∂d_{i}}{∂t} = \frac{d_{i}}{2t}.

Azzal a kiinduló feltétellel, hogy d_{i} = m a t = i időpontban, azt kapjuk, hogy t függvényeként

d_{i} = m(t/i)^{\frac{1}{2}} .

Ebből pedig egyszerű számolással adódik γ = 3.

3. Matematikai eredmények

Dolgozatomban a fenti modellt vizsgálom, azzal az egyszerűsítéssel, hogy m_{0} = m = 1, azaz egy pontból indulva egyesével veszünk új éleket, illetve pontokat, tehát egy fa keletkezik.

A véletlen fa modellben egy pontból indulunk ki, ez a gyökér. Az első lépésben hozzáveszünk egy új pontot és összekötjük a gyökérrel. Minden további lépésben hozzáveszünk egy új pontot, amelyet egy régi ponttal kötünk össze, minden régi pontot a fokszámával arányos, azaz

Π(i) = \frac{d_{i}}{∑_{j} d_{j}}

valószínűséggel választva. Ugyanezt adja, ha a második lépéstől kezdve mindig egy élt választunk (egyenlő valószínűséggel) a meglévők közül és ennek egyik végpontjához (ismét egyenlő valószínűséggel választva) hozzákötünk egy új pontot egy új éllel. Nyilvánvaló a két eljárás megegyezősége, hiszen az utóbbi esetben egy x csúcsot \frac{1}{2}d_{x} \frac{1}{e} = \frac{d_{x}}{2e} valószínűséggel választottunk, ahol e az élek száma, míg d_{x} a pont foka.

Móri Tamás általánosította [12] az eljárást a következő módon. Válassznuk egy tetszőleges monoton növő, pozitív egészeken értelmezett, pozitív értékű φ fügvényt, jelölje S_{n} a ∑_{j=1}^{n} φ(d_{j}). Az eddigi fokszámarányos valószínűség helyett most

Π(i) = \frac{φ(d_{i})}{S_{n}}

valószínűséggekel kössük az új csúcsot az i., már csúcshoz. Különösen érdekes a φ(k) = k + β eset (β > −1), hiszen ekkor S_{n} = 2n + β(n + 1), tehát nem véletlen.

Móri Tamás megmutatta, hogy a k fokú csúcsok aránya 1 valószínűséggel konvergál egy c_{k} határértékhez, amely, mint k függvénye k^{(−3+β)} alakban csökken.

Ezek kívül belátta, hogy maximális fokszám elosztva n^{\frac{1}{2+β}} -val egy pozitív valószínűségi változóhoz konvergál, amint n → ∞.

Mivel az eredeti modell β = 0-nak felel meg, ez alátámasztja a mérési eredményeket, hiszen ott k^{−3} alakban csökkent a k fokú csúcsok aránya. Az általánosítás révén pedig magyarázatot ad azokra a fent leírt esetekre, amikor a mérés szerint k^{−γ} volt az eredmény 2, 1 és 4 közötti γ-kal.

A fenti eredménnyel párhuzamosan Bollobás, Riordan, Spencer és Tusnády vizsgálta ilyen gráfok fokszámeloszlását [6]. Ehhez bevezettek egy precíz modellt [5] a következők miatt. Először is nem világos, hogy miből indul az eredeti algoritmus, milyen élek vannak az eredeti m_{0} csúcs között. Másrészt azon csúcsok S halmazának eloszlása, amelyeket egy új csúccsal összekötünk nincs meghatározva azon valószínűségek által, hogy egyes csúcsok S-ben vannak-e. Például, ha egy 4 hosszú körből indulunk és m = 2, akkor az ötödik csúcsot bármilyen 0 ≤ α ≤ 1/4 mellett α valószínűséggel köthetjük két szomszédos és 1/2 − 2α valószínűséggel két nem szomszédos csúcshoz. Ugyanis ekkor minden csúcs egyforma valószínűséggel kerül be a két kiválasztott közé és az eredeti modell ezt követeli meg.

Az ilyen problémák elkerülése végett megengedik többszörös- és hurokélek létezését is a gráfban. Először az m = 1 esetben induljunk ki egy csúcsból, amelyhez egy hurok él kapcsolódik. Vegyünk egy új csúcsot, amelyet 2/3 valószínűséggel kössünk hozzá, 1/3 valószínűséggel pedig egy hurokéllel önmagához. Minden további lépésben vegyünk egy új csúcsot és egy róla lelógó élet. A másik végét pedig kössük valamelyik csúcshoz fokszámarányos valószínűséggel, megengedve a hurokélet, hiszen az új csúcsnak már egy a foka a lelógó él miatt. Irányított gráfot úgy kaphatunk, ha az új csúcsból a régi felé mutatnak az irányított élek.

m > 1 esetén készítsünk egy G′ gráfot v′_{1}, v′_{2}, .., csúcsokkal az előbbi eljárással, majd vonjuk össze az v′_{1}, ..., v′_{m}-t egy új v_{1} csúccsá, v′_{m+1}, ..., v′_{2m}-t v_{2}-vé, és így tovább. Az összes élet megtartva így persze többszörös- és új hurokélek is keletkezhetnek. Látható, hogy az m > 1 esetet olyan egyszerűen kapjuk az m = 1 esetből, hogy minden kérdést ez utóbbira érdemes visszaveztni.

Nyilvánvaló, hogy ez a modell nem különbözik lényegesen a fejezet elején leírtaktól, a különbség, hogy itt fa helyett ugyanolyan (csak különböző méretű) fákból álló erdő keletkezik, mindegyiknek a gyökerén egy hurokéllel. A komponensek számának eloszlása könnyen meghatározható, hiszen az nedik lépésben 1/(2n + 1) valószínűséggel keletkezik új komponens, egyébként pedig valamelyik már meglévő fa bővül.

A szerzők az m = 1 eset vizsgálatához [6]-ben a következő ekvivalens leírást adják meg. Vegyünk fel egy egyenesen 2n pontot és párosítsuk őket úgy, hogy minden párosítás azonos valószínűséggel forduljon elő. Létrehozunk egy irányított gráfot. Induljunk el az egyenesen az egyik irányból (balról) és vonjuk össze a pontokat egészen addig, míg egy pár jobb oldali pontjához érünk (ezt is vegyük bele), így kapjuk a v_{1} csúcsot. Most egyesítsük a következő jobb oldali pontig a következőket, így kapjuk a v_{2} csúcsot, és így tovább v_{n}-ig. Az éleket úgy vegyük fel, hogy minden pár jobb oldali pontjának megfelelő csúcsból vezessen a baloldalinak megfelelőbe egy irányított él. Indukcióval könnyen bizonyítható, hogy így ugyanolyan eloszlása lesz a keletkező gráfoknak, mint az eredeti eljárással. Így sikerült egy nemrekurzív ekvivalens jellemzését adni a gráfnak, amelynek segítségével belátták a következő eredményt:

Legyen #_{m}^{n}(d) a d befokú pontok száma az n csúcsú m paraméterű gráfban és

α_{m,d} = \frac{2m(m + 1)}{(d + m)(d + m + 1)(d + m + 2)}.

Ha m ≥ 1 és ε > 0 rögzített, akkor n → ∞ mellett 1-hez tartó valószínűséggel

(1 − ε)α_{m,d} ≤ \frac{#_{m}^{n}(d)}{n} ≤ (1 + ε)α_{m,d},

minden 0 ≤ d ≤ n^{1/15} mellett.

Bollobás és Riordan [5]-ban a fent leírt, többszörös és hurokéleket is megengedő modellben vizsgálta a gráf átmérőjét. m = 1 esetén megmutatták, hogy ha γ a γe^{1+γ} = 1 egyenlet megoldása és ε > 0 rögzített, akkor 1 valószínűséggel a legnagyobb komponens átmérő (1/γ − ε) log n és (1/γ + ε) log n közé esik.

m ≥ 2-re viszont rögzített ε > 0 mellett 1 valószínűséggel a gráf összefüggő és az átmérőjére

(1 − ε) log n/ log log n ≤ diam(G_{m}^{n}) ≤ (1 + ε) log n/ log log n

teljesül.

4. A fa szélessége és magassága

A fát a gyökértől elindulva bontsuk szintekre (a gyökér a 0. szint). Jelölje X[n, k] a k-adik szint méretét az n-edik lépés után (az első lépés után van egy él). Ezek a valószínűségi változók meghatározzák a fa alakját, W_{n} := max{X[n, k] : 1 ≤ k} a szélessége, míg H_{n} := max{k ≥ 1 : X[n, k] ≠ 0} a magassága.

Mivel a magasság szoros kapcsolatban van az átmérővel, [5] eredményeiből levezethető, hogy a H_{n} magasság az általunk vizsgált fa modellben log n nagyságrendű. Móri Tamás megmutatta ezt jobb konstansokkal és általánosítva a φ(k) = k + β esetre. Ezek szerint 1 valószínűséggel

\frac{1 + β}{2 + β} ≤ lim inf_{n→∞} \frac{H_{n}}{log n},

lim sup_{n→∞} \frac{H_{n}}{log n} ≤ min_{z>0} \frac{1 + \frac{1+β}{2+β} z}{log(1 + z)}.

A felső becslés értéke β = 0 esetén 1, 79556, β-nak monoton növő függvénye és határértéke e. A z = e − 1 helyettesítéssel lim sup(H_{n}/ log n) ≤ 1 + \frac{1+β}{2+β} e.

Érdemes ezt az eredményt összehasonlítani más fák magasságával. Rényi és Szekeres belátták [15], hogy ha egyeneletes eloszlás szerint választjuk a fát, akkor

lim_{n→∞} P (\frac{H_{n}}{\sqrt{2n}} < x) = H(x),

ahol H(x) = 4x^{−3}π^{5/2} ∑_{p=1}^{∞} p^{2} exp(−π^{2}p^{2}/x^{2}).

Bináris keresőfákra ismert, hogy H_{n} ∼ c log n, ahol c = 4, 31107.. a c log(2e/c) = 1 egyenlet 2-nél nagyobb megoldása.

Célunk a szélesség meghatározása, melynek alapja Chauvin, Drmota és Jabbour-Hattab módszere [7], akik bináris kereső fákra bebizonyították, hogy W_{n} ∼ \frac{n}{\sqrt{π log n}}.

1. Tétel. 1 valószínűséggel

\frac{X[n, k]}{2n/\sqrt{π log n}} = exp (−\frac{(k − \frac{1}{2} log n)^{2}}{log n} ) + O (\frac{1}{\sqrt{log n}}) ,

ha n → ∞ egyenletes hibataggal k ≥ 0-ra.

2. Következmény. Ha n → ∞, akkor 1 valószínűséggel

\frac{W_{n}}{2n/\sqrt{π log n}} = 1 + O (\frac{1}{\sqrt{log n}}) ,

Látható, hogy az eredmény nem sokban különbözik a bináris keresőfáknál tapasztaltaktól, míg jelentősen eltér az egyenletes eloszlás esetén kialakuló \sqrt{n} nagyságrendtől.

A Barabási féle fa alakja, tehát nagyon hasonlít a bináris keresőfáéhoz, a magasság és szélesség is 2 körüli szorzóval tér el.

5. Tétel bizonyítása

A bizonyítás alapja a következő, komplex generátorfüggvény vizsgálata. Legyen

G_{n}(z) = ∑_{k=0}^{∞} X[n, k + 1]z^{k}.

Az összegzés valójában legfeljebb n-ig megy, hiszen k ≥ n-re X[n, k] = 0. Jelölje F_{n} az első n lépés által generált σ-algebrát. A generátorfüggvényt várható értékével elosztva martingált kapunk F_{n}-re nézve.

3. Lemma.

M_{n}(z) := \frac{G_{n}(z)}{EG_{n}(z)}

martingál F_{n}-re nézve.

Bizonyítás: X[n + 1, k] feltételes eloszlása F_{n}-re nézve a következő:

P (X[n + 1, k] = X[n, k] + 1|F_{n}) = \{ \begin{matrix}\frac{X[n,k]+X[n,k−1]}{2n}, & ha k > 1, \\ \frac{X[n,1]}{2n}, & ha k = 1, \end{matrix}

és nyilván

P (X[n + 1, k] = X[n, k]|F_{n}) = 1 − P (X[n + 1, k] = X[n, k] + 1|F_{n}). Ekkor

E(X[n + 1, 1]|F_{n}) = (X[n, 1] + 1)\frac{X[n, 1]}{2n} + X[n, 1] (1 − \frac{X[n, 1]}{2n}) =

= \frac{X[n, 1]}{2n} + X[n, 1] = \frac{2n + 1}{2n}X[n, 1]

ha k = 1 és

E(X[n + 1, k]|F_{n}) = (X[n, k] + 1)\frac{X[n, k] + X[n, k − 1]}{2n}+

+ X[n, k] (1 − \frac{X[n, k] + X[n, k − 1]}{2n}) = \frac{2n + 1}{2n}X[n, k] + \frac{1}{2n}X[n, k − 1]

ha k > 1. Tehát azt kapjuk, hogy

E(G_{n+1}(z)|F_{n}) = \frac{2n + 1}{2n}G_{n}(z) + \frac{z}{2n}G_{n}(z) = \frac{2n + 1 + z}{2n} G_{n}(z).

Ebből a teljes várható érték tételével rögtön látható, hogy

EG_{n}(z) = ∏_{j=1}^{n−1} \frac{2j + 1 + z}{2j} ,

hiszen G_{1}(z) = 1 azonosan. Tehát M_{n}(z) valóban martingál.

Határozzuk meg a várható érték nagyságrendjét.

4. Lemma. Minden kompakt C komplex halmazon

EG_{n}(z) = \frac{n^{(1+z)/2}}{Γ(\frac{3+z}{2})} + O (n^{(ℜz−1)/2})

egyenletesen z ∈ C-re, ha n → ∞.

Bizonyítás: Az előbbi lemmából

EG_{n}(z) = ∏_{j=1}^{n−1} \frac{2j + 1 + z}{2j} = ∏_{j=1}^{n−1} \frac{j + \frac{1+z}{2}}{j} = \frac{2n}{1 + z} ∏_{j=0}^{n−1} \frac{j + \frac{1+z}{2}}{j + 1} .

Vezessük be az α = \frac{1+z}{2} jelölést. Ekkor az utóbbi produktum a (−1)^{n}\binom{−α}{n} binomiális együttható. Ennek nagyságrendjét [9], [7] szerint lehet meghatározni az

\frac{1}{2πi} ∮ (1 − x)^{−α}x^{−n−1}dx

integrál segítségével. Az adódik, hogy

(−1)^{n}\binom{−α}{n} = \frac{n^{α−1}}{Γ(α)} + O(n^{α−2}),

egyenletesen, minden kompakt halmazon. Tehát

EG_{n}(z) = \frac{n}{α} (\frac{n^{α−1}}{Γ(α)} + O(n^{α−2})) =

= \frac{n^{α}}{Γ(α + 1)} + O(n^{α−1}) = \frac{n^{(1+z)/2}}{Γ(\frac{3+z}{2})} + O (n^{(ℜz−1)/2}) ,

egyenletesen minden kompakt halmazon, amint n → ∞.

A következőkben az M_{n}(z) martingál konvergenciáját fogjuk vizsgálni. Ehhez vizsgáljuk az L^{2}-beli viselkedését, pontosabban G_{n}(z) kovarianciafüggvényét.

5. Lemma. Minden z_{1}, z_{2} ∈ ℂ esetén

C_{n+1}^{G}(z_{1}, z_{2}) := E(G_{n+1}(z_{1})G_{n+1}(z_{2})) =

= ∑_{j=1}^{n} (b_{j}(z_{1}, z_{2}) ∏_{k=j+1}^{n} a_{k}(z_{1}, z_{2})) + ∏_{j=1}^{n} a_{j}(z_{1}, z_{2}),

ahol

a_{k}(z_{1}, z_{2}) = 1 + \frac{1 + (z_{1} + z_{2})/2}{k} és b_{k}(z_{1}, z_{2}) = \frac{1 + z_{1}z_{2}}{2k} EG_{k}(z_{1}z_{2}).

Bizonyítás: Megadunk egy lineáris rekurziót C_{n}^{G}(z_{1}, z_{2})-re. Legyen k_{n}+1 az a valószínűségi változó, mely megadja, hogy hányadik szinten lesz az n+1edik lépésben vett új csúcs. Ekkor G_{n+1}(z) − G_{n}(z) = z^{k_{n}}, hiszen eggyel nő a k_{n} + 1-edik szint mérete, a többi nem változik. Ekkor

C_{n+1}^{G}(z_{1}, z_{2}) = E [E ((G_{n}(z_{1}) + z_{1}^{k_{n}})(G_{n}(z_{2}) + z_{2}^{k_{n}})|F_{n})] = = C_{n}^{G}(z_{1}, z_{2}) + E [E (G_{n}(z_{1})z_{2}^{k_{n}} + z_{1}^{k_{n}}G_{n}(z_{2}) + z_{1}^{k_{n}}z_{2}^{k_{n}}|F_{n})] .

Mivel ismerjük a (k_{n}|F_{n}) feltételes eloszlást, így

P (k_{n} = k) = \{ \begin{matrix}\frac{X[n,k]+X[n,k+1]}{2n}, ha k > 0, \\ \frac{X[n,1]}{2n}, ha k = 0 \end{matrix}

behelyettesítésével

E(G_{n}(z_{1})z_{2}^{k_{n}}|F_{n}) = \frac{X[n, 1]}{2n}G_{n}(z_{1}) + ∑_{k=1}^{∞} \frac{X[n, k] + X[n, k + 1]}{2n}G_{n}(z_{1})z_{2}^{k} =

= \frac{1 + z_{2}}{2n} G_{n}(z_{1})G_{n}(z_{2}),

hasonlóan

E(G_{n}(z_{2})z_{1}^{k_{n}}|F_{n}) = \frac{1 + z_{1}}{2n} G_{n}(z_{1})G_{n}(z_{2}), E(z_{1}^{k_{n}}z_{2}^{k_{n}}|F_{n}) = \frac{1 + z_{1}z_{2}}{2n} G_{n}(z_{1}z_{2}),

tehát

C_{n+1}^{G}(z_{1}, z_{2}) = (1 + \frac{1 + (z_{1} + z_{2})/2}{n}) C_{n}^{G}(z_{1}, z_{2}) + \frac{1 + z_{1}z_{2}}{2n} EG_{n}(z_{1}z_{2}).

Ez a lineáris rekurzió pedig pontosan a felírt képletet adja, tekintve, hogy C_{1}^{G}(z_{1}, z_{2}) = 1 bármely z_{1}, z_{2}-re.

Mit mondhatunk ezután M_{n}(z) L^{2}-beli viselkedéséről?

6. Következmény. \{M_{n}(z) : n ∈ ℕ\} korlátos L^{2}-ben, ha |z − 1| < \sqrt{2}. Emiatt létezik M(z) ∈ L^{2} valószínűségi változó, hogy M_{n}(z) → M(z) 1 valószínűséggel és L^{2}-ben, ha n → ∞ és z ∈ H := \{w ∈ ℂ : |w − 1| < \sqrt{2}\}.

Bizonyítás: Az előző, 5. lemma jelölését használva

∏_{k=j+1}^{n} a_{k}(z_{1}, z_{2}) = (\frac{n}{j})^{1+(z_{1}+z_{2})/2} (1 + O (\frac{1}{j})) .

Vezessük be az A ≪ B jelölést, ha létezik c > 0 konstans úgy, hogy A ≤ cB. Így a 4. lemma alapján

C_{n}^{G}(z_{1}, z_{2}) = \frac{1}{2}(1 + z_{1}z_{2}) ∑_{j=1}^{n} \frac{EG_{j}(z_{1}, z_{2})}{j} ∏_{j=k+1}^{n} a_{k}(z_{1}, z_{2}) + ∏_{j=1}^{n} a_{k}(z_{1}, z_{2}) ≪

≪ ∑_{j=1}^{n} j^{ℜ(1+z_{1}z_{2})/2−1} (\frac{n}{j})^{ℜ(z_{1}+z_{2})/2+1} + n^{ℜ(z_{1}+z_{2})/2+1} ≪

≪ n^{ℜ(z_{1}+z_{2})/2+1} ∑_{j=1}^{n} j^{−ℜ(3+z_{1}+z_{2}−z_{1}z_{2})/2}.

Ebből

C_{n}^{M}(z_{1}, z_{2}) := E(M_{n}(z_{1})M_{n}(z_{2})) =

= \frac{E(G_{n}(z_{1})G_{n}(z_{2})}{EG_{n}(z_{1})EG_{n}(z_{2})} ≪ ∑_{j=1}^{n} j^{−ℜ(3+z_{1}+z_{2}−z_{1}z_{2})/2}.

Tehát ha

ℜ\frac{3 + z + \overline{z} − z\overline{z}}{2} = \frac{3}{2} + ℜz − \frac{|z|^{2}}{2} > 1,

akkor az összeg n-nek korlátos függvénye. A fenti egyenlőtlenség pedig pont H-n teljesül, így M_{n}(z) korlátos L^{2}-ben, ha z ∈ H.

Sőt, mint látni fogjuk, ha z_{1}, z_{2} ∈ H, akkor teljesül ℜ(3+z_{1}+z_{2}−z_{1}z_{2})/2 > 1 is, így C_{n}^{M}(z_{1}, z_{2}) → C^{M}(z_{1}, z_{2}) egyenletesen H^{2} kompakt részhalmazain és C^{M}(z) holomorf H^{2}-en.

Az egyenletes konvergenciát úgy bizonyítjuk, mint [7]. Először szükségünk lesz a következő állításra.

7. Állítás. Legyen I = (1 − \sqrt{2}, 1 + \sqrt{2}). Ekkor (M(t))_{t∈I}-nek van M̃ folytonos változata, amelyre minden kompakt C ⊆ I esetén

E (sup_{t∈C} |M̃|^{2}) < ∞.

Általánosabban, ha γ : ℝ → H folytonosan differenciálható görbe, akkor van (M_{n}(γ(t)))_{t∈R}-nek folytonos M̃_{γ} változata, hogy minden kompakt C ⊆ ℝ esetén

E (sup_{t∈C} |M̃_{γ}(t)|^{2}) < ∞.

Bizonyítás: Nyilvánvalóan \overline{M_{n}(z)} = M_{n}(\overline{z}), így minden z_{1}, z_{2} ∈ H-ra

E(|M(z_{1}) − M(z_{2})|^{2}) = C^{M}(z_{1}, \overline{z_{1}}) + C^{M}(z_{2}, \overline{z_{2}}) − 2ℜ(C^{M}(z_{1}, \overline{z_{2}}). (1)

Ha C′ ⊆ H kompakt, akkor C^{M} regularitása miatt, sorba fejtve a második tagig

C^{M}(z_{1}, \overline{z_{1}}) + C^{M}(z_{2}, \overline{z_{2}}) − 2ℜ(C^{M}(z_{1}, \overline{z_{2}}) ≤ K|z_{1} − z_{2}|^{2}  (2)

valamilyen K > 0 konstanssal minden z_{1}, z_{2} ∈ C′-re. Tehát (1) és (2) alapján

E(|M(z_{1}) − M(z_{2})|^{2}) ≤ K|z_{1} − z_{2}|^{2}.  (3)

Így a Kolmogorov kritérium miatt ([16], 25. oldal), létezik egy folytonos M̃ változat és

E ( sup_{s,t∈C′} \frac{|M̃(t) − M̃(s)|}{|t − s|^{α}})^{2} < ∞

minden α ∈ (0, 1/2)-re. Tehát minden kompakt C ⊆ I esetén

E (sup_{t∈C} |M̃(t)|^{2}) < ∞.

Legyen ezek után γ : ℝ → H folytonosan differenciálható. Tekintsük az M_{n,γ} = M_{n}(γ(t)) martingálokat (t ∈ ℝ). Ekkor (3) a következő alakot ölti:

E(|M_{γ}(t_{1}) − M_{γ}(t_{2})|^{2}) ≤ K|γ(t_{1}) − γ(t_{2})|^{2} ≤ K′|t_{1} − t_{2}|^{2}

valamilyen K′ > 0-val. Tehát (M_{γ}(t))_{t∈ℝ}-nek van folytonos M̃_{γ} változata, amelyre

E (sup_{t∈C} |M̃_{γ}(t)|^{2}) < ∞

minden kompakt C ⊆ ℝ esetén.

(M_{n}) egyenletes konvergenciája a következő állításból következik, amely eredetileg [11]-ból való.

8. Állítás. Minden kompakt C ⊆ I esetén C-n 1 valószínűséggel egyenletesen

M_{n} → M,

E (sup_{t∈C} |M_{n}(t) − M(t)|^{2}) → 0,

ha n → ∞. Általánosabban, ha γ : ℝ → H folytonosan differenciálható görbe, akkor legyen M_{n,γ}(t) = M_{n}(γ(t)) és M_{γ}(t) = M(γ(t)). Ekkor ugyanez igaz (M_{n,γ})-ra.

Bizonyítás: Legyen [a, b] ⊆ I. Az előző állítással kapott M̃ egy olyan valószínűségi változó, melynek értékei E = C([a, b], ℂ) elemei, azaz folytonos komplex értékű függvények. Jelöljük E-vel az E Borel halmazait, és F_{∞} := σ(F_{n}, n ≥ 1), ekkor M̃ nyilván F_{∞}-mérhető.

Legyen φ_{t} : E → ℂ az a folytonos lineáris funkcionál, amely X ∈ E-hez X(t)-t rendeli. Ekkor E(φ_{t}(M̃)|F_{n}) = φ_{t}(E(M̃|F_{n})) m.m. Mivel M̃ M-nek folytonos változata, így minden t ∈ [a, b]-re 1 valószínűséggel φ_{t}(M̃) = M(t). Tehát M_{n}(t) = E(M̃|F_{n})(t) m.m., azaz M_{n} = E(M̃|F_{n}) m.m.

Most alkalmazzuk egy tételt vektorértékű martingálokról ([14], Proposition V-2-6, 104.o.). Eszerint

M_{n} = E(M̃|F_{n}) → E(M̃|F_{∞}) m.m. és L_{E}^{2}-ben is.

Mivel M̃ F_{∞}-mérhető, így

sup_{t∈[a,b]} |M_{n}(t) − M̃(t)| → 0 m.m., ha n → ∞,  (4)

E ( sup_{t∈[a,b]} |M_{n}(t) − M̃(t)|^{2}) →_{n→∞} 0.

Tehát az állítás első része (4)-ből következik, hiszen M(t) = M̃(t) m.m. minden t ∈ [a, b]-re.

A második rész ugyanígy bizonyítható, ha az (M_{n,γ}) és M̃_{γ} martingálokra alkalmazzuk az előző lépéseket.

9. Következmény. M_{n}(z) és a deriváltjai egyenletesen konvergensek H kompakt részhalmazain.

Bizonyítás: Az 8. állítás alapján M_{n} egyenletesen konvergens a γ(t) = 1 + ρe^{it} körön minden 0 < ρ < \sqrt{2} esetén, így mivel |s − 1|ρ esetén

M_{n}(s) = \frac{1}{2πi} ∮_{γ} \frac{M_{n}(z)}{z − s}dz,

a Cauchy formula szerint, így M_{n} és a deriváltjai egyenletesen konvergensek H kompakt részhalmazain.

Az 1. tétel bizonyításához szükség lesz G_{n}(z) további becslésére két lemmában. Először E|G_{n}(z)|^{2}-et becsüljük.

10. Lemma. Minden δ > 0-val, |z − 1| ≤ \sqrt{2} − δ esetén

E|G_{n}(z)|^{2} = O(n^{ℜz+1}),

\sqrt{2} − δ ≤ |z − 1| ≤ \sqrt{2} esetén

E|G_{n}(z)|^{2} = O(n^{ℜz+1} log n),

egyenletes hibatagokkal, ha n → ∞. Ezen kívül, ha C ⊆ ℂ−H kompakt (azaz z ∈ C-re |z − 1| ≥ \sqrt{2}), akkor

E|G_{n}(z)|^{2} = O(n^{(|z|^{2}+1)/2} log n)

egyenletesen z ∈ C-re.

Bizonyítás: Idézzük fel a 6. következmény bizonyításában kapott becslést. Ez alapján

E|G_{n}(z)|^{2} ≪ n^{ℜz+1} ∑_{j=1}^{n} j^{−(3−|z|^{2})/2−ℜz}

Mivel pont az 1 körüli \sqrt{2} sugarú kör az, ahol j kitevője kisebb, mint egy, ezért |z − 1| ≤ \sqrt{2} − δ sugarú körön a kitevő legfeljebb −1 − δ′ < −1, tehát

E|G_{n}(z)|^{2} ≪ n^{ℜz+1} ∑_{j=1}^{n} j^{−1−δ′} ≪ n^{ℜz+1}.

Másrészt, ha \sqrt{2} − δ ≤ |z − 1| ≤ \sqrt{2}, akkor pedig

E|G_{n}(z)|^{2} ≪ n^{ℜz+1} ∑_{j=1}^{n} j^{−1} ≪ n^{ℜz+1} log n.

Harmadrészt |z − 1| > \sqrt{2} esetén a szummát felülről becsülve

E|G_{n}(z)|^{2} ≪ n^{ℜz+1} ∑_{j=1}^{n} j^{−(3−|z|^{2})/2−ℜz} ≪ n^{ℜz+1} \frac{n^{−(1−|z|^{2})/2−ℜz}}{−(1 − |z|^{2})/2 − ℜz} .

Az egyenletességhez azonban ez nem elég, előfordulhat, hogy a nevező tart 0-hoz, viszont tovább felülről becsülve

E|G_{n}(z)|^{2} ≪ n^{ℜz+1} \frac{(n + 1)^{−(1−|z|^{2})/2−ℜz} − 1}{−(1 − |z|^{2})/2 − ℜz} ≪

≪ n^{(|z|^{2}+1)/2} \frac{1 − e^{−((1−|z|^{2})/2−ℜz) log(n+1)}}{−(1 − |z|^{2})/2 − ℜz} .

Ha most a nevező tart 0-hoz, akkor az exponenciális függvényt sorba fejtve látható, hogy

E|G_{n}(z)|^{2} ≪ n^{(|z|^{2}+1)/2} log n.

Ezzel az egyenletességet biztosítottuk, a lemmát bebizonyítottuk.

Most pedig G_{n}(z) deriváltját becsüljük.

11. Lemma. Minden z ≠ 0 mellett, 1 valószínűséggel

|G′_{n}(z)| ≪ |z|^{−1}n^{(|z|+1)/2} log n.

Bizonyítás: Nyilván |G′_{n}(z)| ≤ G′_{n}(|z|). Ismert, hogy a fa magassága H_{n} ≪ c log n. Tehát van n_{0}, hogy n ≥ n_{0}-ra X[n, k] = 0 1 valószínűséggel, ha k > (c + 1) log n. Így elég nagy n-re 1 valószínűséggel

G′_{n}(|z|) = ∑_{k=0}^{∞} kX[n, k + 1]|z|^{k−1} ≤ (c + 1) log n ∑_{k=0}^{∞} X[n, k + 1]|z|^{k−1} =

= (c + 1) log n\frac{G_{n}(|z|)}{|z|},

ami a bizonyítandó becslés.

A tétel bizonyításában G_{n}(z)-t becsüljük majd a |z| = 1 körvonalon. A H körlapon kívüli részen a következő lemmával:

12. Lemma. Minden K > 0-ra van δ > 0, hogy 1 valószínűséggel

sup_{|z|=1,|z−1|≥\sqrt{2}−δ} |G_{n}(z)| = O (\frac{n}{(log n)^{K}} ) ,

ha n → ∞.

Bizonyítás: A Csebisev-egyenlőtlenség szerint

P (|G_{n}(z)| ≥ \frac{n}{(log n)^{K}} ) ≤ \frac{E|G_{n}(z)|^{2}}{(n/(log n)^{K})^{2}} .  (5)

A számlálót a 10. lemma alapján becsülhetjük. Ha ugyanis |z − 1| ≥ \sqrt{2}, akkor |z| = 1 miatt

E|G_{n}(z)|^{2} << n log n,  (6)

ha pedig \sqrt{2} > |z − 1| ≥ \sqrt{2} − δ valamilyen kis δ > 0-val, akkor

E|G_{n}(z)|^{2} << n^{ℜz+1} log n << n^{1+\sqrt{2}δ−δ^{2}/2} log n,  (7)

mert az origó körüli 1 sugarú és az 1 körüli \sqrt{2} sugarú kör ±i-ben metszi egymást és ebből pontosan kiszámolhatjuk, hogy mennyi ℜz, ha |z − 1| = \sqrt{2} − δ.

Tehát (5), (6) és (7) alapján minden ε > 0-hoz van δ > 0 (ε = \sqrt{2}δ−δ^{2}/2ből visszaszámolva), hogy |z| = 1 és |z − 1| ≥ \sqrt{2} − δ mellett

P (|G_{n}(z)| ≥ \frac{n}{(log n)^{K}} ) ≤ \frac{E|G_{n}(z)|^{2}}{(n/(log n)^{K})^{2}} << \frac{(log n)^{2K+1}}{n^{1−ε}} .  (8)

Legyen φ = arg z_{δ}, ahol z_{δ} a |z| = 1, |z − 1| = \sqrt{2} − δ egyenleteknek eleget tevő komplex számok közül a pozitív képzetes részű, tehát a két kör felső metszéspontja. Legyen z(n, j) = e^{t(n,j)}, ahol

t(n, j) = φ + (2π − 2φ)\frac{j}{(log n)^{K+1}} ,

ahol j = 0, 1, ..., (log n)^{K+1}. Ezek a pontok tehát a |z| = 1 kör |z−1| ≥ \sqrt{2}−δ ívét osztják fel egyenlő részekre. Az únió valószínűségét a valószínűségek összegével becsülve tehát (8) miatt

P (|G_{n}(z(n, j))| ≥ \frac{n}{(log n)^{K}} valamely j-re) ≤ \frac{(log n)^{3K+2}}{n^{1−ε}} .

Vegyük észre, hogy elég kis ε-ra

∑_{n≥0} \frac{(log(n^{2}))^{3K+2}}{n^{2(1−ε)}} < ∞,

így a Borel-Cantelli lemma miatt 1 valószínűséggel legfeljebb véges sok n kivételével

sup_{j} |G_{n^{2}}(z(n^{2}, j))| ≤ \frac{n^{2}}{(log(n^{2}))^{K}} .

Az 10. lemma segítségével becsülhetünk az osztópontok között. Tegyük fel, hogy |z| = 1, t(n^{2}, j) < arg z < t(n^{2}, j + 1). Ekkor egyenletesen

G_{n^{2}}(z) = G_{n^{2}}(z(n^{2}, j)) + O(G′_{n^{2}}(1)(log(n^{2}))^{−K−1}) ≤

≤ \frac{n^{2}}{(log(n^{2}))^{K}} + O(n^{2}(log(n^{2}))^{1−K−1}) << \frac{n^{2}}{(log(n^{2}))^{K}} .

Tehát 1 valószínűséggel legfeljebb véges sok kivétellel

sup_{|z|=1,|z−1|≥\sqrt{2}−δ} |G_{n^{2}}(z)| ≤ \frac{n^{2}}{(log(n^{2}))^{K}} .

Végül idézzük fel a G_{n+1}(z) − G_{n}(z) = z^{k_{n}} egyenlőséget. Ez alapján 1 ≤ k < 2n + 1-re egyenletesen

G_{n^{2}+k}(z) = G_{n^{2}}(z) + O(k) << \frac{n^{2}}{(log(n^{2}))^{K}} + O(n) << \frac{n^{2} + k}{(log(n^{2} + k))^{K}} .

Tehát 1 valószínűséggel legfeljebb véges sok kivétellel

sup_{|z|=1,|z−1|≥\sqrt{2}−δ} |G_{n}(z)| ≤ \frac{n}{(log(n))^{K}} .

Ezek után rátérhetünk közvetlenül a tétel bizonyítására. Az X[n, k] együtthatót a Cauchy-formula segítségével nyerjük ki a G_{n}(z) generátorfüggvényből:

X[n, k + 1] = \frac{1}{2πi} ∫_{|z|=1} \frac{G_{n}(ξ)}{ξ^{k+1}}dξ = \frac{1}{2π} ∫_{−π}^{π} G_{n}(e^{it})e^{−kit}dt.

Az integrált bontsuk két részre:

I_{1} := \frac{1}{2π} ∫_{|t|≤π/2−δ} G_{n}(e^{it})e^{−kit}dt,

I_{2} := \frac{1}{2π} ∫_{π≥|t|≥π/2−δ} G_{n}(e^{it})e^{−kit}dt,

olyan δ-val, amely eleget tesz a 12. lemma feltételének. A lemmát alkalmazva tetszőleges K > 0-ra becsülhetjük a második integrált a következőképpen:

|I_{2}| ≤ \frac{1}{2π} ∫_{π≥|t|≥π/2−δ} |G_{n}(e^{it})|dt << \frac{n}{(log n)^{K}} .  (9)

A |t| ≤ π/2 − δ esetben használjuk ki, hogy a 9. következmény miatt

M_{n}(e^{it}) = \frac{G_{n}(e^{it})}{EG_{n}(e^{it})}

1 valószínűséggel egyenletesen korlátos. A nevező nagyságrendjét a 4. lemma alapján ismerjük és az egyenletes korlátosság miatt a számláló abszolút értéke ennek legfeljebb konstansszorosa. Tehát

|G_{n}(e^{it})| << n^{(1+ℜe^{it})/2} = n · n^{(ℜe^{it}−1)/2} = n · n^{(cos t−1)/2} = = ne^{(cos t−1)(log n)/2} << ne^{−c′t^{2}(log n)}

valamilyen c′ > 0 konstanssal. Rögzítsünk egy elég kis pozitív ϑ-t. Ekkor

\frac{1}{2π} ∫_{(log n)^{−(1−ϑ)/2}≤|t|≤π/2−δ} |G_{n}(e^{it})|dt << n ∫_{(log n)^{−(1−ϑ)/2}}^{∞} e^{−c′t^{2} log n}dt. (10)

Ha Y normális eloszlású valószínűségi változó 0 várható értékkel és σ^{2} szórásnégyzettel, akkor

∫_{η}^{∞} e^{− \frac{t^{2}}{2σ^{2}}} dt = \sqrt{2π}σP (Y ≥ η) = \sqrt{2π}σP (\frac{Y}{σ} ≥ \frac{η}{σ} ) ,

ahol X_{1} := Y/σ már standard normális, legyen X_{2} szintén, de független az elsőtől. Ekkor

P (X_{1} ≥ \frac{η}{σ} ) ≤ P (X_{1}^{2} ≥ \frac{η^{2}}{σ^{2}} ) ≤ P (X_{1}^{2} + X_{2}^{2} ≥ \frac{η^{2}}{σ^{2}} ) = exp (−\frac{1}{2} \frac{η^{2}}{σ^{2}} ) .

Így (10) tovább folytatható, ha σ^{2} = 1/(c′ log n)-et és η = (log n)^{−(1−ϑ)/2}-t helyettesítünk a számolásba.

n ∫_{(log n)^{−(1−ϑ)/2}}^{∞} e^{−c′t^{2} log n}dt << ne^{−c′(logn)^{ϑ}}.

Látható, hogy ez bármilyen pozitív ϑ-ra aszimptotikusan kisebb, mint az |I_{2}|-re (9)-ben kapott becslés.

Tehát a teljes integrálból marad

I_{0} := \frac{1}{2π} ∫_{|t|≤(log n)^{−(1−ϑ)/2}} G_{n}(e^{it})e^{−kit}dt.

Definíció alapján

G_{n}(z) = EG_{n}(z)M_{n}(z)  (11)

A 4. lemma a következő alakba is írható

EG_{n}(z) = \frac{n^{(1+z)/2}}{Γ(\frac{3+z}{2})} + O (n^{(ℜz−1)/2}) = n · n^{(z−1)/2} (\frac{1}{Γ(\frac{3+z}{2})} + O (\frac{1}{n}))

egyenletesen. Ebből, ha t → 0, ráadásul úgy, hogy |t| ≤ (log n)^{−(1−ϑ)/2}, akkor

EG_{n}(e^{it}) = ne^{\frac{1}{2} (e^{it}−1)(log n)} (\frac{1}{Γ(\frac{3+e^{it}}{2} )} + O (\frac{1}{n})) =

= ne^{−(t^{2}/4) log n+(it/2) log n} (1 − \frac{it}{2}Γ′(2) − \frac{t^{3}}{12}i log n + O(t^{4} log n)) . (12)

Másrészt, mivel M_{n}(1) = 1, így

M_{n}(e^{it}) = 1 + itM′_{n}(1) + O(t^{2}).  (13)

Ekkor (11)-be behelyettesítve (12)-t és (13)-at, kapjuk, hogy k-ban egyenletesen 1 valószínűséggel

G_{n}(e^{it})e^{−kit} = ne^{it((log n)/2−k)−(t^{2}/4) log n}·

· (1 + it (M′_{n}(1) − \frac{Γ′(2)}{2}) − i\frac{t^{3}}{12} log n + O(t^{2} + t^{4} log n)) .

Parciális integrálással kapjuk, hogy

∫_{−∞}^{∞} e^{−(t^{2}/4) log n}(t^{2} + t^{4} log n)dt = 72\sqrt{π}(log n)^{−3/2}.

Ugyanúgy becsülve, mint (10) kapjuk, hogy

∫_{|t|≥(log n)^{−(1−ϑ)/2}} e^{−t^{2} log n}(1 + t + t^{3} log n) << e^{−(log n)^{ϑ}}.

Így azt kapjuk, hogy

\frac{I_{0}}{n} = \frac{1}{2π} ∫_{−∞}^{∞} e^{it((1/2) log n−k)−(t^{2}/4) log n}·

· (1 + it (M′_{n}(1) − \frac{Γ′(2)}{2}) − i\frac{t^{3}}{12} log n) dt + O((log n)^{−3/2}).

Az integrálást elvégezve

\frac{I_{0}}{n} = \frac{2}{\sqrt{π log n}} exp (−\frac{(\frac{1}{2} log n − k)^{2}}{log n} ) ·

· (1 + \frac{\frac{1}{2} log n − k}{log n} − \frac{2(\frac{1}{2} log n − k)^{3}}{3(log n)^{2}} − 2 \frac{\frac{1}{2} log n − k}{log n} (M′_{n}(1) − Γ′(2)/2)) +

+ O((log n)^{−3/2}).

Tehát 1 valószínűséggel, k-ban egyenletes hibataggal

\frac{X[n, k]}{2n/\sqrt{π log n}} = exp (−\frac{(\frac{1}{2} log n − k)^{2}}{log n} ) ·

· (1 + \frac{\frac{1}{2} log n − k}{log n} − \frac{2(\frac{1}{2} log n − k)^{3}}{3(log n)^{2}} − 2 \frac{\frac{1}{2} log n − k}{log n} (M′_{n}(1) − Γ′(2)/2)) +

+ O (\frac{1}{log n}) .

Ebből már következik a tétel állítása, hiszen |\frac{1}{2} log n − k| ≤ c\sqrt{log n} esetén

\frac{X[n, k]}{2n/\sqrt{π log n}} = exp (−\frac{(\frac{1}{2} log n − k)^{2}}{log n} ) (1 + O (\frac{1}{\sqrt{log n}})) .

Ez az eset a tétel lényeges állítása, azaz ha valamely köz epső szint mérett́ vizsgáljuk. Ha ugyanis k messze van \frac{1}{2} log n-től, akkor az O (\frac{1}{\sqrt{log n}}) tag meghatározó, így az alsó és felsö szintek méretére ad felsö becslést.

Ezzel a bizonyítást befejeztük.

Itt szeretnék köszönetet mondani Móri Tamásnak témavezetői munkájáért.

Hivatkozások

[1] Barabási, A.-L., Albert, R., Emergence of scaling in random networks, Science 286 (1999), 509-512.

[2] Barabási, A.-L., Albert, R., Hawoong Jeong Mean-field theory for scale-free random networks, Physica A 272 (1999) 173-187.

[3] Barabási, A.-L., Albert, R., Hawoong Jeong Scale-free characteristics of random networks: the topology of the world-wide web, Physica A 281 (2000) 69-77.

[4] Bollobás, B. Random Graphs, Academic Press, London (1985)

[5] Bollobás, B., Riordan, O., The diameter of a scale-free random graph, Combinatorica (2003)

[6] Bollobás, B., Riordan, O., Spencer, J., Tusnády, G., The degree sequence of a scale-free random graph process, Random Structures Algorithms 18 (2001), 279-290.

[7] Chauvin, B., Drmota, M., Jabbour-Hattab, J., The profile of binary search trees, The Annals of Applied Probability 11 (2001), 1042-1062.

[8] Erdős, P., Some remarks on the theory of graphs, Bull. Res. Council Israel, Section F 7 (1947) 292-294.

[9] Flajolet, P., Odlyzko, A.M. Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), 216-240

[10] Gilbert, E.N., Random graphs, Ann. Math. Statist. 30 (1959), 1141-1144.

[11] Joffe, A. Le Cam, L., Neveu, J. Sur la loi des grands nombres pour des variables aléatoires attachées à un arbre dyadique, C. R. Acad. Sci. Paris. Ser. A 277 (1973), 963-964.

[12] Móri, T.F.,On random trees, Studia Sci. Math. Hungar. 39 (2002), 143-155.

[13] Móri, T.F.,The maximum degree of the Barabási random tree, Combinatorics, Probability & Computing (megjelenés alatt)

[14] Neveu, J., Martingales à temps discret, Masson and Cie, Paris (1972)

[15] Rényi, A., Szekeres, G., On the height of trees, J. Austral. Math. Soc. 7 (1967) 497-507.

[16] Revuz, D., Yor, M. Continuous Martingales and Brownian Motion, Springer, New York (1990)

[17] Szele, T., Combinatorial investigations concerning complete directed graphs, Matematikai és Fizikai Lapok 50 (1943) 287-293.

[18] Watts, D.J., Strogatz, S.H., Collective dynamics of small-worlds’ networks, Nature 393 (1998), 440-442.