Véletlenszerű séta

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. október 6-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A véletlenszerű séta egy sztochasztikus vagy véletlenszerű folyamatként ismert matematikai objektum, amely véletlenszerű lépések sorozatából álló útvonalat ír le valamilyen matematikai térben (például egész számok halmazán ).

A véletlenszerű séta legegyszerűbb példája az egész számok számegyenese mentén történő véletlenszerű séta, , amely a 0 pontból kezdődik, és minden lépésben egyenlő valószínűséggel eltolódik +1-gyel vagy -1-gyel . További példák a molekula pályája folyadékban vagy gázban ( Brown-mozgás ), az állatok útkeresése táplálékkeresés közben , a részvényárfolyamok ingadozása a tőzsdén , egy játékos pénzügyi helyzete : az összes leírt eset véletlenszerű sétával közelíthető. modellek, még akkor is, ha a való életben nem teljesen véletlenszerűek. $\mathbb {Z}$

Amint a példákból látható, a véletlenszerű séta modellt a mérnöki tudományokban és számos tudományterületen használják, beleértve az ökológiát, pszichológiát, számítástechnikát, fizikát, kémiát, biológiát, közgazdaságtant és szociológiát. A véletlenszerű séta megmagyarázza számos folyamat megfigyelt viselkedését ezekben a régiókban, és így alapvető modellként szolgál a rögzített sztochasztikus aktivitáshoz. Tehát a matematikában a π értéke véletlenszerű sétával és ágens-alapú modellezéssel közelíthető. [1] [2] A véletlenszerű séta fogalmát először Karl Pearson vezette be 1905-ben. [3]

A véletlenszerű séták különféle fajtái érdekesek lehetnek. Maga a kifejezés leggyakrabban a Markov-láncok vagy Markov-folyamatok egy speciális kategóriájára utal, sok időfüggő folyamatot pedig véletlenszerű sétaként emlegetnek, a speciális tulajdonságait jelző módosítóval. Véletlenszerű séták (Markov vagy nem) is előfordulhatnak számos területen: az általánosan tanulmányozottak közé tartoznak a gráfok , az egész számok vagy valós számsorok , a vektorterek , a görbe felületek, a többdimenziós Riemann-sokaságok és a véges , végesen generált csoportok, a Lie-csoportok . Az időparaméter is eltérő lehet. A legegyszerűbb esetben a séta diszkrét időben megy végbe, és valószínűségi változók sorozata ( X
t) = ( X
egy, X
2, ...) , természetes számokkal indexelve. Vannak azonban véletlenszerű séták is, amelyekben a lépések tetszőleges időpillanatban történnek, és ebben az esetben az X pozíció
tminden t ∈ [0,+∞) időre meg kell határozni . A véletlenszerű séta speciális esetei a Levy repülési és diffúziós modellek , mint például a Brown-mozgás .

A véletlenszerű séta a Markov-folyamat megvitatásának alapvető témája, és matematikai tanulmányozása nagyon kiterjedt.

Véletlenszerű séta rácson

A véletlenszerű séta jól ismert modellje a szabályos rácson való séta, ahol minden lépésnél a helyszín egy bizonyos valószínűségi eloszlásnak megfelelően más-más pontra kerül.

Egy egyszerű véletlenszerű séta során egy hely csak a szomszédos rácspontokra mozoghat, és egy rács útvonalat alkot. Egy lokálisan korlátos rácson végzett egyszerű szimmetrikus véletlenszerű séta során annak a valószínűsége, hogy egy pont minden közvetlen szomszédjába kerül, egyenlő. A legjobban tanulmányozott példa a véletlenszerű séta egész számok d - dimenziós rácsán (ezt néha hiperköbös rácsnak nevezik) . [négy] ${\displaystyle \mathbb {Z} ^{d))$

Ha az állapottér véges számú dimenzióra korlátozódik, akkor egy ilyen véletlenszerű sétamodellt egyszerű korlátos szimmetrikus véletlenszerű sétának nevezünk , és az átmenet valószínűsége a pont helyétől függ, mivel a mozgás a határ- és sarokpontokon korlátozott. . [5]

Egydimenziós véletlenszerű séta

A véletlenszerű séta legegyszerűbb példája egy véletlenszerű séta az egész számok számegyenesen , , amely a 0 pontból indul, és minden lépésben egyenlő valószínűséggel +1 vagy -1 mozog. $\mathbb {Z}$

Ezt a vándorlást a következőképpen szemléltethetjük. A jelet a számegyenes nullára helyezik, és egy "tisztességes" érmét dobnak fel. Ha fejjel jön fel, a címke egy egységgel jobbra, ha pedig farokkal lép fel, akkor egy egységgel balra. Öt dobás után a pont -5, -3, -1, 1, 3, 5 lehet. Öt dobásnál, beleértve három fejet és két farkot, bármilyen sorrendben, a pont 1 lesz. 10 módja van. az 1. pont eléréséhez (három fej és két farok gurításával), 10 mód a −1 ponthoz (három farok és két fej), 5 módja a 3. pont elérésének (négy fej) és egy "farok" 5 módjai a -3 ponthoz (négy "farok" és egy "sas"), 1 mód az 5-ös ponthoz (öt "fej") és 1 mód a -5 ponthoz (öt "farok"). ") . Az öt dobás lehetséges kimenetelét az alábbiakban szemléltetjük.

Ennek a lépésnek a formális meghatározásához független valószínűségi változókat veszünk , ahol minden változó 1 vagy -1, 50%-os valószínűséggel minden értékre, a halmazt és a sorozatot egyszerű véletlenszerű séta - nak nevezzük . Ez a sorozat (a −1 és 1 sorozat összege) a megtett távolságot jelenti, ha a séta minden egyes szakaszának hossza eggyel egyenlő. A sorozat matematikai elvárása nulla. Ez azt jelenti, hogy az összes érmefeldobás átlagértéke a feldobások számának növekedésével nulla felé tart. Ez a várakozás véges additív tulajdonságából következik: $Z_{1},Z_{2},\dots$ $S_{0}=0\,\!$ $S_{n}=\sum _{j=1}^{n}Z_{j}.$ $\{S_{n}\}\,\!$ $\mathbb {Z}$ $E(S_{n})\,\!$ $S_{n}\,\!$

E(S_{n})=\sum _{j=1}^{n}E(Z_{j})=0.

Hasonlóan érvelve használjuk a valószínűségi változók függetlenségét és azt a tényt, hogy , látjuk: $E(Z_{n}^{2})=1$

E(S_{n}^{2})=\sum _{i=1}^{n}E(Z_{i}^{2})+2\sum _{1\leq i<j \leq n}E(Z_{i}Z_{j})=n.

Ez egyértelművé teszi, hogy n lépés megtétele után a várható távolságnak a nagyságrendűnek kell lennie . Valójában [6] $E(|S_{n}|)\,\!$ ${\sqrt n}$

\lim _{n\to \infty }{\frac {E(|S_{n}|)}{\sqrt {n}}}={\sqrt {\frac {2}{\pi }} }.

Hányszor lépi át a véletlenszerű séta a határt, ha korlátlan ideig lehet vándorolni? A legegyszerűbb véletlenszerű séta végtelen számú alkalommal metszi az egyes pontokat. Az így létrejövő effektusnak több neve is van: a szintátlépés jelensége , ismétlődése vagy a játékos tönkretétele . Az utolsó eset elnevezésének oka a következő: a véges pénzösszegű játékos előbb-utóbb veszít, ha fair játékot játszik egy korlátlan pénzösszegű pot ellen. A játékos pénze egy véletlenszerű séta, és egy bizonyos időpontban eléri a nullát, és a játéknak vége lesz. $\mathbb {Z}$

Legyenek a és b pozitív egészek, akkor a lépések várható száma, amikor egy egyszerű, 0-tól kezdődő egydimenziós véletlenszerű séta először eléri a b -t vagy −a értéket ab . Annak a valószínűsége, hogy egy adott séta eléri a b -t, mielőtt elérné az −a -t , az , ami abból következik, hogy egy egyszerű véletlenszerű séta martingál . $a/(a+b)$

A fent említett eredmények egy része a Pascal-háromszög tulajdonságaiból származtatható . Az n feletti összes különálló séták száma

lépések, ahol minden lépés +1 vagy -1 egyenlő 2 n . Egy egyszerű véletlenszerű séta esetén ezen lépések mindegyike egyenértékű. A k szám egyenlőségéhez szükséges és elegendő, hogy a lépések száma +1-gyel haladja meg a lépések számát k számmal -1-gyel . Ezért a +1-re lépésnek (n + k)/2 - szer kell történnie n séta között, ezért a feltételt kielégítő séták száma megegyezik az (n + k)/2 elem kiválasztásának lehetőségeivel. n elemű halmaz. [7] Ezt jelöli: . Ahhoz, hogy ez a kifejezés értelme legyen, szükséges, hogy az n + k összeg páros szám legyen, ami azt jelenti, hogy az n és a k számoknak egyszerre párosnak vagy páratlannak kell lenniük. Ezért az a valószínűség, amely egyenlő lesz : Pascal-háromszög bejegyzéseit faktoriálisokkal ábrázolva és Stirling képletét használva , jó becsléseket kaphatunk ezekre a valószínűségekre . $S_{n}\,\!$ $S_{n}=k$ $n \choose (n+k)/2$ $S_{n}=k$ ${\displaystyle 2^{-n}{n \choose (n+k)/2))$ $n$

Ha a hely a + jelre korlátozódik a rövidség kedvéért, akkor a véletlenszerű séta öt lépés után egy bizonyos számnál megállja a következőt: 0,5,0,4,0,1}. $\mathbb {Z}$

Mutassuk meg ezt a megfelelést a Pascal-háromszögnek n kis értékeire . A nulla lépésnél az egyetlen lehetőség a nullán maradás. Azonban már az első lépésnél lehetőség van arra, hogy -1-re vagy 1-re kerüljön. A második lépésnél 1-ről a 2-es pontra vagy vissza a nullára léphet. -1-ről -2-re vagy vissza nullára léphet. Ezért van egy eset, amikor a −2 pontban, két esetben nullán, és egy esetben a 2. pontban vagyunk.

k	−5	−4	−3	−2	−1	0	egy	2	3	négy	5
$P[S_{0}=k]$						egy
$2P[S_{1}=k]$					egy		egy
$2^{2}P[S_{2}=k]$				egy		2		egy
$2^{3}P[S_{3}=k]$			egy		3		3		egy
$2^{4}P[S_{4}=k]$		egy		négy		6		négy		egy
$2^{5}P[S_{5}=k]$	egy		5		tíz		tíz		5		egy

A centrális határtétel és az iterált logaritmus törvénye egy egyszerű véletlenszerű séta viselkedésének fontos aspektusait írja le . Különösen, ha n növekszik, a valószínűségek (az egyes sorban lévő számok arányában) normális eloszlás felé hajlanak . $\mathbb {Z}$

A kristályrácsokon való véletlenszerű séták (véges gráfok végtelen számú Abeli-féle fedőgráfja) közvetlen általánosításnak tekinthetők. Valójában ilyen feltételek mellett még a centrális határtétel és a nagy eltérés tétele is érvényesíthető. [8] [9]

Mint egy Markov-lánc

Az egydimenziós diszkrét véletlenszerű séta egy egész állapotú Markov-lánc, amelynek kezdeti eloszlását a valószínűségi változó valószínűségi függvénye adja meg , az átmenet valószínűségi mátrixa pedig $X_{0}$

P\equiv (p_{{ij}})_{{i,j\in {\mathbb {Z}}}}=\left({\begin{mátrix}\ddots &\ddots &\ddots &\\&q_ {{-1}}&0&p_{{-1}}&\\&&q_{0}&0&p_{0}\\&&&q_{1}&0&p_{1}\\&&&&\ddots &\ddots &\ddots \end{mátrix} }\jobb)

vagyis

p_{{i,i+1}}\equiv {\mathbb {P}}(X_{{n+1}}=i+1\mid X_{n}=i)=p_{i},

p_{{i,i-1}}\equiv {\mathbb {P}}(X_{{n+1}}=i-1\mid X_{n}=i)=q_{i},\quad i \in {\mathbb {Z}),

p_{{ij}}\equiv {\mathbb {P}}(X_{{n+1}}=j\mid X_{n}=i)=0,\quad |ij|\not =1.

Megemelt méretek

Magasabb méretekben a véletlenszerű sétapontok halmaza meglehetősen érdekes geometriai tulajdonságokkal rendelkezik. Valójában egy diszkrét fraktált kapunk , vagyis egy olyan halmazt, amely nagyításkor sztochasztikus önhasonlóságot mutat . Kis léptékben megfigyelheti a "szaggatottságot" azon a rácson, amelyen a séta történik. Lawler két idézett könyve jó anyagforrás a témában. A véletlenszerű séta pályája a meglátogatott pontok gyűjteménye, amelyet úgy tekintenek, mint egy elrendezést arra az időpontra, amikor a séta elérte a pontot. Az egyik dimenzióban a pálya egyszerűen az összes pont a minimális magasság és a maximális magasság között, amelyet a vándor elért (mindkettő átlagosan . nagyságrendű ). ${\sqrt {n}}$

Egy kétdimenziós eset megjelenítéséhez elképzelhetünk egy személyt, aki véletlenszerűen sétál a városban. Ez a város gyakorlatilag végtelen, és a járdák négyzetrácsában terül el. Minden kereszteződésben egy személy véletlenszerűen választ egyet a négy lehetséges útvonal közül (beleértve azt is, ahonnan jött). Formálisan ez egy véletlenszerű séta a sík összes pontjának halmazán egész koordinátákkal .

Vajon ez az ember visszatér valaha a vándorlás kiindulópontjához? Ez az eset a fent tárgyalt szintbeli kereszteződési probléma 2D megfelelője. 1921-ben Pólya György bebizonyította, hogy egy kétdimenziós véletlenszerű séta esetén az ember szinte biztosan visszatér, de három vagy több dimenzió esetén a visszatérés valószínűsége a dimenziók számának növekedésével csökken. A háromdimenziós esetben a valószínűség körülbelül 34%-ra csökken. [10] Shizuo Kakutani matematikus híres erről az eredményről szóló idézetéről: "A részeg előbb-utóbb hazatalál, de egy részeg madár örökre elveszhet." [tizenegy]

Ennek a kérdésnek egy másik változata, amelyet Poya is feltett: ha két ember elhagyja ugyanazt a kiindulópontot, találkoznak-e valaha? [12] Elképzelhető, hogy a helyük közötti különbség (két független véletlenszerű séta) is egy egyszerű véletlenszerű séta, tehát szinte biztosan találkoznak majd egy kétdimenziós séta során, de három vagy több dimenzió esetén a visszatérési valószínűség a ugyanaz, mint az előző esetben, csökken a mérések számának növekedésével. Erdős Pal és Samuel James Taylor 1960-ban azt is kimutatta, hogy 4-nél kisebb vagy azzal egyenlő dimenziók esetén két független véletlenszerű séta bármely két pontból kiindulva szinte biztosan végtelen sok metszésponttal rendelkezik, de 5-nél nagyobb méreteknél szinte biztosan. csak véges számú alkalommal metszik egymást. [13]

A 2D véletlenszerű séta aszimptotikus függvényét a lépések számának növekedésével a Rayleigh-eloszlás adja meg . A valószínűségi eloszlás az origótól számított sugár függvénye, és minden lépésnél a lépés hossza állandó.

P(r)={\frac {2r}{N}}e^{-r^{2}/N}

A Wiener-folyamathoz való viszony

A Wiener-folyamat egy sztochasztikus folyamat, amely viselkedésében hasonló a Brown-mozgáshoz , a kis részecskék folyadékban való diffúziójának fizikai jelenségéhez. (Néha egy Wiener-folyamatot Brown-mozgásnak neveznek, bár szigorúan véve a Wiener-folyamat modell, a Brown-mozgás pedig modellezett jelenség.)

A Wiener-folyamat az egydimenziós véletlenszerű séta méretezhető határa . Ez azt jelenti, hogy ha véletlenszerűen sétálunk nagyon kis lépésekkel, akkor közelítést kaphatunk a Wiener-folyamathoz (és kisebb pontossággal a Brown-mozgáshoz). Pontosabban, ha a lépés hossza ε, akkor L /ε 2 hosszúságú sétát kell tenni az L Wiener út közelítéséhez . Ahogy a lépéshossz közeledik a nullához (és a lépések száma arányosan növekszik), a véletlenszerű séta megfelelő értelemben lefedi a Wiener-folyamatot. Formálisan, ha B az összes L hosszúságú út tere a maximális topológiával, és ha M a mértékek tere B felett normál topológiával, akkor a konvergencia az M térben van . Analógia alapján a Wiener-folyamat több dimenzióban a skálázható határa egy véletlenszerű séta azonos számú dimenzióban.

A véletlenszerű séta egy diszkrét fraktál (egy egész számú dimenziójú függvény; 1, 2, ...), míg a Wiener-folyamat pályája egy valódi fraktál, és a kettő között van bizonyos kapcsolat. Például tegyünk egy véletlenszerű sétát, és addig "sétálunk", amíg el nem haladunk a lépés hosszának r -szeres sugarú körén. Ekkor a séta teljesítéséhez szükséges lépések átlagos száma r 2 lesz . Ez a tény annak a ténynek a diszkrét változata , hogy a Wiener-folyamat séta a Hausdorff 2-es dimenzió fraktálja .

A kétdimenziós térben a pontok átlagos száma, amelyen egy véletlenszerű séta elhalad a pályája határán , r 4/3 . Ez összhangban van azzal a ténnyel, hogy a Wiener-folyamat pályahatára 4/3-os fraktál, amit Mandelbrot javasolt szimulációk segítségével, de Lawler, Schramm és Werner csak 2000-ben bizonyította . [tizennégy]

A Wiener-folyamatnak sok szimmetriája van, ellentétben a véletlenszerű sétával. Például egy Wiener-folyamat forgásinvariáns, a véletlenszerű séta viszont nem, mert a rácsja nem forgásinvariáns (a véletlenszerű séta 90 fokkal forgásinvariáns, míg a Wiener-folyamatok, mondjuk, további 17 fokkal forgásinvariáns). ). Ez azt jelenti, hogy sok esetben a véletlenszerű séta során adott feladatok könnyebben megoldhatók a következő módon: a problémát átvisszük a Wiener folyamatba, ott megoldjuk, majd visszavisszük. Másrészt néhány probléma könnyebben megoldható egy véletlenszerű séta során, annak diszkrét jellege miatt.

A véletlenszerű séta egy Wiener-folyamathoz való konvergenciája a központi határérték-tétel és a Donsker-tétel segítségével történik. A t = 0- nál ismert rögzített pozíciójú részecskére a centrális határtétel azt mondja, hogy nagyszámú független véletlenszerű sétalépés után a vándor pozíciója a normál variancia -eloszlás szerint oszlik el :

\sigma ^{2}={\frac {t}{\delta t}}\,\varepsilon ^{2},

ahol t a véletlenszerű séta kezdete óta eltelt idő, a séta lépésnagysága és a két egymást követő lépés között eltelt idő. $\varepsilon$ $\delta t$

Ez az eset megfelel a Wiener-folyamatot leíró diffúziós egyenlet Green függvényének , ami arra utal, hogy kellően sok lépés után a véletlenszerű séta a Wiener-folyamathoz konvergál.

3D-s esetben a diffúziós egyenlet Green függvényének megfelelő variancia:

\sigma ^{2}=6\,D\,t.

Kiegyenlítve ezt az értéket a véletlenszerű sétáló helyzetéhez kapcsolódó varianciával, megkaphatjuk az ekvivalens diffúziós együtthatót egy aszimptotikus Wiener-folyamathoz, amelyhez a véletlenszerű séta kellően sok lépés után konvergál:

D={\frac {\varepsilon ^{2}}{6\delta t}}

(csak három dimenzió esetén van értelme).

Megjegyzés: A fenti két varianciakifejezés egy olyan vektorhoz társított eloszlásnak felel meg, amely egy véletlenszerű séta két végét három dimenzióban köti össze. Az egyes komponensekhez tartozó különbség, vagy csak a teljes érték egyharmada (még mindig 3D). $\vec R$ $R_{x}$ $R_{y}$ $R_{z}$

2D esetén: [15]

D={\frac {\varepsilon ^{2}}{4\delta t}}.

1D esetén: [16]

D={\frac {\varepsilon ^{2}}{2\delta t}}.

Donsker-tétel

Vegyünk egy véletlenszerű sétát , ahol . $Y_{n}=\sum \limits _{{i=1}}^{{n}}{X_{i}}$ $EX_{i}=0,DX_{i}=\sigma ^{2}<\infty$

A centrális határeloszlás tétele kimondja, hogy a -nál való eloszlással . ${\frac {Y_{n}}{\sigma {\sqrt {n}}}}\rightarrow N(0,1)$ $n\jobbra nyíl\infty$

A véletlenszerű séták esetében azonban ez az állítás jelentősen megerősíthető.

Véletlenszerű folyamatot készítünk a vonatkozásban , a következőképpen definiálva: , a többire pedig lineáris folytatással definiáljuk a folyamatot: $Y_{n}$ $S_{n}(t),t\in [0,1]$ $S_{n}\left({\frac {k}{n}}\right)={\frac {Y_{{k}}}{\sigma {\sqrt {n}}}}$ $t$

$S_{n}(t)=(k+1-nt)S_{n}\left({\frac {k}{n}}\right)+(nt-k)S_{n}\left({\ frac {k+1}{n}}\jobbra),t\in \left({\frac {k}{n));{\frac {k+1}{n}}\jobbra)$

Az eloszlásra vonatkozó központi határérték tételből $\forall t$ $S_{n}(t)\rightarrow N(0,t)$ $n\jobbra nyíl\infty$

Ez a folyamat egydimenziós eloszlásának konvergenciáját jelenti a Wiener-folyamat egydimenziós eloszlásaihoz . Az invariancia elvének is nevezett Donsker-tétel kimondja, hogy a folyamatok gyenge konvergenciája van, $S_{n}(t)$ $S_{n}(t)\jobbra nyíl W(t),n\jobbra \infty$

A folyamatok gyenge konvergenciája a Wiener-mértékhez képest folytonos függvények konvergenciáját jelenti, azaz lehetővé teszi a függvények értékeinek kiszámítását Brown-mozgásból (például maximum, minimum, utolsó nulla, első elérés pillanata). a szint és egyebek) egyszerű véletlenszerű séta során a határértékre való átlépéssel.

Gauss véletlenszerű séta

A normál eloszlástól függően változó lépéshosszú véletlenszerű séta valós világbeli idősoradatként, például pénzügyi piacokként használatos. A Black-Schools képlet például egy Gauss-féle véletlenszerű sétát használ alapfeltevésként.

Ebben az esetben a lépésméret az inverz kumulatív normális eloszlás, ahol 0 ≤ z ≤ 1, és egy egyenletes eloszlású véletlenszám, μ és σ pedig a normális eloszlás átlaga és szórása. $\Phi ^{-1}(z,\mu ,\sigma )$

Ha μ nem nulla, a véletlenszerű séta lineáris trendet fog követni. Ha v s a véletlenszerű séta kezdeti értéke, akkor az n lépés után várható érték v s + n μ.

Abban a speciális esetben, amikor μ nulla, n lépés után a megtett távolság valószínűségi eloszlását N (0, n σ 2 ) definiáljuk, ahol N () a normális eloszlás jelölése, n a lépések száma , és σ a fenti inverz kumulatív normális eloszlásból származik.

Bizonyítás: A Gauss-féle véletlenszerű séta független és azonos eloszlású valószínűségi változók sorozatának összegeként ábrázolható, X i egy inverz kumulatív normális eloszlásból, ahol az átlag nulla, a σ pedig az eredeti inverz kumulatív normális eloszlásból származik:

Z = ,

\sum _{i=0}^{n}{X_{i))

de van egy eloszlásunk két független normális eloszlású valószínűségi változó összegére, Z = X + Y, amelyet a

\mathcal{N}

(μ X + μ Y , σ 2 X + σ 2 Y )

Esetünkben μ X = μ Y = 0 és σ 2 X = σ 2 Y = σ 2 adják:

\mathcal{N}

(0, 2σ 2 )

Indukcióval n lépésre a következőket kapjuk:

Z ~ (0, n σ 2 ).

\mathcal{N}

A nulla átlaggal és véges szórással (nem feltétlenül csak normál eloszlású) bármely eloszlás szerint elosztott lépések esetén az n lépés után megtett távolság négyzetes középértéke a következőképpen adódik:

{\sqrt {E|S_{n}^{2}|}}=\sigma {\sqrt {n)).

De egy Gauss-féle véletlenszerű séta esetén ez csak az n lépés után megtett távolság eloszlásának szórása . Ezért, ha μ nulla, és ha a megtett effektív távolság egy szórás, akkor 68,27% az esély arra, hogy az n lépés után megtett effektív távolság ± σ között lesz . Ezenkívül 50% az esélye annak, hogy az n lépés után megtett távolság ± 0,6745σ között lesz . ${\sqrt {n}}$ ${\sqrt {n}}$

Rendellenes diffúzió

A rendezetlen rendszerekben, például porózus közegekben és fraktálokban ez nem -vel , hanem -vel arányos lehet . A kitevőt anomáliás diffúziós kitevőnek nevezzük, és lehet nagyobb vagy kisebb, mint 2. [17] Az anomális diffúziót σ r 2 ~ Dt α alakban is kifejezhetjük, ahol α az anomália paramétere. Egyes véletlenszerű környezetben előforduló diffúziók még az idő logaritmusának erejével is arányosak, mint például Sinai járása vagy Brox diffúziója. $\sigma ^{2}$ $t$ $t^{2/d_{w))$ $d_{w}$

Különböző helyek száma

Az egyetlen véletlenszerű sétáló által meglátogatott különálló helyek számát alaposan tanulmányozták négyzetes és köbös rácsok és fraktálok esetében. [18] [19] Ez az érték a holtpontok (angolul trapping ) és a kinetikus reakciók problémáinak elemzéséhez hasznos . Összefügg továbbá az állapotok rezgéssűrűségével, [20] [21] a folyamatok diffúziós reakcióival [22] és a populációk eloszlásával az ökológiában. [23] [24] Nemrég tanulmányozták d - dimenziós euklideszi rácsok esetében ennek a problémának a véletlenszerű sétálók által meglátogatott különálló helyeinek számát . [25] Az N sétálók által meglátogatott különböző helyek száma nem egyszerűen az egyes sétálók által meglátogatott helyek számával függ össze. $Utca)$ $N$ $S_{N}(t)$

Az információ mennyiségének becslése

Egy Gauss-féle véletlenszerű séta információmennyiségének becslése a hibatávolság négyzetéhez, azaz a másodfokú torzítási függvényéhez, paraméteresen megadva: [26]

R(D_{\theta })={\frac {1}{2}}\int _{0}^{1}\max\{0,\log _{2}\left(S(\) varphi )/\theta \right)\}\,d\varphi ,

D_{\theta }=\int _{0}^{1}\min\{S(\varphi ),\theta \}\,d\varphi ,

ahol . Ezért nem lehetséges a bináris kódolás a bitszámnál kevesebb bittel, majd a dekódolás a várható RMS hibával, amely kisebb, mint . Másrészt, bármely -hez van egy kellően nagy és bináris kód, amely legfeljebb elemet tartalmazhat, így a várható átlagos négyzetes hiba a kódból való helyreállításkor legfeljebb . ${\displaystyle S(\varphi )=\left(2\sin(\pi \varphi /2)\right)^{-2))$ ${\{Z_{n}\}_{n=1}^{N))$ $NR(D_{\theta })$ $D_{\theta }$ $\varepsilon >0$ $N\in \mathbb {N}$ ${\displaystyle 2^{NR(D_{\theta )))))$ ${\{Z_{n}\}_{n=1}^{N))$ $D_{\theta }-\varepsilon$

Alkalmazások

Amint már említettük, jelentős azoknak a természeti jelenségeknek a köre, amelyeket a véletlenszerű séták egyes fajtái megpróbáltak leírni. Különösen a fizikában, [27] [28] a kémiában, [29] az anyagtudományban , [30] [31] a biológiában [32] és más különféle tudományokban. [33] [34] Íme a véletlenszerű séta néhány alkalmazása:

A pénzügyi közgazdaságtanban a "véletlenszerű séta hipotézist" használják a részvényárak és más tényezők modellezésére. Az empirikus vizsgálatok azonban eltéréseket találtak az elméleti modellel szemben, különösen a rövid és hosszú távú kapcsolatokban.
A populációgenetikában a véletlenszerű séta a genetikai sodródás statisztikai tulajdonságait írja le .
A fizikában a véletlenszerű sétákat a Brown-mozgás és diffúzió egyszerűsített modelljeként használják, például a molekulák véletlenszerű mozgását folyadékokban és gázokban. Például diffúzan korlátozott aggregáció. A kvantumtérelméletben a fizikában is fontos szerepet töltenek be a véletlenszerű séták és néhány önkölcsönhatásba lépő séta .
A matematikai ökológiában véletlenszerű sétákat használnak az állatok egyéni mozgásának leírására, a biológiai diffúziós folyamatok empirikus támogatására, és néha a populációdinamika modellezésére .
A polimerfizikában a véletlenszerű séta ideális láncot ír le, a polimerek tanulmányozásának legegyszerűbb modelljét . [35]
A matematika más területein a véletlenszerű sétát arra használják, hogy megoldásokat találjanak a Laplace-egyenletre , megbecsüljék a harmonikus mértéket, valamint különféle konstrukciókat az elemzésben és a kombinatorikában .
A számítástechnikában véletlenszerű sétákat használnak az internet méretének becslésére . [36]
A képszegmentálás során véletlenszerű sétákat használnak az egyes pixelekhez társítandó címkék (például "objektum" vagy "háttér") meghatározására. [37] Ezt az algoritmust általában "random walker" szegmentációs algoritmusnak nevezik.

Mindezekben az esetekben a véletlenszerű sétát gyakran Brown-mozgás váltja fel:

Az agykutatásban véletlenszerű sétákat használnak a neuronok tüzelési kaszkádjainak modellezésére.
A látás tudományában a szemsodródás általában véletlenszerű sétaként viselkedik. [38] Egyes szerzők szerint a rögzítő szemmozgásokat általában véletlenszerű sétával is leírják. [39]
A pszichológiában a véletlenszerű séták pontosan megmagyarázzák a kapcsolatot a döntés meghozatalához szükséges idő és egy bizonyos döntés meghozatalának valószínűsége között. [40]
Véletlenszerű séták segítségével nagyon nagy vagy ismeretlen állapottérből lehet mintát venni, például kiválasztani egy véletlenszerű oldalt az interneten, vagy megvizsgálni egy véletlenszerű munkavállaló munkakörülményeit egy adott országban.

A számítástechnikában ez utóbbi megközelítést Markov-lánc Monte Carlo (MCMC) néven ismerik. Gyakran valamilyen összetett állapottérből való mintavételezés egy valószínűségi becslést is ad a tér méretére vonatkozóan. Egy nagy nullákból és egyesekből álló mátrix állandójának becslése volt az első nagy probléma, amely ezzel a megközelítéssel kapcsolatos.

A véletlenszerű sétákat gyakran használják hatalmas online grafikonok, például közösségi hálózatok mintavételére .
A vezeték nélküli számítógépes hálózatokban a véletlenszerű sétát használják a csomópont mozgásának modellezésére.
A mozgékony baktériumok elfogult, véletlenszerű sétákat hajtanak végre . [41]
A véletlenszerű sétákat a szerencsejáték modellezésére használják .
A fizikában a véletlenszerű séták a Fermi-becslési módszer középpontjában állnak.
A Twitter véletlenszerű sétákat használ, hogy javaslatot tegyen, kit érdemes követni [42]
Dave Byer és Percy Diaconis bebizonyította, hogy 7 megkeverés elég egy pakli kártya megkeveréséhez (továbbiért lásd a Keverés részt ). Ez az eredmény egy szimmetrikus csoportban való véletlenszerű séta állításává válik, ezt bizonyítják, a csoport szerkezetének döntő felhasználásával Fourier-analízissel.
Véletlenszerű séták alkalmazásával lehetőség nyílik a mozgás pályájának rendszerezésére az optimalizált célfüggvény paramétereinek terében , amelyet az optimalizálási feladatok megoldásában használunk [43] . A valószínűségi változók eloszlásának speciális törvényét alkalmazva a véletlenszerű séta módosítása, az úgynevezett Levy repülések érhetők el
Véletlenszerű séták segítségével megoldható a Maxwell-egyenletek határérték-problémája integrál formában. Az integrál kiszámítása Monte Carlo módszerrel történik, míg az integrandus mintavételezése véletlenszerű séta segítségével történik. Így lehetőség nyílik az integrált áramkörökben a vezetők kölcsönös kapacitásának megtalálására, megkerülve a térdiszkretizálásra vonatkozó véges- és határelemes módszerek követelményeit, ami döntő szerepet játszik a módszer megválasztásában, figyelembe véve a kapuk számának növekedését a térben. modern integrált áramkörök. Ellentétben a véges és a határelemes módszerekkel, a véletlenszerű séta módszer azonnal megtalálja a mező integrálját, és nem az egyes pontokban lévő mezőt, amelyet azután integrálnak a kapacitás meghatározásához. [44] A véletlenszerű sétamódszerek a 21. század elején de facto szabványokká váltak az integrált áramkörökben található parazita kapacitások megtalálásában.
A közegben történő optikai sugárzás transzfer egyenletének Monte Carlo módszerrel történő megoldására használják.h*

Opciók

Számos véletlenszerű folyamatot találtak a tisztán véletlenszerű sétákhoz hasonlónak, de ezekben az egyszerű szerkezet általánosítható. Egy tiszta struktúra független és azonos eloszlású valószínűségi változók által meghatározott lépésekkel jellemezhető .

Grafikonokon

Egy k hosszúságú véletlenszerű séta egy esetlegesen végtelen G gráfon 0 gyökével egy sztochasztikus folyamat olyan valószínűségi változókkal , hogy , és ez a szomszédok közül egyenletesen véletlenszerűen kiválasztott csúcs . Ekkor a szám annak a valószínűsége, hogy egy k hosszúságú véletlenszerű séta v - vel kezdődik és w -vel végződik . Különösen, ha G egy 0 -ban gyökerező gráf , annak a valószínűsége, hogy a lépésenkénti véletlenszerű séta 0 -ra tér vissza . ${\displaystyle X_{1},X_{2},\dots ,X_{k))$ $X_{1}=0$ ${X_{i+1))$ $X_{i}$ $p_{v,w,k}(G)$ ${\displaystyle p_{0,0,2k))$ $2k$

A korábban ismertetett szakasz analógiájával (megnövelt méretek) tegyük fel, hogy most városunk már nem tökéletes négyzetrács. Amikor személyünk elér egy kereszteződést, egyenlő valószínűséggel választ a különböző elérhető utak között. Így, ha hét kijárat van a kereszteződésben, egy személy mindegyikhez egy hetedes valószínűséggel megy. Így véletlenszerű sétát kapunk a grafikonon. Vajon eljut az emberünk az otthonába? Kiderült, hogy meglehetősen jó feltételek mellett a válasz igen marad, [45] de a grafikontól függően a következő kérdésre ("Találkozik-e két ember?") a "végtelenül gyakran" válasz már nem majdnem bizonyos esemény. [46]

Példa arra, hogy egy személy szinte biztosan eléri a házat, ha az összes blokk hossza a- tól b - ig terjed (ahol a és b két véges pozitív szám). Fontos: nem tételezzük fel, hogy a gráf sík , azaz alagutak és hidak létezhetnek a városban. Ennek az eredménynek az egyik módja az elektromos hálózatokhoz való csatlakozás . Vegyünk egy várostérképet, és helyezzünk el egy 1 ohmos ellenállást minden blokkra. Most mérjük meg a "pont és a végtelen közötti ellenállást". Más szóval, válasszunk egy R számot , vegyük az elektromos hálózat összes pontját, amelyek távolsága a mi pontunktól nagyobb, mint R, és kössük össze őket. Egy véges elektromos hálózatot kapunk, amelyben meg tudjuk mérni az ellenállást a pontunk és a hálózat többi pontja között. Legyen R a végtelen felé. Az így kapott határt pont és végtelen közötti ellenállásnak nevezzük .

Kiderült, hogy a következő sejtés igaz (egy elemi bizonyíték található Doyle és Snell könyvében):

Tétel : Egy gráf akkor és csak akkor tranziens, ha a pont és a végtelen közötti ellenállás véges. Sőt, a pont kiválasztása nem fontos, ha a gráf össze van kötve.

Más szóval, egy tranziens rendszerben csak a véges ellenállást kell leküzdenie ahhoz, hogy bármely pontból elérje a végtelent. Egy visszatérő rendszerben bármely pont és a végtelen közötti ellenállás végtelen.

Egy véletlenszerű séta egy gráfon a Markov-lánc speciális esete . Az általános Markov-lánctól eltérően a grafikonon történő véletlenszerű séta időszimmetriának vagy reverzibilitásnak nevezett tulajdonsággal rendelkezik . Nagyjából ez a tulajdonság, amelyet a részletes egyensúly elvének is neveznek , azt jelenti, hogy egy adott út egyik vagy másik irányba történő keresztezésének valószínűségei között nagyon egyszerű kapcsolat van (ha a gráf szabályos , akkor egyenlők). Ennek a tulajdonságnak fontos következményei vannak.

Az 1980-as évek óta sok kutatást végeztek a gráf tulajdonságainak véletlenszerű sétákhoz való viszonyítására. A fent leírt elektromos hálózaton kívül izoperimetrikus egyenlőtlenségekkel, funkcionális egyenlőtlenségekkel, mint például a Sobolev- és Poincaré -egyenlőtlenségekkel, valamint a Laplace-egyenlet megoldásainak tulajdonságaival is vannak összefüggések . E kutatások nagy része a végesen generált csoportok Cayley -gráfjaira összpontosított . Sok esetben ezek a diszkrét eredmények sokaságra és Lie-csoportokra is átkerülnek, vagy azokból származnak .

A véletlenszerű gráfokról , különösen az Erdős-Rényi-modellről , a véletlenszerű sétálók egyes tulajdonságaira vonatkozóan születtek elemzési eredmények. Ide tartozik a gyalogló első [47] és utolsó [48] találatának megoszlása (angol. ütési idő), ahol az első találat az, amikor a sétáló először lép egy korábban meglátogatott helyre, az utolsó pedig egybeesik az az eset, amikor a sétálónak nincs hova mennie, kivéve a korábban meglátogatott helyet.

Ez az online könyv jó referencia egy grafikonon való véletlenszerű sétához . Csoportok tanulmányozására Wöss könyvei alkalmasak. Ha maga az átmeneti kernel véletlenszerű (a környezet alapján ), akkor a véletlenszerű sétát "véletlenszerű járásnak véletlenszerű környezetben" nevezzük. Ha a véletlenszerű járás törvénye magában foglalja a véletlenszerűséget , a törvényt hőkezeltnek (angol. annealed ) nevezzük; másrészt, ha rögzítettnek tekintjük, a törvényt temperednek (eng. quenched ) nevezzük. $p(x,y)$ $\omega$ $\omega$ $\omega$

A gráf minden lehetséges élét ugyanolyan valószínűséggel választhatjuk ki, mint a bizonytalanság (entrópia) lokális maximumát. Ezt globálisan is megtehetjük - egy maximális entrópia véletlenszerű séta esetén (eng. maximal entropy random walk, MERW ) szükséges, hogy minden út egyformán valószínű legyen, vagy más szóval bármely két csúcsra minden adott hosszúságú út egyformán valószínű. [49] Az ilyen séta sokkal erősebb lokalizációs tulajdonságokkal rendelkezik.

Önkölcsönhatású véletlenszerű séták

Különféle véletlenszerű séta létezik, amelyben minden lépés összetett módon függ az előzőtől. Analitikusan nehezebb megoldani őket, mint a szokásos véletlenszerű sétákat; azonban bármely véletlenszerű sétáló modell viselkedése kiszámítható számítógépek segítségével. Például:

Önkerülő vándorlás. [ötven]

Az n hosszúságú önelkerülő séta egy n lépés hosszúságú véletlenszerű út, amely az origótól indul, és csak a szomszédos pontokon halad át, és soha nem halad át ugyanazon a ponton kétszer. Kétdimenziós esetben egy ilyen út általában nagyon rövid [51] , míg a megemelt dimenzióban korlátlanul nő. Ezt a modellt gyakran használják a polimerfizikában (az 1960-as évek óta). ${\displaystyle \mathbb {Z} ^{d))$ ${\displaystyle \mathbb {Z} ^{d))$

Véletlenszerű séta ciklustörléssel. [52] [53]
Megerősített véletlenszerű séta. [54]
Kutatási folyamat.
Többügynök véletlenszerű séta. [55]

Hosszú távú korrelált séták

A hosszú távú korrelált idősorok számos biológiai, klimatológiai és gazdasági rendszerben megtalálhatók:

Szívverés felvétel [56]
Nem kódoló DNS-szekvenciák [57]
A részvények volatilitásának idősora [58]
A világ hőmérsékleti rekordjai [59]

Véletlenszerű séták korrelációja

Véletlenszerű séták, amelyekben a mozgás iránya egy adott időpontban korrelál a mozgás irányával a következő időpontban. Az állatok mozgásának szimulálására szolgál. [60] [61]

Lásd még

Jegyzetek

↑ Wirth, E.; Szabó, G.; Czinkóczky, A. Measure Landscape Diversity with Logical Scout Agents // ISPRS – International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences : folyóirat. - 2016. - június 8. ( XLI-B2 köt. ). - P. 491-495 . - doi : 10.5194/isprs-archives-xli-b2-491-2016 . - .
↑ Wirth E. (2015). Pi az ügynök határátlépéseiből a NetLogo csomag segítségével . Wolfram Könyvtár Archívum
↑ Pearson, K. A véletlenszerű séta problémája // Természet . - 1905. - Kt. 72 , sz. 1865 . - 294. o . - doi : 10.1038/072294b0 . — .
↑ Pal, Révész (1990) Véletlenszerű séta véletlenszerű és nem véletlenszerű környezetben , World Scientific
↑ Kohls, Moritz; Hernandez, Tanja. A Random Walk Mobility Algorithm várható lefedettsége (angolul) : folyóirat. - 2016. - . - arXiv : 1611.02861 .
↑ Random Walk-1-Dimensional - a Wolfram MathWorldtől . Mathworld.wolfram.com (2000. április 26.). Letöltve: 2016. november 2. (határozatlan)
↑ Edward A. Colding és munkatársai, Véletlenszerű sétamodellek a biológiában, Journal of the Royal Society Interface, 2008
↑ Kotani, M. és Sunada, T. Kristályrácsok spektrális geometriája. — Kortárs. Math. - 2003. - T. 338. - S. 271-305. — (Kortárs matematika). — ISBN 9780821833834 . - doi : 10.1090/conm/338/06077 .
↑ Kotani, M. és Sunada, T. Nagy eltérés és az érintőkúp a kristályrács végtelenjében , Math . Z. : folyóirat. - 2006. - Vol. 254 , sz. 4 . - P. 837-870 . - doi : 10.1007/s00209-006-0951-9 .
↑ Polia véletlenszerű sétaállandói . Mathworld.wolfram.com. Letöltve: 2016. november 2. (határozatlan)
↑ Durrett, Rick. Valószínűség: elmélet és példák . - Cambridge University Press , 2010. - 191. o . — ISBN 9781139491136 .
↑ Polya, George. Valószínűség ; kombinatoriumok; Tanítás és tanulás matematikából (angol) . - Cambridge, Mass.: MIT Press , 1984. - P. 582-585 . — ISBN 0-262-16097-8 .
↑ Erdős, P.; Taylor, SJ A véletlenszerű sétányok néhány metszéspontja // Acta Mathematica Academiae Scientiarum Hungaricae : folyóirat . - 1960. - 1. évf. 11 , sz. 3-4 . - P. 231-248 . — ISSN 0001-5954 . - doi : 10.1007/BF02020942 .
↑ MacKenzie, D. MATEMATIKA: A Föld legvadabb táncának mértéke // Tudomány : folyóirat. - 2000. - Vol. 290 , sz. 5498 . - P. 1883-1884 . doi : 10.1126 / science.290.5498.1883 . — PMID 17742050 .
↑ 2. fejezet DIFFÚZIÓ Archiválva : 2015. február 9. a Wayback Machine -nél . dartmouth.edu.
↑ Diffúziós egyenlet a véletlenszerű séta számára Archiválva : 2015. április 21. a Wayback Machine -nál . fizika.uakron.edu.
↑ D. Ben-Avraham és S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems Archiválva : 2011. október 4., a Wayback Machine , Cambridge University Press, 2000.
↑ Weiss, George H.; Rubin, Robert J. Random Walks: Theory and Selected Applications // Advances in Chemical Physics. - 1982. - T. 52. - S. 363-505. — ISBN 9780470142769 . - doi : 10.1002/9780470142769.ch5 .
↑ Blumen, A.; Klafter, J.; Zumofen, G. Models for Reaction Dynamics in Glasses // Optical Spectroscopy of Glasses. - 1986. - T. 1. - S. 199-265. - (Kis dimenziós szerkezetű anyagok fizikája és kémiája). - ISBN 978-94-010-8566-3 . - doi : 10.1007/978-94-009-4650-7_5 .
↑ Sándor, S.; Orbach, R. Halmazállapotok sűrűsége fraktálokon : "fraktonok" // Journal de Physique Lettres. - 1982. - T. 43 , 17. sz . - S. 625-631 . doi : 10.1051/jphyslet : 019820043017062500 .
↑ Rammal, R.; Toulouse, G. Random walks on fractal structures and percolation cluster (angol) // Journal de Physique Lettres : Journal. - 1983. - 1. évf. 44 , sz. 1 . - P. 13-22 . - doi : 10.1051/jphyslet:0198300440101300 .
↑ Smoluchowski, MV Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen (német) // Z. Phys. Chem. : bolt. - 1917. - S. 129-168 . , Rice, SA Diffusion-Limited Reactions . - Elsevier , 1985. - V. 25. - (Átfogó kémiai kinetika). — ISBN 978-0-444-42354-2 .
↑ Skellam, JG Random Dispersal in Theoretical Populations // Biometrika : folyóirat. - 1951. - 1. évf. 38 , sz. 1/2 . - P. 196-218 . - doi : 10.2307/2332328 . — PMID 14848123 . — .
↑ Skellam, JG Studies in Statistical Ecology: I. Spatial Pattern (angol) // Biometrika : folyóirat. - 1952. - 1. évf. 39 , sz. 3/4 . - P. 346-362 . - doi : 10.2307/2334030 . — .
↑ Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. N diffúziós részecskék által borított terület // Nature . - 1992. - 1. évf. 355 , sz. 6359 . - P. 423-426 . - doi : 10.1038/355423a0 . - . , Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George. N véletlenszerű sétáló által meglátogatott különálló helyek száma // Physical Review A : Journal . - 1992. - 1. évf. 45 , sz. 10 . - P. 7128-7138 . - doi : 10.1103/PhysRevA.45.7128 . - . — PMID 9906785 . ; Az N véletlenszerű sétáló problémájával kapcsolatos betekintést lásd: Shlesinger, Michael F. New paths for random walkers // Nature . - 1992. - 1. évf. 355 , sz. 6359 . - 396-397 . o . - doi : 10.1038/355396a0 . — . és a cikket illusztráló színes grafikát.
↑ Berger, T. Wiener-folyamatok információs sebessége // IEEE Transactions on Information Theory : folyóirat. - 1970. - 1. évf. 16 , sz. 2 . - 134-139 . o . - doi : 10.1109/TIT.1970.1054423 .
↑ Risken H. (1984) A Fokker–Planck egyenlet . Springer, Berlin.
↑ De Gennes PG (1979) Scaling Concepts in Polymer Physics . Cornell University Press, Ithaca és London.
↑ Van Kampen NG (1992) Sztochasztikus folyamatok a fizikában és a kémiában , átdolgozott és bővített kiadás. Észak-Hollandia, Amszterdam.
↑ Weiss, George H.A Random Walkszempontjai és alkalmazásai . - North-Holland Publishing Co., Amszterdam, 1994. - (Véletlen anyagok és eljárások). - ISBN 978-0-444-81606-1 .
↑ Doi M. és Edwards SF (1986) The Theory of Polymer Dynamics . Clarendon Press, Oxford
↑ Goel NW és Richter-Dyn N. (1974) Sztochasztikus modellek a biológiában . Academic Press, New York.
↑ Redner S. (2001) Útmutató az első áthaladás folyamatához . Cambridge University Press, Cambridge, Egyesült Királyság.
↑ Cox D. R. (1962) Megújuláselmélet . Methuen, London.
↑ Jones , RAL Lágy kondenzált anyag . — Reprint.. — Oxford [ua]: Oxford University Press , 2004. — P. 77–78 . — ISBN 978-0-19-850589-1 .
↑ Bar-Yossef, Ziv; Gurevich, Maxim. Véletlenszerű mintavétel a keresőmotor indexéből // Journal of the ACM : Journal. - Számítógépek Szövetsége (ACM), 2008. - 20. évf. 55 , sz. 5 . - 1-74 . o . — ISSN 0004-5411 . - doi : 10.1145/1411509.1411514 .
↑ Grady, L. Véletlenszerű lépések a képszegmentáláshoz // IEEE Transactions on Pattern Analysis and Machine Intelligence : folyóirat. - 2006. - Vol. 28 , sz. 11 . - P. 1768-1783 . - doi : 10.1109/TPAMI.2006.233 . — PMID 17063682 .
↑ Rucci, M; Victor, JD A bizonytalan szem: információfeldolgozási szakasz, nem hiba // Trends in Neurosciences : folyóirat. - Cell Press , 2015. - Vol. 38 , sz. 4 . - P. 195-206 . - doi : 10.1016/j.tins.2015.01.005 . — PMID 25698649 .
↑ Engbert, R.; Mergenthaler, K.; Sinn, P.; Pikovsky, A. A fixáló szemmozgások és mikroszakkádok integrált modellje (angol) // Proceedings of the National Academy of Sciences of the United States of America : Journal. - 2011. - 20. évf. 108 , sz. 39 . - P. E765-70 . - doi : 10.1073/pnas.1102730108 . - . — PMID 21873243 .
↑ Nosofsky, R. M.; Palmeri, TJ A gyorsított osztályozás példaértékű véletlenszerű sétamodellje // Psychological Review : folyóirat. - 1997. - 1. évf. 104 , sz. 2 . - P. 266-300 . - doi : 10.1037/0033-295x.104.2.266 . — PMID 9127583 . Az eredetiből archiválva: 2004. december 10.
↑ Codling, E. A.; Plank, M. J; Benhamou, S. Véletlenszerű sétamodellek a biológiában // Journal of the Royal Society Interface : folyóirat. - 2008. - augusztus 6. ( 5. köt. , 25. sz.). - P. 813-834 . - doi : 10.1098/rsif.2008.0014 . — PMID 18426776 .
↑ Gupta, Pankaj et al. WTF: The who-to-follow rendszer a Twitteren , Proceedings of the 22. International Conference on World Wide Web
↑ Karpenko A.P. Modern keresőoptimalizálási algoritmusok. A természet által ihletett algoritmusok. M.: MSTU kiadó im. N. E. Bauman, 2014. 446 p.
↑ Sztochasztikus algoritmus nagy sebességű kapacitáskivonáshoz integrált áramkörökben // Microelectronics Reliability. — 1993-07. - T. 33 , sz. 9 . - S. 1420-1421 . — ISSN 0026-2714 . - doi : 10.1016/0026-2714(93)90150-w .
↑ Érdekes megjegyezni, hogy egy általános gráfban két független véletlenszerű sétáló találkozása nem mindig redukálódik egyetlen véletlenszerű séta visszatérésének problémájára.
↑ Krishnapur, Manjunath; Peresz, Yuval. Ismétlődő grafikonok, ahol két független véletlenszerű séta végtelenül gyakran ütközik // Elektronikus kommunikáció valószínűsége : folyóirat. - 2004. - 20. évf. 9 . - 72-81 . o . — ISSN 1083-589X . - doi : 10.1214/ECP.v9-1111 . - . — arXiv : math/0406487 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. A véletlenszerű séták első ütési idejének megoszlása az Erdős–Rényi hálózatokon // Fizikai folyóirat A: Mathematical and Theoretical : folyóirat. - 2017. - Kt. 50 , sz. 11 . — P. 115001 . - doi : 10.1088/1751-8121/aa5af3 . — Iránykód . - arXiv : 1606.01560 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Az önelkerülő séták úthosszainak eloszlása Erdős–Rényi hálózatokon // Fizikai folyóirat A: Mathematical and Theoretical : folyóirat. - 2016. - Kt. 49 , sz. 28 . — P. 285002 . - doi : 10.1088/1751-8113/49/28/285002 . - Iránykód . - arXiv : 1603.06613 .
↑ Burda, Z.; Duda, J.; Szerencse, JM; Waclaw, B. A maximális entrópia véletlenszerű séta lokalizációja // Physical Review Letters : folyóirat . - 2009. - 1. évf. 102 , sz. 16 . - P. 160602 . - doi : 10.1103/PhysRevLett.102.160602 . - . - arXiv : 0810.4113 . — PMID 19518691 .
↑ Madras, Neal és Slade, Gordon (1996) The Self-Avoiding Walk , Birkhäuser Boston. ISBN 0-8176-3891-1 .
↑ Hemmer, S.; Hemmer, PC Egy átlagos önelkerülő véletlenszerű séta a négyzetrácson 71 lépésig tart // Journal of Chemical Physics : Journal. - 1984. - 1. évf. 81 , sz. 1 . - P. 584-585 . - doi : 10.1063/1.447349 . - .
↑ Lawler, Gregory (1996). Véletlenszerű séták kereszteződése , Birkhäuser Boston. ISBN 0-8176-3892-X .
↑ Lawler, Gregory Conformally Invariant Processes in the Plane , book.ps.
↑ Pemantle, Robin. Véletlenszerű folyamatok felmérése megerősítéssel // Valószínűségi felmérések : folyóirat. - 2007. - Vol. 4 . - 1-79 . o . - doi : 10.1214/07-PS094 . — arXiv : math/0610076 .
↑ Alamgir, M és von Luxburg, U (2010). "Multi-agent random walks for local clustering on graphs" , IEEE 10th International Conference on Data Mining (ICDM) , pp. 18-27.
↑ Peng, C.-K.; Mietus, J; Hausdorff, JM; Havlin, S; Stanley, H. E.; Goldberger, A.L. A szívverés hosszú távú antikorrelációi és nem Gauss-féle viselkedése // Phys . Fordulat. Lett. : folyóirat. - 1993. - 1. évf. 70 , sz. 9 . - P. 1343-1346 . - doi : 10.1103/PhysRevLett.70.1343 . - . — PMID 10054352 .
↑ Peng, CK; Buldyrev, SV; Goldberger, A. L.; Havlin, S; Sciortino, F; Simons, M; Stanley, H.E. Long-range correlations in nucleotid series // Nature . - 1992. - 1. évf. 356. sz . 6365 . - 168-170 . o . - doi : 10.1038/356168a0 . — . — PMID 1301010 .
↑ Liu, Yanhui; Cizeau, Pierre; Meyer, Martin; Peng, C.-K.; Eugene Stanley, H. Korrelációk gazdasági idősorokban // Physica A : folyóirat. - 1997. - 1. évf. 245 , sz. 3-4 . - 437. o . - doi : 10.1016/S0378-4371(97)00368-3 . — . - arXiv : cond-mat/9706021 .
↑ Koscielny-Bunde, Éva; Bunde, Armin; Havlin, Shlomo; Roman, H. Eduardo; Goldreich, Yair; Schellnhuber, Hans-Joachim. A légkör változékonyságát szabályozó egyetemes perzisztencia törvény jelzése // Phys . Fordulat. Lett. : folyóirat. - 1998. - 1. évf. 81 , sz. 3 . - 729. o . - doi : 10.1103/PhysRevLett.81.729 . — .
↑ Bovet, Pierre; Benhamou, Simon. Az állatok mozgásának térbeli elemzése korrelált véletlenszerű sétamodellel // Journal of Theoretical Biology : folyóirat. - 1988. - 1. évf. 131. sz . 4 . - P. 419-433 . - doi : 10.1016/S0022-5193(88)80038-9 .
↑ Kareiva, PM; Shigesada, N. A rovarmozgás elemzése korrelált véletlenszerű sétaként (angol) // Oecologia : Journal. - 1983. - 1. évf. 56 , sz. 2-3 . - P. 234-238 . - doi : 10.1007/BF00379695 . — . — PMID 28310199 .

Irodalom

Aldous, David; Töltsd, James Allen. Megfordítható Markov-láncok és véletlenszerű séták a grafikonokon . – 2002.
Ben-Avraham D.; Havlin S. , Diffusion and Reactions in Fractals and Disordered Systems Archiválva : 2011. október 4., a Wayback Machine , Cambridge University Press, 2000.
Doyle, Peter G.; Snell, J. Laurie. Véletlenszerű séták és elektromos hálózatok. - Mathematical Association of America , 1984. - Vol. 22. - (Carus Mathematical Monographs). - ISBN 978-0-88385-024-4 .
Feller, William (1968), Bevezetés a valószínűségszámításba és alkalmazásaiba (1. kötet). ISBN 0-471-25708-7
Hughes, Barry D. (1996), Random Walks and Random Environments , Oxford University Press. ISBN 0-19-853789-1
Norris, James (1998), Markov Chains , Cambridge University Press. ISBN 0-521-63396-6
Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz" Archiválva : 2016. március 4., a Wayback Machine , Mathematische Annalen , 84(1-2):149-1921. március.
Révész, Pal (2013), Random Walk in Random and Non-random Environments (Third Edition) , World Scientific Pub Co. ISBN 978-981-4447-50-8
Szunada, ToshikazuTopológiai krisztallográfia: Kilátással a diszkrét geometriai elemzésre . - Springer, 2012. - 2. évf. 6. - (Felmérések és oktatóanyagok az alkalmazott matematikai tudományokból). — ISBN 978-4-431-54177-6 .
Weiss G. A Random Walk szempontjai és alkalmazásai , Észak-Holland, 1994.
Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups , Cambridge traktusok matematikában 138, Cambridge University Press. ISBN 0-521-55292-3

Linkek

Polya véletlenszerű séta állandói
Véletlenszerű séta a Java kisalkalmazásban Archivált 2007. augusztus 31. a Wayback Machine -nél
Kvantum véletlenszerű séta
Gauss véletlenszerű sétabecslő
Elektronvezetési modellek Maximális entrópiával Véletlenszerű séták Wolfram demonstrációs projekt

Szótárak és enciklopédiák	Nagy dán Nagy orosz Britannica (online)
Bibliográfiai katalógusokban	BNF : 119358404 J9U : 987007563128805171 LCCN : sh85111357 NDL : 00571555