Véletlen bolyongások (Z^d)-n és speciális gráfokon

Bevezetés

Közismert eredmény Pólya György tétele, amely szerint egy, a számegyenes egész számain ((Z^1)) vagy a síkbeli négyzetrácson ((Z^2)) való szimmetrikus egyszerű bolyongás (azaz olyan bolyongás, amely minden lépésben azonos valószínűséggel lép az aktuális helyének minden szomszédjára) 1 valószínűséggel visszatér a kiindulási helyére (azaz a (Z^1), (Z^2) gráfok rekurrensek), viszont (Z^d)-n, ha d>2 egész, már pozitív valószínűséggel nem tér vissza. (A bizonyítás megtalálható például az [1] könyv 1. kötetének XIV. fejezetében.) A dolgozat első felében ilyen, (Z^d)-n történő bolyongásokat szimulálok, megvizsgálva több jellemzőjüket: visszatérnek-e az origóba, illetve hányszor térnek vissza; adott számú lépést téve milyen messzire jutnak el az origótól átlagosan, addig mi a maximális távolságuk az origótól, a térnek milyen részét járják be.
Egy másik probléma, hogy egy végtelen gráfon két szimmetrikus egyszerű bolyongás találkozik-e. Világos, hogy ez (Z^d)-n ekvivalens a rekurrenciával, mivel az egyik séta minden lépését helyettesíthetjük a másik séta ellenkező irányba történő léptetésével. A dolgozat második részében olyan speciális gráfokon való bolyongásokat vizsgálok, amelyeken ez a két probléma nem ekvivalens: a gráf rekurrens ugyan, de két egyszerű szimmetrikus bolyongás pozitív valószínűséggel soha nem találkozik.

Egy-egy séta 1, 2 és 3 dimenzióban

A (Z^1), (Z^2) és a (Z^3) közötti különbség már egy-egy ábrán is látható. Amíg 1 és 2 dimenzióban a bolyongás meglehetősen sűrűn bejárja a tér egy részét, 3 dimenzióban sokkal kevésbé tölti ki a teret. A rekurrenciából ugyanis (összefüggő gráfok esetén) következik, hogy a bolyongás a gráf minden csúcsát 1 valószínűséggel végtelen sokszor eléri. (Bizonyítás: ha egy adott O csúcsból indítva a bolyongás 1 valószínűséggel visszatér O-ba, akkor speciálisan akkor is 1 valószínűséggel visszatér, ha előbb eljut egy adott A csúcsba. Ezért A-ból indítva 1 valószínűséggel elér O-ba. Másrészt egy P-vel jelölt O->A út esetén pozitív a valószínűsége, hogy O-ból indítva ezen halad. A bolyongás O-ból indítva 1 valószínűséggel visszatér O-ba, így 1 valószínűséggel végtelen sokszot visszatér O-ba (nem lehet pozitív a valószínűsége annak, hogy pontosan k-szor jár O-ban, ha k egy véges szám). Ezért annak a valószínűsége, hogy egyetlen O-ba való visszatérés után sem választja a P utat, 0. Tehát 1 valószínűséggel valamikor elér A-ba. Mivel A a gráf tetszőleges csúcsa volt, beláttuk, hogy a bolyongás O-ból indítva bármely csúcsot 1 valószínűséggel elér, és bármely csúcsból indítva 1 valószínűséggel eléri O-t. Tehát bármely A és B, nem feltétlenül különböző csúcsok esetén a bolyongás A-ból indulva 1 valószínűséggel eléri B-t (például O-n keresztül). Ebből már következik, hogy a bolyongás (bárhonnan indulva) bármelyik csúcsot 1 valószínűséggel végtelen sokszor bejárja.)

Program a bolyongás kirajzolására:

ClearAll[Lepesek,Bolyongas,maxtav,vegtav,szoveg1,szoveg2,szoveg3];
Lepesek[d_]:=Array[Table[KroneckerDelta[i,#],{i,1,d}]&,d]~Join~Array[-Table[KroneckerDelta[i,#],{i,1,d}]&,d];
Bolyongas[n_,d_]:=Module[{seta=Accumulate[RandomChoice[Lepesek[d],n]]},
vegtav=Norm[seta[[n]]];
maxtav=Max[Array[Norm[seta[[#]]]&,n]];
szoveg1=Row[{"A végpont távolsága az origótól: ",N[vegtav]}];
szoveg2=Row[{"Maximális távolság az origótól: ",N[maxtav]}];
szoveg3=Row[{"(Sqrt[n])=",N[Sqrt[n]]}];
Which[d==1,Column[{ListPlot[{Flatten[seta],{Flatten[seta][[-1]]}},Joined->{True,False},PlotStyle->{Red,PointSize[Large]},AspectRatio->1,ImageSize->Medium],szoveg1,szoveg2,szoveg3}],
d==2,Column[{ListPlot[{seta,{seta[[-1]]}},Joined->{True,False},PlotStyle->{Red,PointSize[Large]},AspectRatio->1,ImageSize->Medium],szoveg1,szoveg2,szoveg3}],
d==3,Column[{ListPointPlot3D[{seta,{seta[[-1]]},{{0,0,0}}},AspectRatio->1,ColorFunction->"BlueGreenYellow",ImageSize->Medium],szoveg1,szoveg2,szoveg3}]]];

1 dimenziós bolyongás:

Bolyongas[1000000,1]

2 dimenziós bolyongás:

Bolyongas[1000000,2]

3 dimenziós bolyongás:

Bolyongas[100000,3]

A séták maximális távolsága az origótól az első n lépésben, és a távolság n lépés megtétele után is (Sqrt[n])nagyságrendjébe esik. (Pontosabb összefüggés majd sok séta átlagolásából látható.)

Sok séta átlagolva (Z^d)-n

(Z^2)-n a sík milyen részét járja be?

Sok sétát összegezve (átlagolva) látható, hogy a síknak milyen részét járják be a bolyongások. Egy origó körüli nagyjából szabályos kört kapunk, amelyben minél közelebb van egy pont az origóhoz, annál nagyobb valószínűséggel éri el a séta n lépésen belül. A rácsszerkezet tehát nagy n-re már eltűnik, mintha bármilyen irányba léphetne a bolyongó. (Mindenhol k jelöli a séták számát, n a séták lépésszámát.)

ClearAll[n,k,setak];
n=1000;
k=1000;
setak=Array[Accumulate[RandomChoice[{{0,1},{0,-1},{1,0},{-1,0}},n]]&,{k}];

ClearAll[t];
t=Total[Array[Count[setak[[#1]],{#2-71,#3-71}]&,{k,141,141}]];

MatrixPlot[t]

Visszatér-e az origóba, és ha igen, hány lépés után?

ClearAll[n,k,d,lepesek,origo,setak,visszateresek];
d=1;
lepesek=Lepesek[d];
origo=Array[0&,d];
n=5000;
k=1000;
setak=Array[Accumulate[RandomChoice[lepesek,n]]&,k];
visszateresek=Array[LengthWhile[setak[[#]],#≠origo&]+1&,k];

Sort[visszateresek/.(n+1)->"nem"]

10000 sétát vizsgálva :

Grid[{{"az első visszatérés ideje","1-100","101-300","301-500","501-1000","1001-2000","2001-3000","3001-5000","visszatért 5000 lépés alatt","nem tért vissza 5000 lépés alatt"},
{"1 dimenzióban",9235,309,100,108,75,25,32,9884,116},{"2 dimenzióban",5881,522,201,227,196,102,131,7260,2740},{"3 dimenzióban",3092,117,39,33,23,9,12,3325,6675}},Frame->All]

3 dimenzióban 10000 sétából 3325 tért vissza az origóba 5000 lépésen belül, így a visszatérés valószínűsége ennyi lépés alatt kb. 0,3325. Az látszik az eredményekből, hogy n növelésével nem nőne jelentősen ez a valószínűség, mert amikor a bolyongás nem tért vissza az origóba az első 200-300 lépésben, akkor nagyon kevés alkalommal tért vissza a további több, mint 4000 lépésben. (116 tért vissza a 300. és az 5000. lépés között.) Valóban, kiszámolható, hogy az origóba való visszatérés valószínűsége kb. 0,35.
2 dimenzióban láthatóan más a visszatérések idejének eloszlása. Itt sokkal egyenletesebben oszlik el, például 131 séta tért vissza a 3000. és az 5000. lépés között, míg 3 dimenzióban csak 12 . Mivel a visszatérés idejének várható értéke végtelen, akármilyen hosszú sétákat nézünk, nagy valószínűséggel sok olyan lesz, ami nem tér vissza (10000 sétából 7260 tért vissza 5000 lépés alatt), de a különbség a 3 dimenziós esethez képest szemmel látható.
1 dimenzióban egyértelműen látható a rekurrencia: a séták nagy többsége viszonylag kevés lépés után visszatér (10000 sétából 9235 visszatért 100 lépésen belül, 9752 visszatért 1000 lépésen belül, 9884 5000 lépésen belül).

A visszatérések számának eloszlása

A végtelen séta origóba való visszatérései számának eloszlását próbáljuk meg közelíteni. Ehhez megvizsgáljuk, hogy mi a súlyfüggvény az első m lépést tekintve, egyre nagyobb m-eket véve.

1 dimenzióban :

ClearAll[n,k,d,lepesek,origo,setak,visszateresek];
n=10000;
k=1000;
d=1;
lepesek=Lepesek[d];
origo=Array[0&,d];
setak=Array[Accumulate[RandomChoice[lepesek,n]]&,k];
visszateresek=Array[Position[setak[[#]],origo]&,k];

ClearAll[m,visszateresekmig];
visszateresekmig[m_]:=Array[Select[visszateresek[[#]],#[[1]]≤m&]&,k];
Row[Table[DiscretePlot[Length[Select[visszateresekmig[m],Length[#]==x&]]/k,{x,500},Joined->True,ImageSize->Medium,PlotRange->{0,0.04}],{m,{2000,5000,10000}}]]

2 dimenzióban:

ClearAll[n,k,d,lepesek,origo,setak,visszateresek];
n=50000;
k=1000;
d=2;
lepesek=Lepesek[d];
origo=Array[0&,d];
setak=Array[Accumulate[RandomChoice[lepesek,n]]&,k];
visszateresek=Array[Position[setak[[#]],origo]&,k];

ClearAll[m,visszateresekmig];
visszateresekmig[m_]:=Array[Select[visszateresek[[#]],#[[1]]≤m&]&,k];
Row[Table[DiscretePlot[Length[Select[visszateresekmig[m],Length[#]==x&]]/k,{x,100},Joined->True,ImageSize->Medium,PlotRange->{0,0.15}],{m,{10000,20000,50000}}]]

3 dimenzióban :

ClearAll[n,k,d,lepesek,origo,setak,visszateresek];
n=50000;
k=1000;
d=3;
lepesek=Lepesek[d];
origo=Array[0&,d];
setak=Array[Accumulate[RandomChoice[lepesek,n]]&,k];
visszateresek=Array[Position[setak[[#]],origo]&,k];

ClearAll[m,visszateresekmig];
visszateresekmig[m_]:=Array[Select[visszateresek[[#]],#[[1]]≤m&]&,k];
Row[Table[DiscretePlot[Length[Select[visszateresekmig[m],Length[#]==x&]]/k,{x,100},Joined->True,ImageSize->Medium,PlotRange->{0,0.15}],{m,{10000,20000,50000}}]]

1 dimenzióban látható, hogy a találkozások számának eloszlása m növekedtével egyre egyenletesebb, a súly egyre jobban szétterül a számegyenesen. Ebből sejthető, hogy a végtelen bolyongás végtelen sokszor vissza fog térni.
2 dimenzióban még 50000 lépésig vizsgálva is nagy a súly a kicsi értékeken, és gyorsan lecseng a súlyfüggvény. Tehát itt nagyon lassú az eloszlás konvergenciája. (A rekurrencia miatt itt is végtelen sokszor visszatér a végtelen séta.)
3 dimenzióban keveset változik a súlyfüggvény m növekedtével a vizsgált esetekben. Ezért a kapott súlyfüggvények jó közelítései a végtelen séta súlyfüggvényének. Kiszámítható, hogy egy végtelen séta várhatóan kb. 0,53-szor tér vissza az origóba. (A visszatérések számának eloszlása pesszimista geometriai, amelynek paramétere kb. 0,65, ugyanis az origóból indítva kb. 0,35 valószínűséggel tér vissza.)

Milyen messze jár maximum?

ClearAll[n,k,d,lepesek,setak,max];
d=3;
lepesek=Lepesek[d];
n=5000;
k=1000;
setak=Array[Accumulate[RandomChoice[lepesek,n]]&,k];
max=Table[Max[Array[N[Norm[setak[[i,#]]]]&,n]],{i,k}];
Total[max]/(k Sqrt[n])

A bolyongás maximális távolsága az origótól az első n lépés alatt (Sqrt[n])rendjébe esik. Sok sétát (kis n-re 10000, nagy n-re 1000 darabot) átlagolva az átlagos maximális távolság és (Sqrt[n]) hányadosa:

Grid[{{,"n=50","n=100","n=500","n=1000","n=2000","n=3000","n=4000","n=5000"},
{"1 dimenzióban",1.1918,1.2034,1.2324,1.2405,1.2341,1.2468,1.2530,1.2356},
{"2 dimenzióban",1.1190,1.1377,1.1571,1.1461,1.1539,1.1794,1.1738,1.1646},
{"3 dimenzióban",1.0969,1.1089,1.1224,1.1219,1.1247,1.1373,1.1334,1.1416}},Frame->All]

Látható, hogy a hányadosok keveset változnak n növekedtével, tehát valóban (Sqrt[n]) a nagyságrend, mégpedig a dimenzió növekedtével egyre kisebb konstansszorzóval.

Milyen messze van a végén?

ClearAll[n,k,d];
d=3;
lepesek=Lepesek[d];
n=100000;
k=1000;
Total[Array[N[Norm[Nest[#+RandomChoice[lepesek]&,Array[0&,d],n]]]&,k]]/(k Sqrt[n])

A bolyongás távolsága n lépés után az origótól szintén (Sqrt[n]) rendjébe esik. (Az is igaz, hogy a távolság négyzetének várható értéke pontosan n.) Sok (10000, illetve 1000) sétát átlagolva az elért távolság és (Sqrt[n]) hányadosa:

Grid[{{,"n=50","n=100","n=500","n=1000","n=5000","n=10000","n=50000","n=100000"},
{"1 dimenzióban",0.8010,0.7993,0.7951,0.8041,0.7944,0.7885,0.8006,0.7962},
{"2 dimenzióban",0.8917,0.8898,0.8809,0.8860,0.8875,0.8862,0.8767,0.8890},
{"3 dimenzióban",0.9153,0.9193,0.9256,0.9260,0.9217,0.9138,0.9202,0.9238}},Frame->All]

(1 dimenzióban kiszámítható, hogy a hányados n->∞ esetén (Sqrt[(2/π)])≈0,7979-hez tart.)
Érdekes módon itt a dimenzió növekedtével növekedés figyelhető meg, tehát miközben a (Sqrt[n]) konstansszorzója a maximális távolságban csökken a dimenzió növekedtével, a végpont távolságában nő.

Bolyongások "fésűn"

Definiáljuk a következő gráfokat:
G(∞): a csúcshalmaza (Z^2), az élhalmaza {{(x,y), (x',y')} : (y=y'=0 és |x-x'|=1) vagy (x=x' és |y-y'|=1)};
G(α): a csúcshalmaza {(x,y)∈(Z^2) : 0⩽y⩽|x((|)^α)}, az élhalmaza G(∞) élhalmazának erre a csúcshalmazra való leszűkítése (α pozitív valós szám).

Graphics[{Red, PointSize[Large], Line[{{-3.5,0}, {3.5,0}}], Array[Line[{{#-4,-2.5},{#-4,2.5}}]&,7], Array[Point[{#1-4,#2-3}]&,{7,5}], Black, Inset[Style["G(∞)", 20],{0,-3}],
Red, Line[{{5.5,-2}, {12.5, -2}}], Array[Line[{{#+5, -2},{#+5, -2+(((4-#))^2)/2}}]&,7], Array[Table[Point[{#+5, -2+i/2}], {i,0,(((4-#))^2)}]&,7], Black, Inset[Style["G(2)", 20], {9,-3}]}]

Az könnyen látható, hogy mivel Z (a számegyenes) rekurrens gráf, ezek a gráfok is rekurrensek. Ugyanis az, hogy Z csúcsaiból most kiágaznak véges hosszú szakaszok, illetve egy-egy Z-vel izomorf gráf, nem változtat az origóba való visszatérés valószínűségén, mivel ezekről a kiágazásokról a bolyongó 1 valószínűséggel visszatér a gerincre. Ugyanakkor, ha két független bolyongást indítunk el az origóból, azok nem feltétlenül fognak 1 valószínűséggel találkozni. Tehát ezeken a gráfokon nem ekvivalens a találkozás és a visszatérés problémája, ellentétben a (Z^d)gráfokkal. Azt vizsgálom meg, hogy ezen gráfok közül pontosan melyekre teljesül, hogy két független bolyongás pozitív valószínűséggel nem találkozik.

Egy csúcs szomszédai G(α)-ban, illetve G(∞)-ben:

ClearAll[szomszedok];
szomszedok[{a_,b_}, α_]:=Select[{a,b}/.{{{a,b}/;b==0->{a+1,b}},{{a,b}/;b==0->{a-1,b}},{{a,b}/;b<Floor[(((Abs[a]))^α)]->{a,b+1}},{{a,b}/;b>0->{a,b-1}}},#≠{a,b}&]
szomszedok[{a_, b_}]:=Select[{a,b}/.{{{a,b}/;b==0->{a+1,b}},{{a,b}/;b==0->{a-1,b}},{{a,b}->{a,b+1}},{{a,b}->{a,b-1}}},#≠{a,b}&]

Az első találkozás ideje

ClearAll[x,y,n,k,α,i,talalkozas,talalkozasok];
α=1/3;
n=100000;
k=1000;
talalkozasok={};
Do[
x={0,0};
y={0,0};
i=0;
talalkozas=0;
While[i<n&&talalkozas==0,x=RandomChoice[szomszedok[x,α]];y=RandomChoice[szomszedok[y,α]];i++;If[x==y,talalkozas=1]];
If[talalkozas==1,talalkozasok=talalkozasok~Join ~{i},talalkozasok=talalkozasok~Join ~{"nem"} ],{k}];

Sort[talalkozasok]

Length[Select[talalkozasok,#<100000&]]

G(∞)-en 500 bolyongáspárból 345 találkozott az első 50000 lépésben, ebből 292 már 100 lépésen belül, és csak 8 olyan volt, amely nem találkozott az első 5000 lépésben, de további 45000 lépés alatt már igen. Ezért megállapítható, hogy n növekedtével (néhány ezertől kezdve) nem nő jelentősen a találkozó séták száma, tehát két séta pozitív valószínűséggel nem találkozik (a szimulációból 0,69-es közelítés adódik a találkozás valószínűségére).
Arra az állításra, hogy G(∞)-en két független bolyongás pozitív valószínűséggel nem találkozik, azaz (ezzel ekvivalens), hogy 1 valószínűséggel csak véges sokszor találkoznak, ad bizonyítást M. Krishnapur és Y. Peres egy 2004-es cikke [2].

G(2)-n 1000 bolyongáspárból 937 találkozott az első 100000 lépésben, ebből 917 az első 10000-ben, 932 az első 25000-ben és 935 az első 50000-ben. Tehát itt 1-hez már közel van a találkozás valószínűsége, de a szimuláció alapján még nem éri el az 1-et, mert n növekedtével már ahhoz túl lassan nő a találkozó bolyongáspárok száma.
G(1.5)-en 1000 bolyongáspárból 961 találkozott az első 100000 lépésben, ebből 949 az első 10000-ben, 954 az első 25000-ben és 958 az első 50000-ben. A korábban említett megfontolások alapján itt is (már kisebb biztossággal, de) megállapítható, hogy kisebb 1-nél a találkozás valószínűsége.
G(1)-en 1000 bolyongáspárból 989 találkozott az első 100000 lépésben, ebből 978 az első 10000-ben, 984 az első 25000-ben és 988 az első 50000-ben. Itt már ez alapján nehéz megbecsülni, hogy a találkozás valószínűsége kisebb-e 1-nél. Valójában az α=1 a kritikus eset.
G(0.5)-en 1000 bolyongáspárból 996 találkozott az első 100000 lépésben. Ez alapján állítható, hogy itt 1 a találkozás valószínűsége.
G(1/3)-on 1000 bolyongáspárból 995 találkozott 100000 lépésen belül. Itt is 1 a találkozás valószínűsége.

M. T. Barlow, Y. Peres és P. Sousi friss eredménye ([3]), hogy valóban a fent leírtak igazak, azaz G(α)-n α>1 esetén pozitív valószínűséggel nem találkoznak (azaz 1 valószínűséggel csak véges sokszor találkoznak; a gráf rendelkezik a "véges sok találkozás" tulajdonságával), α≤1 esetén pedig 1 valószínűséggel találkoznak (azaz 1 valószínűséggel végtelen sokszor találkoznak).

A találkozások számának eloszlása

Egy bolyongáspár találkozásai számának eloszlását próbáljuk meg közelíteni. Megvizsgáljuk, hogy mi az eloszlás (súlyfüggvény) az első m lépést tekintve, egyre nagyobb m-eket nézve. (A G(∞), G(2) és G(1/2) gráfokat vizsgáljuk, m értéke rendre 500, 1000 és 2000 mindhárom esetben.)

G(∞)-en:

ClearAll[n,k,setak1,setak2,talalkozasok];
n=2000;
k=1000;
setak1=Array[NestList[RandomChoice[szomszedok[#]]&,RandomChoice[szomszedok[{0,0}]],n-1]&,k];
setak2=Array[NestList[RandomChoice[szomszedok[#]]&,RandomChoice[szomszedok[{0,0}]],n-1]&,k];
talalkozasok=Array[Position[setak1[[#]]-setak2[[#]],{0,0}]&,k];

ClearAll[m,talalkozasokmig];
talalkozasokmig[m_]:=Array[Select[talalkozasok[[#]],#[[1]]≤m&]&,k];
Row[Table[DiscretePlot[Length[Select[talalkozasokmig[m],Length[#]==x&]]/k,{x,100},Joined->True,ImageSize->Medium,PlotRange->{0,0.15}],{m,{500,1000,2000}}]]

G(2)-n:

ClearAll[n,k,α,setak1,setak2,talalkozasok];
α=2;
n=2000;
k=1000;
setak1=Array[NestList[RandomChoice[szomszedok[#,α]]&,RandomChoice[szomszedok[{0,0},α]],n-1]&,k];
setak2=Array[NestList[RandomChoice[szomszedok[#,α]]&,RandomChoice[szomszedok[{0,0},α]],n-1]&,k];
talalkozasok=Array[Position[setak1[[#]]-setak2[[#]],{0,0}]&,k];

ClearAll[m,talalkozasokmig];
talalkozasokmig[m_]:=Array[Select[talalkozasok[[#]],#[[1]]≤m&]&,k];
Row[Table[DiscretePlot[Length[Select[talalkozasokmig[m],Length[#]==x&]]/k,{x,100},Joined->True,ImageSize->Medium,PlotRange->{0,0.15}],{m,{500,1000,2000}}]]

G(1/2)-en:

ClearAll[n,k,α,setak1,setak2,talalkozasok];
α=0.5;
n=2000;
k=1000;
setak1=Array[NestList[RandomChoice[szomszedok[#,α]]&,RandomChoice[szomszedok[{0,0},α]],n-1]&,k];
setak2=Array[NestList[RandomChoice[szomszedok[#,α]]&,RandomChoice[szomszedok[{0,0},α]],n-1]&,k];
talalkozasok=Array[Position[setak1[[#]]-setak2[[#]],{0,0}]&,k];

ClearAll[m,talalkozasokmig];
talalkozasokmig[m_]:=Array[Select[talalkozasok[[#]],#[[1]]≤m&]&,k];
Row[Table[DiscretePlot[Length[Select[talalkozasokmig[m],Length[#]==x&]]/k,{x,100},Joined->True,ImageSize->Medium,PlotRange->{0,0.15}],{m,{500,1000,2000}}]]

Megfigyelhető a különbség az első kettő és a harmadik eset között. Az előbbiek esetén m növekedtével kevés változás látható, ezért ez egy jó közelítése a végtelen séták találkozásszám-eloszlásának. Tehát a végtelen sétáknál is a kis értékeken (azaz a kevés találkozáson) lesz nagy súly, utána a súlyfüggvény lecseng. (A találkozások számának várható értéke azonban végtelen lesz, ez a gráf rekurrenciájából következik, lásd a [2] cikket.) G(1/2) esetében azonban m növelésével egyre egyenletesebbé válik az eloszlás, a súly egyre inkább szétoszlik a számegyenesen. Innen sejthető, hogy a végtelen séták végtelen sokszor fognak találkozni.

Összefoglalás

A dolgozat első részében (Z^d)-n történő egyszerű szimmetrikus bolyongásokat vizsgáltunk. Megállapítottuk a minőségi különbséget az 1, 2, illetve a 3 dimenziós eset között (rekurrencia-tranziencia, séta alakja, visszatérések számának eloszlása milyen gyorsan konvergál), vizsgáltuk az origóba való visszatérés idejét, a visszatérések számának eloszlását, az origótól való maximális és végső távolságot egy adott lépésig. A második részben speciális "fésű-gráfokon" való bolyongáspárokat vizsgáltunk abból a szempontból, hogy mely gráfokon találkoznak 1-nél kisebb valószínűséggel, hogyan alakul a találkozásaik számának eloszlása. Ez alapján megpróbáltuk elhatárolni ezen gráfok két csoportját.

További lehetőségek

Nem csak a Z gráf csúcsaihoz lehet hozzáragasztani más gráfokat, hanem tetszőleges rerekurrens G gráf minden csúcsához ugyanazt a rekurrens H gráfot (mindig ugyanannál a csúcsánál fogva). Ennek jelölése a szakirodalomban (Subscript[Comb, v])(G,H), aminek a csúcshalmaza tehát V(G)×V(H), az élhalmaza {{(x,w),(x,z)}:{w,z}∈E(H),x∈V(G)}⋃{{(x,v),(y,v)}:{x,y}∈E(G)}, ahol V(G) a G gráf csúcshalmaza, E(G) az élhalmaza, v∈V(H) adott csúcs (a gráfok itt mindig összefüggőek). A fenti G(∞) például (Subscript[Comb, 0])(Z,Z). Könnyen látható, hogy rekurrens G, H gráfokra (Subscript[Comb, v])(G,H) is rekurrens. Vizsgálható, hogy ha G és H végtelen gráfok, akkor mikor fog (Subscript[Comb, v])(G,H) rendelkezni a véges sok találkozás tulajdonságával. Tetszőleges G mellett H=Z és H=(Z^2) esetre bizonyítást ad M. Krishnapur és Y. Peres cikke, majd felveti a kérdést, hogy igaz-e bármilyen végtelen G és H rekurrens gráfokra. O. Gurel-Gurevich és A. Nachmias egy cikkében ([4]) mutat egy olyan (a fenitieknek megfelelő) H gráfot (és v∈V(H) csúcsot), amelyre (Subscript[Comb, v])(Z,H) nem rendelkezik a véges sok találkozás tulajdonságával.

Másik lehetőség annak a vizsgálata, hogy a fenti G(α) gráfok mintájára Z helyett (Z^2) csúcsaihoz csatlakoztatunk véges hosszú szakaszokat, amelyek hosszát egy f(x,y) függyvény írja le ((x,y)∈(Z^2)). Nyitott kérdés, hogy ez milyen f függvényekre fog rendelkezni a véges sok találkozás tulajdonságával. M. T. Barlow, Y. Peres és P. Sousi cikke alapján biztosan nem, ha f növekedése logaritmikus.

Irodalomjegyzék

[1] William Feller: An Introduction to Probability Theory and Its Applications

[2]

Hyperlink["M. Krishnapur, Y. Peres: Recurrent graphs where two independent random walks collide finitely often", "http://www.emis.de/journals/EJP-ECP/_ejpecp/ECP/include/getdocef94.pdf"]

[3]

Hyperlink["M. T. Barlow, Y. Peres, P. Sousi: Collisions of Random Walks", "http://arxiv.org/PS_cache/arxiv/pdf/1003/1003.3255v1.pdf"]

[4]

Hyperlink["O. Gurel-Gurevich, A. Nachmias: Non-concentration of Return Times","http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.1438v1.pdf"]

Eredmények

Hyperlink["eredmények","http://www.math.bme.hu/~barthazs/BarthaZsolt.nb"]