Náhodná procházka

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. října 2022; ověření vyžaduje 1 úpravu .

Náhodná procházka je matematický objekt známý jako stochastický nebo náhodný proces , který popisuje cestu sestávající ze sekvence náhodných kroků v nějakém matematickém prostoru (například na množině celých čísel ).

Nejjednodušším příkladem náhodné procházky je náhodná procházka po číselné řadě celých čísel , , která začíná v bodě 0 a posouvá se o +1 nebo -1 v každém kroku se stejnou pravděpodobností . Dalšími příklady jsou trajektorie molekuly v kapalině nebo plynu ( Brownův pohyb ), hledání cesty u zvířat během hledání potravy , kolísání cen akcií na akciovém trhu , finanční situace hráče : všechny popsané případy lze aproximovat náhodnou procházkou. modely, i když v reálném životě nemusí být zcela náhodné. $\mathbb {Z}$

Jak můžete vidět z příkladů, model náhodné procházky se používá ve strojírenství a mnoha vědeckých oborech, včetně ekologie, psychologie, informatiky, fyziky, chemie, biologie, ekonomie a sociologie. Náhodná procházka vysvětluje pozorované chování mnoha procesů v těchto oblastech a slouží tak jako základní model pro zaznamenanou stochastickou aktivitu. Takže v matematice lze hodnotu π aproximovat pomocí náhodné procházky a modelování založeného na agentech. [1] [2] Koncept náhodné procházky poprvé představil Karl Pearson v roce 1905. [3]

Typy náhodných procházek mohou být zajímavé. Samotný termín nejčastěji označuje zvláštní kategorii Markovových řetězců nebo Markovových procesů a mnoho časově závislých procesů se označuje jako náhodné procházky s modifikátorem označujícím jejich speciální vlastnosti. Náhodné procházky (Markov nebo ne) mohou také nastat v paletě polí: ty běžně studované zahrnují grafy , číselnou řadu celých nebo reálných čísel , vektorové prostory , zakřivené povrchy, multidimenzionální Riemannovy variety a konečné , finitely generované grupy, Lieovy grupy . Časový parametr může být také odlišný. V nejjednodušším případě se procházka odehrává v diskrétním čase a je posloupností náhodných proměnných ( X
t) = ( X
jeden, X
2, ...) , indexované přirozenými čísly. Existují však také náhodné procházky, ve kterých se kroky vyskytují v libovolném časovém okamžiku, a v tomto případě pozice X
tmusí být definováno pro všechny časy t ∈ [0,+∞) . Speciálními případy náhodné procházky jsou Levyho letové a difúzní modely , jako je Brownův pohyb .

Náhodná procházka je základním tématem diskusí o Markovově procesu a jeho matematické studium je velmi rozsáhlé.

Náhodná chůze po mříži

Známým modelem náhodné procházky je chůze po pravidelné mříži, kde se při každém kroku místo přesune do jiného bodu v souladu s určitým rozdělením pravděpodobnosti.

Při jednoduché náhodné procházce se může umístění přesunout pouze k sousedním bodům mřížky a vytvořit tak dráhu mřížky. V jednoduché symetrické náhodné procházce po lokálně ohraničené mřížce jsou pravděpodobnosti, že bod míří ke každému z jeho bezprostředních sousedů, stejné. Nejlépe prozkoumaným příkladem je náhodná procházka po d - rozměrné mřížce celých čísel (někdy nazývané hyperkubická mřížka) . [čtyři] ${\displaystyle \mathbb {Z} ^{d))$

Pokud je stavový prostor omezen na konečný počet dimenzí, pak se takový model náhodné procházky nazývá jednoduchá ohraničená symetrická náhodná procházka a pravděpodobnosti přechodu závisí na umístění bodu, protože pohyb je omezen na hraničních a rohových bodech. . [5]

Jednorozměrná náhodná procházka

Nejjednodušším příkladem náhodné procházky je náhodná procházka po číselné ose celých čísel , , která začíná v bodě 0 a pohybuje se +1 nebo −1 se stejnou pravděpodobností v každém kroku. $\mathbb {Z}$

Toto putování lze znázornit následovně. Značka se umístí na nulu číselné řady a vhodí se „spravedlivá“ mince. Pokud se dostane nahoru, štítek se posune o jednu jednotku doprava, a pokud se dostane nahoru, posune se o jednotku doleva. Po pěti hodech může být známka na -5, -3, -1, 1, 3, 5. Pro pět hodů, včetně tří hlav a dvou ocasů, v libovolném pořadí, bude známka na 1. Existuje 10 způsobů jak se dostat do bodu 1 (hozením tří hlav a dvou ocasů), 10 způsobů, jak se dostat do bodu −1 (tři ocasy a dvě hlavy), 5 způsobů, jak se dostat do bodu 3 (čtyři hlavy) a jeden „ocásky“), 5 způsoby, jak se dostat do bodu -3 (čtyři "ocasy" a jeden "orel"), 1 způsob, jak se dostat do bodu 5 (pět "hlav") a 1 způsob, jak se dostat do bodu -5 (pět "ocasů"). ") . Možné výsledky pěti hodů jsou uvedeny níže.

Abychom tuto procházku formálně definovali, vezmeme nezávislé náhodné proměnné , kde každá proměnná je buď 1 nebo −1, s pravděpodobností rovnou 50 % pro každou hodnotu, množina a Série se nazývají jednoduchá náhodná procházka na . Tato řada (součet posloupnosti −1 a 1) znamená ujetou vzdálenost, pokud má každá část chůze délku rovnou jedné. Matematické očekávání řady je nulové. To znamená, že průměrná hodnota všech hodů mincí má s rostoucím počtem hodů tendenci k nule. To vyplývá z konečné aditivní vlastnosti očekávání: $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.

Argumentujeme podobně, používáme nezávislost náhodných proměnných a skutečnost , že vidíme: $E(Z_{n}^{2})=1$

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

To objasňuje , že očekávaná vzdálenost po přesunutí n kroků by měla být řádu . Ve skutečnosti [6] $E(|S_{n}|)\,\!$ ${\sqrt n}$

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

Kolikrát náhodná procházka překročí hranici, pokud je možné bloudit donekonečna? Nejjednodušší náhodná procházka protne každý bod nekonečněkrát. Výsledný efekt má mnoho názvů: fenomén překročení úrovně , opakování nebo problém se zničením hráče . Důvod pro pojmenování posledního případu je tento: hráč s konečným množstvím peněz dříve nebo později prohraje, pokud hraje férovou hru proti banku s neomezeným množstvím peněz. Peníze hráče jsou náhodnou procházkou a v určitém okamžiku dosáhnou nuly a hra bude u konce. $\mathbb {Z}$

Nechť aab jsou kladná celá čísla, pak očekávaný počet kroků , když jednoduchá jednorozměrná náhodná procházka začínající na 0 nejprve dosáhne b nebo −a je ab . Pravděpodobnost, že daná procházka dosáhne b dříve, než dosáhne −a , je , což vyplývá ze skutečnosti, že jednoduchá náhodná procházka je martingal . $a/(a+b)$

Některé z výše uvedených výsledků lze odvodit z vlastností Pascalova trojúhelníku . Počet všech zřetelných procházek přes n

kroky, kde každý krok je buď +1 nebo -1 se rovná 2 n . Pro jednoduchou náhodnou procházku je každý z těchto kroků stejně pravděpodobný. Abychom se rovnali číslu k , je nutné a postačující, aby počet kroků o +1 v chůzi převýšil počet kroků o −1 o číslo k . Proto musí nastat krok na +1 (n + k)/2 krát mezi n procházkami, proto se počet procházek, které splňují podmínku, rovná počtu způsobů výběru (n + k)/2 prvků z n -prvková sada. [7] Označuje se jako . Aby tento výraz dával smysl, je nutné, aby součet n + k byl sudé číslo, což znamená, že čísla n a k musí být buď sudá, nebo lichá zároveň. Pravděpodobnost, která se tedy bude rovnat . Reprezentací vstupů Pascalova trojúhelníku z hlediska faktoriálů a pomocí Stirlingova vzorce lze získat dobré odhady těchto pravděpodobností pro velké hodnoty . $S_{n}\,\!$ $S_{n}=k$ $n \vyberte (n+k)/2$ $S_{n}=k$ ${\displaystyle 2^{-n}{n \vyberte (n+k)/2))$ $n$

Pokud je prostor kvůli stručnosti omezen na +, pak počet způsobů, jak se náhodná procházka zastaví na nějakém čísle po pěti krocích, může být zobrazen jako {0,5,0,4,0,1}. $\mathbb {Z}$

Ukažme tuto shodu s Pascalovým trojúhelníkem pro malé hodnoty n . U nulového kroku je jedinou možností zůstat na nule. Již při prvním tahu však existuje možnost skončit buď na -1 nebo na 1. Při druhém tahu z 1 se můžete přesunout do bodu 2 nebo zpět na nulu. Můžete se pohybovat od -1 do -2 nebo zpět na nulu. Existuje tedy jeden případ, kdy jsme v bodě -2, dva případy, kdy jsme na nule, a jeden případ, kdy jsme v bodě 2.

k	−5	−4	−3	−2	−1	0	jeden	2	3	čtyři	5
$P[S_{0}=k]$						jeden
$2P[S_{1}=k]$					jeden		jeden
$2^{2}P[S_{2}=k]$				jeden		2		jeden
$2^{3}P[S_{3}=k]$			jeden		3		3		jeden
$2^{4}P[S_{4}=k]$		jeden		čtyři		6		čtyři		jeden
$2^{5}P[S_{5}=k]$	jeden		5		deset		deset		5		jeden

Centrální limitní teorém a zákon iterovaného logaritmu popisují důležité aspekty chování jednoduché náhodné procházky po . Zejména, jak se n zvyšuje, pravděpodobnosti (v poměru k číslům v každém řádku) mají tendenci k normálnímu rozdělení . $\mathbb {Z}$

Náhodné procházky po krystalových mřížkách (nekonečně mnohonásobné abelovské krycí grafy konečných grafů) lze považovat za přímé zobecnění. Ve skutečnosti je za takových podmínek dokonce možné prosadit centrální limitní větu a větu o velké odchylce. [8] [9]

Jako Markovův řetěz

Jednorozměrná diskrétní náhodná procházka je celočíselný Markovův řetězec , jehož počáteční rozdělení je dáno funkcí pravděpodobnosti náhodné proměnné a matice pravděpodobnosti přechodu je $X_{0}$

P\equiv (p_{{ij}})_{{i,j\in {\mathbb {Z}}}}=\left({\begin{matrix}\ddots &\ddots &\ddots &\\&q_ {{-1}}&0&p_{{-1}}&\\&&q_{0}&0&p_{0}\\&&&q_{1}&0&p_{1}\\&&&&\dtečky &\dtečky &\dtečky \end{matrix} }\že jo)

to znamená

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.

Zvýšené rozměry

Ve vyšších dimenzích má množina bodů náhodné procházky poměrně zajímavé geometrické vlastnosti. Ve skutečnosti získáme diskrétní fraktál , tedy sadu, která při přiblížení ukazuje stochastickou sebepodobnost . V malém měřítku můžete pozorovat "zubatost" na mřížce, na které se provádí chůze. Dvě citované Lawlerovy knihy jsou dobrým zdrojem materiálu na toto téma. Trajektorie náhodné procházky je sbírka navštívených bodů, které jsou považovány za soubor až do okamžiku, kdy procházka dosáhla bodu. V jednom rozměru jsou trajektorií jednoduše všechny body mezi minimální výškou a maximální výškou, které vandr dosáhl (oba v průměru řádově ). ${\sqrt {n}}$

Pro vizualizaci dvourozměrného případu si lze představit osobu, která náhodně chodí po městě. Toto město je prakticky nekonečné a je rozloženo do čtvercové sítě chodníků. Na každé křižovatce si člověk náhodně vybere jednu ze čtyř možných tras (včetně té, ze které přišel). Formálně se jedná o náhodnou procházku po množině všech bodů v rovině s celočíselnými souřadnicemi .

Vrátí se tato osoba někdy na výchozí bod putování? Tento případ je 2D ekvivalentem problému úrovňového přejezdu diskutovaného výše. V roce 1921 György Pólya dokázal, že v případě dvojrozměrné náhodné procházky by se člověk téměř jistě vrátil, ale pro tři nebo více dimenzí pravděpodobnost návratu klesá s rostoucím počtem dimenzí. V trojrozměrném případě pravděpodobnost klesá na cca 34 %. [10] Matematik Shizuo Kakutani je známý svým citátem týkajícím se tohoto výsledku: "Opilec dříve nebo později najde cestu domů, ale opilý pták může být navždy ztracen." [jedenáct]

Další verze této otázky, kterou si položil i Poya, zní: pokud dva lidé odejdou ze stejného výchozího bodu, setkají se někdy? [12] Dá se předpokládat, že rozdíl mezi jejich umístěními (dvě nezávislé náhodné procházky) je také jednoduchá náhodná procházka, takže se téměř jistě setkají ve dvourozměrné procházce, ale pro tři nebo více rozměrů je pravděpodobnost návratu stejně jako v předchozím případě klesá s rostoucím počtem měření. Pal Erdős a Samuel James Taylor také v roce 1960 ukázali, že pro rozměry menší nebo rovné 4 mají dvě nezávislé náhodné procházky, začínající v libovolných dvou daných bodech, téměř jistě nekonečně mnoho průsečíků, ale pro rozměry větší než 5 téměř jistě protínají pouze konečný počet časů. [13]

Asymptotická funkce pro 2D náhodnou procházku s rostoucím počtem kroků je dána Rayleighovým rozdělením . Rozdělení pravděpodobnosti je funkcí poloměru od počátku a pro každý krok je délka kroku konstantní.

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

Vztah k Wienerově procesu

Wienerův proces je stochastický proces, který se svým chováním podobá Brownovu pohybu , fyzikálnímu jevu difúze malých částic v kapalině. (Někdy se Wienerův proces nazývá Brownův pohyb, ačkoli přísně vzato je Wienerův proces model a Brownův pohyb je modelovaný jev.)

Wienerův proces je škálovatelný limit jednorozměrné náhodné procházky. To znamená, že pokud uděláte náhodnou procházku s velmi malými kroky, můžete získat aproximaci Wienerova procesu (a s menší přesností Brownova pohybu). Přesněji, je-li délka kroku ε, je třeba provést procházku délky L /ε 2 , aby se aproximovala Wienerova cesta L . Jak se délka kroku blíží nule (a počet kroků se úměrně zvyšuje), náhodná procházka pokrývá Wienerův proces ve vhodném smyslu. Formálně, jestliže B je prostor všech cest délky L s maximální topologií a jestliže M je prostor mír nad B s normální topologií, pak je konvergence v prostoru M . Analogicky je Wienerův proces ve více dimenzích škálovatelným limitem náhodné procházky ve stejném počtu dimenzí.

Náhodná procházka je diskrétní fraktál (funkce s celočíselným počtem dimenzí; 1, 2, ...), zatímco trajektorie Wienerova procesu je skutečný fraktál a mezi nimi existuje určitá souvislost. Udělejme například náhodnou procházku a budeme „chodit“, dokud neprojdeme kružnicí o poloměru r krát délka kroku. Pak se průměrný počet kroků potřebných k dokončení chůze bude rovnat r 2 . Tato skutečnost je diskrétní verzí skutečnosti, že procházka Wienerovým procesem je fraktálem Hausdorffovy dimenze 2.

Ve dvourozměrném prostoru je průměrný počet bodů, které náhodná procházka projde na hranici své trajektorie, r 4/3 . To je v souladu se skutečností, že hranice trajektorie Wienerova procesu je 4/3 fraktál, který navrhl Mandelbrot pomocí simulací, ale byl prokázán až v roce 2000 Lawlerem, Schrammem a Wernerem . [čtrnáct]

Wienerův proces má na rozdíl od náhodné procházky mnoho symetrií . Například procházka Wienerovým procesem je rotačně invariantní, ale náhodná procházka není, protože její mřížka není rotačně invariantní (náhodná procházka je rotačně invariantní o 90 stupňů, zatímco Wienerovy procesy jsou rotačně invariantní například o dalších 17 stupňů). ). To znamená, že v mnoha případech se problémy zadané na náhodné procházce snáze řeší následujícím způsobem: přeneste problém do Wienerova procesu, vyřešte problém tam a pak jej přeneste zpět. Na druhou stranu se některé problémy dají snáze vyřešit na náhodné procházce kvůli její diskrétnosti.

Konvergence náhodné procházky k Wienerově procesu se provádí pomocí centrální limitní věty a Donskerovy věty. Pro částici ve známé pevné poloze v t = 0 nám centrální limitní teorém říká, že po velkém počtu nezávislých náhodných kroků bude pozice tuláka rozdělena podle normálního rozložení rozptylu :

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

kde t je čas, který uplynul od začátku náhodné procházky, je velikost kroku procházky a je čas, který uplynul mezi dvěma po sobě jdoucími kroky. $\varepsilon$ $\delta t$

Tento případ odpovídá Greenově funkci difúzní rovnice , která popisuje Wienerův proces, což naznačuje, že po dostatečně velkém počtu kroků náhodná procházka konverguje k Wienerově procesu.

V 3D případě je rozptyl odpovídající Greenově funkci difúzní rovnice:

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

Vyrovnáním této hodnoty s rozptylem spojeným s polohou náhodného chodce lze získat ekvivalentní difúzní koeficient uvažovaný pro asymptotický Wienerův proces, ke kterému náhodná procházka konverguje po dostatečně velkém počtu kroků:

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

(má smysl pouze v případě tří rozměrů).

Poznámka: Výše uvedené dva výrazy rozptylu odpovídají rozdělení spojenému s vektorem , který spojuje dva konce náhodné procházky ve třech rozměrech. Rozdíl spojený s každou komponentou nebo , je pouze jedna třetina celkové hodnoty (stále 3D). $\vec R$ $R_{x}$ $R_{y}$ $R_{z}$

Pro 2D: [15]

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

Pro 1D: [16]

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

Donskerův teorém

Zvažte náhodnou procházku , kde . $Y_{n}=\sum \limits _{{i=1}}^{{n}}{X_{i}}$ $EX_{i}=0,DX_{i}=\sigma ^{2}<\infty$

Centrální limitní teorém říká, že rozdělením na . ${\frac {Y_{n}}{\sigma {\sqrt {n}}}}\rightarrow N(0,1)$ $n\rightarrow\infty$

U náhodných procházek však lze toto tvrzení výrazně posílit.

Sestrojíme náhodný proces s ohledem na , definujeme jej takto: a pro zbytek definujeme proces lineárním pokračováním: $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}}\right),t\in \left({\frac {k}{n));{\frac {k+1}{n}}\right)$

Z centrální limitní věty o rozdělení pro $\forall t$ $S_{n}(t)\rightarrow N(0,t)$ $n\rightarrow\infty$

To znamená konvergenci jednorozměrných distribucí procesu k jednorozměrným distribucím Wienerova procesu . Donskerův teorém, nazývaný také princip invariance, říká, že existuje slabá konvergence procesů, $S_{n}(t)$ $S_{n}(t)\šipka doprava W(t),n\šipka doprava \infty$

Slabá konvergence procesů znamená konvergenci funkcionálů, které jsou spojité s ohledem na Wienerovu míru, to znamená, že umožňuje vypočítat hodnoty funkcionálů z Brownova pohybu (například maximum, minimum, poslední nula, okamžik prvního dosažení úroveň a další) přechodem na limit z jednoduché náhodné procházky.

Gaussova náhodná procházka

Náhodná procházka s délkou kroku, která se mění s normálním rozdělením , se používá jako data časových řad v reálném světě, jako jsou finanční trhy. Vzorec Black-Schools například používá jako základní předpoklad Gaussovu náhodnou procházku.

V tomto případě je velikost kroku inverzní kumulativní normální rozdělení , kde 0 ≤ z ≤ 1 a je rovnoměrně rozdělené náhodné číslo, a μ a σ jsou střední a standardní odchylka normálního rozdělení. $\Phi ^{-1}(z,\mu ,\sigma)$

Pokud je μ nenulové, náhodná procházka bude sledovat lineární trend. Je-li v s počáteční hodnota náhodné procházky, pak očekávaná hodnota po n krocích je v s + n μ.

Pro speciální případ, kdy μ je nula, je po n krocích definováno rozdělení pravděpodobnosti ujeté vzdálenosti jako N (0, n σ 2 ), kde N () je označení pro normální rozdělení, n je počet kroků , a σ je převzato z výše uvedeného inverzního kumulativního normálního rozdělení.

Důkaz: Gaussovu náhodnou procházku lze reprezentovat jako součet posloupnosti nezávislých a shodně rozdělených náhodných veličin, X i z inverzního kumulativního normálního rozdělení, kde průměr je nula a σ je převzato z původního inverzního kumulativního normálního rozdělení:

Z = ,

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

ale máme rozdělení pro součet dvou nezávislých normálně rozdělených náhodných veličin, Z = X + Y, získaných díky

\mathcal{N}

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

V našem případě μ X = μ Y = 0 a σ 2 X = σ 2 Y = σ 2 dávají:

\mathcal{N}

(0, 2σ 2 )

Indukcí pro n kroků máme:

Z ~ (0, nσ2 ) .

\mathcal{N}

Pro kroky rozdělené podle libovolného rozdělení s nulovým průměrem a konečným rozptylem (ne nutně jen normálním rozdělením) je střední kvadrát ujeté vzdálenosti po n krocích dán vztahem:

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

Ale pro Gaussovu náhodnou procházku je to pouze standardní odchylka distribuce ujeté vzdálenosti po n krocích. Pokud je tedy μ nula a pokud je překonaná rms vzdálenost jedna standardní odchylka, existuje 68,27% šance, že rms vzdálenost ujetá po n krocích bude mezi ± σ . Existuje také 50% pravděpodobnost, že vzdálenost ujetá po n krocích bude mezi ± 0,6745σ . ${\sqrt {n}}$ ${\sqrt {n}}$

Anomální difúze

V neuspořádaných systémech, jako jsou porézní média a fraktály, může být úměrná nikoli , ale . Exponent se nazývá exponent anomální difúze a může být větší nebo menší než 2. [17] Anomální difuzi lze také vyjádřit jako σ r 2 ~ Dt α , kde α je parametr anomálie. Některé difúze v náhodném prostředí jsou dokonce úměrné síle logaritmu času, jako je Sinajova chůze nebo Broxova difúze. $\sigma ^{2}$ $t$ $t^{2/d_{w))$ $d_{w}$

Počet různých míst

Počet různých míst navštívených jedním náhodným chodcem byl rozsáhle studován pro čtvercové a kubické mřížky a fraktály. [18] [19] Tato hodnota je užitečná pro analýzu problémů uváznutí (anglicky trapping ) a kinetických reakcí. Souvisí také s vibrační hustotou stavů, [20] [21] difúzními reakcemi procesů [22] , a rozložením populací v ekologii. [23] [24] Zobecnění tohoto problému na počet různých míst navštěvovaných náhodnými chodci, označované jako , bylo nedávno studováno pro d -rozměrné euklidovské mřížky. [25] Počet různých míst navštívených N chodci nesouvisí pouze s počtem různých míst navštívených každým chodcem. $Svatý)$ $N$ $S_{N}(t)$

Odhad množství informací

Odhad informačního množství Gaussovy náhodné procházky s ohledem na druhou mocninu chybové vzdálenosti, tj. její funkci kvadratického zkreslení, danou parametricky: [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 ,

kde . Proto není možné binárně kódovat s menším počtem bitů a poté dekódovat s očekávanou chybou RMS menší než . Na druhou stranu pro jakýkoli , existuje dostatečně velký a binární kód s ne více než prvky, takže očekávaná střední kvadratická chyba při obnově z tohoto kódu není větší než . ${\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$

Aplikace

Jak již bylo zmíněno, rozsah přírodních jevů, které se některé variety náhodných procházek snažily popsat, je významný. Zejména ve fyzice, [27] [28] chemii, [29] nauce o materiálech [ 30] [31] biologii [32] a dalších různých vědách. [33] [34] Zde jsou některé aplikace náhodné procházky:

Ve finanční ekonomii se „hypotéza náhodné procházky“ používá k modelování cen akcií a dalších faktorů. Empirické studie však zjistily rozpory s teoretickým modelem, zejména v krátkodobých a dlouhodobých vztazích.
V populační genetice náhodná procházka popisuje statistické vlastnosti genetického driftu .
Ve fyzice se náhodné procházky používají jako zjednodušené modely Brownova pohybu a difúze , jako je náhodný pohyb molekul v kapalinách a plynech. Například difúzně omezená agregace. Také ve fyzice hrají v kvantové teorii pole důležitou roli náhodné procházky a některé z nich interagující procházky .
V matematické ekologii se náhodné procházky používají k popisu jednotlivých pohybů zvířat, k empirické podpoře biodifúzních procesů a někdy k modelování populační dynamiky .
Ve fyzice polymerů náhodná procházka popisuje ideální řetězec, nejjednodušší model pro studium polymerů . [35]
V jiných oblastech matematiky se náhodná procházka používá k nalezení řešení Laplaceovy rovnice , k odhadu harmonické míry ak různým konstrukcím v analýze a kombinatorice .
V informatice se k odhadu velikosti internetu používají náhodné procházky . [36]
Při segmentaci obrazu se náhodné procházky používají k určení štítků (jako je „objekt“ nebo „pozadí“), které se mají přiřadit ke každému pixelu. [37] Tento algoritmus je běžně označován jako segmentační algoritmus „random walker“.

Ve všech těchto případech je náhodná procházka často nahrazena Brownovým pohybem:

Při výzkumu mozku se náhodné procházky používají k modelování kaskád střílení neuronů.
Ve vědě o vidění má oční drift tendenci chovat se jako náhodná procházka. [38] Podle některých autorů se fixování očních pohybů obecně popisuje také náhodnou procházkou. [39]
V psychologii náhodné procházky přesně vysvětlují vztah mezi časem potřebným k rozhodnutí a pravděpodobností, že bude učiněno určité rozhodnutí. [40]
Náhodné procházky lze použít k odběru vzorků ze stavového prostoru, který je velmi velký nebo neznámý, například k výběru náhodné stránky na internetu nebo ke zkoumání pracovních podmínek náhodného pracovníka v dané zemi.

Při použití v počítačové vědě je druhý přístup známý jako Markovův řetězec Monte Carlo (MCMC). Vzorkování z nějakého komplexního stavového prostoru často také poskytuje pravděpodobnostní odhad velikosti prostoru. Odhad trvalosti velké matice nul a jedniček byl prvním velkým problémem spojeným s použitím tohoto přístupu.

Náhodné procházky se často používají k vzorkování masivních online grafů, jako jsou sociální sítě .
V bezdrátových počítačových sítích se náhodná procházka používá k modelování pohybu uzlu.
Pohyblivé bakterie provádějí zkreslené náhodné procházky . [41]
Náhodné procházky slouží k modelování hazardu .
Ve fyzice jsou náhodné procházky jádrem metody Fermiho odhadu.
Twitter používá náhodné procházky, aby navrhl, kdo by mohl být hodný sledování [42]
Dave Byer a Percy Diaconis dokázali, že k zamíchání balíčku karet stačí 7 zamíchání (více viz sekce Zamíchání ). Tento výsledek se promítá do tvrzení o náhodné procházce v symetrické skupině, což dokazují, s rozhodujícím využitím struktury skupiny pomocí Fourierovy analýzy.
Pomocí náhodných procházek je možné organizovat trajektorii pohybu v prostoru parametrů optimalizované účelové funkce , která se využívá při řešení optimalizačních úloh [43] . použití speciálního zákona rozdělení náhodných veličin lze získat modifikaci náhodné procházky zvanou Levyho lety
Pomocí náhodných procházek lze vyřešit okrajový problém pro Maxwellovy rovnice v integrálním tvaru. Integrál je vypočítán pomocí metody Monte Carlo, zatímco integrand je vzorkován pomocí náhodné procházky. Je tak možné nalézt vzájemné kapacity vodičů v integrovaných obvodech, obcházet požadavky metod konečných a hraničních prvků na prostorovou diskretizaci, která hraje rozhodující roli při výběru metody, s přihlédnutím k nárůstu počtu hradel v moderní integrované obvody. Na rozdíl od metod konečných a hraničních prvků metoda náhodné procházky okamžitě najde integrál pole, a nikoli pole v každém bodě, které se pak integruje, aby se zjistila kapacita. [44] Metody náhodné chůze se staly na počátku 21. století de facto standardem při hledání parazitních kapacit v integrovaných obvodech.
Používá se při řešení rovnice přenosu optického záření v médiu metodou Monte Carlo.h*

Možnosti

Bylo zjištěno, že několik druhů náhodných procesů je podobných čistě náhodným procházkám, ale ve kterých lze jednoduchou strukturu více zobecnit. Čistá struktura může být charakterizována kroky definovanými nezávislými a shodně rozdělenými náhodnými proměnnými .

Na grafech

Náhodná procházka délky k na možná nekonečném grafu G s kořenem 0 je stochastický proces s náhodnými proměnnými takovými, že , a to je vrchol rovnoměrně náhodně vybraný mezi sousedy . Potom číslo je pravděpodobnost, že náhodná procházka délky k začíná na v a končí na w . Konkrétně, pokud G je graf s kořenem 0 , je pravděpodobnost, že se postupná náhodná procházka vrátí na 0 . ${\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$

Analogicky k výše popsané části (zvětšení rozměrů) předpokládejme, že nyní naše město již není dokonalou čtvercovou sítí. Když se náš člověk dostane na určitou křižovatku, vybírá se stejnou pravděpodobností mezi různými dostupnými cestami. Pokud je tedy na křižovatce sedm sjezdů, na každý pojede člověk s pravděpodobností jedné sedminy. Dostaneme tedy náhodnou procházku po grafu. Dostane se náš muž do svého domu? Ukazuje se, že za celkem dobrých podmínek zůstává odpověď ano, [45] ale v závislosti na grafu u další otázky („Sejdou se dva lidé?“) již nemusí být odpověď „nekonečně často“ téměř určitá událost. [46]

Příklad, kdy člověk téměř jistě dosáhne domu, je, když jsou délky všech bloků v rozsahu od a do b ( kde aab jsou dvě konečná kladná čísla). Důležité: nepředpokládáme, že graf je rovinný , to znamená, že ve městě mohou existovat tunely a mosty. Jedním ze způsobů, jak dokázat tento výsledek, je připojení k elektrické síti . Vezměte mapu města a umístěte na každý blok 1 ohmový odpor . Nyní změřme „odpor mezi bodem a nekonečnem“. Jinými slovy, zvolme nějaké číslo R a vezměme všechny body v elektrické síti se vzdáleností mezi nimi a naším bodem větší než R a spojíme je dohromady. Získáme konečnou elektrickou síť, ve které můžeme měřit odpor mezi naším bodem a ostatními body v síti. Nechť R směřuje k nekonečnu. Výsledná mez se nazývá odpor mezi bodem a nekonečnem .

Ukazuje se, že následující domněnka je pravdivá (elementární důkaz lze nalézt v knize Doyla a Snella):

Věta : Graf je přechodný právě tehdy, když je odpor mezi bodem a nekonečnem konečný. Navíc je výběr bodu nedůležitý, pokud je graf souvislý.

Jinými slovy, v přechodném systému stačí překonat konečný odpor, aby se z jakéhokoli bodu dostalo do nekonečna. V rekurentním systému je odpor mezi libovolným bodem a nekonečnem nekonečný.

Náhodná procházka po grafu je speciální případ Markovova řetězce . Na rozdíl od obecného Markovova řetězce má náhodná procházka po grafu vlastnost zvanou časová symetrie nebo reverzibilita . Zhruba řečeno, tato vlastnost, nazývaná také principem detailní rovnováhy , znamená, že pravděpodobnosti protnutí dané cesty jedním nebo druhým směrem mají mezi sebou velmi jednoduchý vztah (pokud je graf pravidelný , pak jsou stejné). Tato vlastnost má důležité důsledky.

Od 80. let 20. století bylo provedeno mnoho výzkumů zaměřených na vztah vlastností grafu k náhodným procházkám. Kromě výše popsané elektrické sítě existují také souvislosti s izoperimetrickými nerovnostmi, funkčními nerovnostmi, jako jsou Sobolevovy a Poincarého nerovnosti a vlastnostmi řešení Laplaceovy rovnice . Velká část tohoto výzkumu se zaměřila na Cayleyovy grafy finitně generovaných skupin. V mnoha případech se tyto jednotlivé výsledky přenášejí do variet a Lieových grup nebo jsou z nich odvozeny .

Pokud jde o náhodné grafy , zejména o Erdős-Rényiho model , byly získány analytické výsledky pro některé vlastnosti náhodných chodců. Zahrnují rozložení prvního [47] a posledního [48] zásahu (angl. hitting time) chodce, kde první zásah je první krok, kdy chodec poprvé vkročí na dříve navštívené místo, a poslední se shoduje s případ, kdy chodec nemá kam jít, kromě dříve navštíveného místa.

Dobrou referencí pro náhodnou procházku po grafu je tato online kniha. Pro studium skupin jsou vhodné Wössovy knihy. Pokud je samotné přechodové jádro náhodné (na základě prostředí ), pak se náhodná procházka nazývá „náhodná procházka v náhodném prostředí“. Když zákon náhodné procházky zahrnuje náhodnost , zákon se nazývá annealed (eng. annealed ); na druhé straně, je-li zákon považován za pevný, nazývá se temperovaný (eng. quenched ). $p(x,y)$ $\omega$ $\omega$ $\omega$

Můžeme zvolit každou možnou hranu grafu se stejnou pravděpodobností jako lokální maximum nejistoty (entropie). Můžeme to udělat i globálně - v maximální entropické náhodné procházce (angl. maximum entropy random walk, MERW ) je nutné, aby všechny cesty byly stejně pravděpodobné nebo jinými slovy, pro libovolné dva vrcholy byla každá cesta dané délky stejně pravděpodobné. [49] Taková chůze má mnohem silnější lokalizační vlastnosti.

Samočinné náhodné procházky

Existuje samostatný druh náhodné procházky, ve které každý krok závisí na předchozím nějakým komplexním způsobem. Analyticky se řeší obtížněji než běžné náhodné procházky; chování jakéhokoli modelu náhodného chodce však lze získat pomocí počítačů. Například:

Sebevyhýbání se bloudění. [padesáti]

Sebevyhýbající se procházka délky n je náhodná cesta o délce n kroků, začínající v počátku, která prochází pouze sousedními body a nikdy neprochází stejným bodem dvakrát. Ve dvourozměrném případě je taková cesta obvykle velmi krátká [51] , zatímco ve zvýšené dimenzi roste bez omezení. Tento model se často používá ve fyzice polymerů (od 60. let). ${\displaystyle \mathbb {Z} ^{d))$ ${\displaystyle \mathbb {Z} ^{d))$

Náhodná procházka s vymazáním kola. [52] [53]
Posílená náhodná procházka. [54]
Výzkumný proces.
Multiagentní náhodná procházka. [55]

Dlouhodobé korelované procházky

Dlouhodobé korelované časové řady se nacházejí v mnoha biologických, klimatologických a ekonomických systémech:

Záznam srdečního tepu [56]
Nekódující sekvence DNA [57]
Časová řada volatility akcií [58]
Teplotní rekordy po celém světě [59]

Korelace náhodných procházek

Náhodné procházky, při kterých směr pohybu v jednom časovém okamžiku koreluje se směrem pohybu v dalším časovém okamžiku. Používá se k simulaci pohybu zvířat. [60] [61]

Viz také

Poznámky

↑ 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 : journal. - 2016. - 8. června ( sv. XLI-B2 ). - str. 491-495 . - doi : 10.5194/isprs-archives-xli-b2-491-2016 . - .
↑ Wirth E. (2015). Pi z hraničních přechodů agenta pomocí balíčku NetLogo . Archiv knihovny Wolfram
↑ Pearson, K. Problém náhodné procházky // Příroda . - 1905. - Sv. 72 , č. 1865 . — S. 294 . - doi : 10.1038/072294b0 . — .
↑ Pal, Révész (1990) Náhodná procházka v náhodném a nenáhodném prostředí , World Scientific
↑ Kohls, Moritz; Hernandez, Tanja. Očekávané pokrytí algoritmu mobility náhodné chůze (anglicky) : journal. - 2016. - . - arXiv : 1611.02861 .
↑ Random Walk-1-Dimensional – od Wolframa MathWorld . Mathworld.wolfram.com (26. dubna 2000). Staženo: 2. listopadu 2016. (neurčitý)
↑ Edward A. Colding a kol., Modely náhodné chůze v biologii, Journal of the Royal Society Interface, 2008
↑ Kotani, M. and Sunada, T. Spektrální geometrie krystalových mřížek. — Současné. Matematika. - 2003. - T. 338. - S. 271-305. — (Současná matematika). — ISBN 9780821833834 . - doi : 10.1090/conm/338/06077 .
↑ Kotani, M. and Sunada, T. Velká odchylka a tečný kužel v nekonečnu krystalové mřížky , Math . Z. : deník. - 2006. - Sv. 254 , č.p. 4 . - S. 837-870 . - doi : 10.1007/s00209-006-0951-9 .
↑ Konstanty náhodné chůze Polia . Mathworld.wolfram.com. Staženo: 2. listopadu 2016. (neurčitý)
↑ Durrett, Rick. Pravděpodobnost: Teorie a příklady . - Cambridge University Press , 2010. - S. 191 . — ISBN 9781139491136 .
↑ Polya, George. pravděpodobnost ; kombinatoria; Výuka a učení v matematice (angličtina) . — Cambridge, Mass.: MIT Press , 1984. — S. 582–585 . — ISBN 0-262-16097-8 .
↑ Erdős, P.; Taylor, SJ Některé průnikové vlastnosti cest náhodných procházek // Acta Mathematica Academiae Scientiarum Hungaricae : journal . - 1960. - Sv. 11 , č. 3-4 . - str. 231-248 . — ISSN 0001-5954 . - doi : 10.1007/BF02020942 .
↑ MacKenzie, D. MATEMATIKA: Taking the Measure of the Wildest Dance on Earth // Science : journal. - 2000. - Sv. 290 , č.p. 5498 . - S. 1883-1884 . doi : 10.1126 / věda.290.5498.1883 . — PMID 17742050 .
↑ Chapter 2 DIFFUSION Archivováno 9. února 2015 na Wayback Machine . dartmouth.edu.
↑ Difúzní rovnice pro náhodnou procházku Archivováno 21. dubna 2015 na Wayback Machine . fyzika.uakron.edu.
↑ D. Ben-Avraham a S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems Archived 4 October 2011 at Wayback Machine , Cambridge University Press, 2000.
↑ Weiss, George H.; Rubin, Robert J. Random Walks: Theory and Selected Applications // Pokroky v chemické fyzice. - 1982. - T. 52. - S. 363-505. — ISBN 9780470142769 . - doi : 10.1002/9780470142769.ch5 .
↑ Blumen, A.; Klaafter, J.; Zumofen, G. Modely pro dynamiku reakcí v brýlích // Optická spektroskopie brýlí. - 1986. - T. 1. - S. 199-265. - (Fyzika a chemie materiálů s nízkorozměrnými strukturami). - ISBN 978-94-010-8566-3 . - doi : 10.1007/978-94-009-4650-7_5 .
↑ Alexander, S.; Orbach, R. Hustota stavů na fraktálech: "fraktony" // Journal de Physique Lettres. - 1982. - T. 43 , č. 17 . - S. 625-631 . doi : 10.1051/jphyslet : 019820043017062500 .
↑ Rammal, R.; Toulouse, G. Random chodí po fraktálních strukturách a perkolačních shlucích (anglicky) // Journal de Physique Lettres : journal. - 1983. - Sv. 44 , č. 1 . - str. 13-22 . - doi : 10.1051/jphyslet:0198300440101300 .
↑ Smoluchowski, MV Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen (německy) // Z. Phys. Chem. : prodejna. - 1917. - S. 129-168 . , Rice, SA Reakce omezené difúzí . - Elsevier , 1985. - V. 25. - (Komplexní chemická kinetika). — ISBN 978-0-444-42354-2 .
↑ Skellam, JG Random Dispersal in Theoretical Populations // Biometrika : journal. - 1951. - Sv. 38 , č. 1/2 . - str. 196-218 . - doi : 10.2307/2332328 . — PMID 14848123 . — .
↑ Skellam, JG Studies in Statistical Ecology: I. Spatial Pattern (anglicky) // Biometrika : journal. - 1952. - Sv. 39 , č. 3/4 . - str. 346-362 . - doi : 10.2307/2334030 . — .
↑ Larralde, Hernan; Trunfio, Pavel; Havlín, Šlomo; Stanley, H. Eugene; Weiss, George H. Území pokryté N difuzními částicemi // Příroda . - 1992. - Sv. 355 , č.p. 6359 . - str. 423-426 . - doi : 10.1038/355423a0 . - . , Larralde, Hernan; Trunfio, Pavel; Havlín, Šlomo; Stanley, H.; Weiss, Jiří. Počet různých míst navštívených N náhodnými chodci // Physical Review A : journal . - 1992. - Sv. 45 , č. 10 . - str. 7128-7138 . - doi : 10.1103/PhysRevA.45.7128 . - . — PMID 9906785 . ; pro postřehy týkající se problému N náhodných chodců viz Shlesinger, Michael F. Nové cesty pro náhodné chodce // Nature . - 1992. - Sv. 355 , č.p. 6359 . - str. 396-397 . - doi : 10.1038/355396a0 . — . a barevné kresby ilustrující článek.
↑ Berger, T. Informační sazby Wienerových procesů // IEEE Transactions on Information Theory : deník. - 1970. - Sv. 16 , č. 2 . - str. 134-139 . - doi : 10.1109/TIT.1970.1054423 .
↑ Risken H. (1984) The Fokker–Planck Equation . Springer, Berlín.
↑ De Gennes PG (1979) Scaling Concepts in Polymer Physics . Cornell University Press, Ithaca a Londýn.
↑ Van Kampen NG (1992) Stochastic Processes in Physics and Chemistry , přepracované a rozšířené vydání. Severní Holandsko, Amsterdam.
↑ Weiss, George H.Aspekty a aplikace náhodné procházky . - North-Holland Publishing Co., Amsterdam, 1994. - (Náhodné materiály a procesy). - ISBN 978-0-444-81606-1 .
↑ Doi M. a Edwards SF (1986) The Theory of Polymer Dynamics . Clarendon Press, Oxford
↑ Goel NW a Richter-Dyn N. (1974) Stochastic Models in Biology . Academic Press, New York.
↑ Redner S. (2001) Průvodce procesem první pasáže . Cambridge University Press, Cambridge, Spojené království.
↑ Cox D. R. (1962) Teorie obnovy . Methuen, Londýn.
↑ Jones , RAL Měkká kondenzovaná hmota . — Reprint.. — Oxford [ua]: Oxford University Press , 2004. — S. 77–78 . — ISBN 978-0-19-850589-1 .
↑ Bar-Yossef, Živ; Gurevič, Maxim. Náhodný výběr z indexu vyhledávače // Journal of the ACM : journal. - Asociace pro výpočetní techniku (ACM), 2008. - Sv. 55 , č. 5 . - str. 1-74 . — ISSN 0004-5411 . - doi : 10.1145/1411509.1411514 .
↑ Grady, L. Random walks for image segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence : deník. - 2006. - Sv. 28 , č. 11 . - S. 1768-1783 . - doi : 10.1109/TPAMI.2006.233 . — PMID 17063682 .
↑ Rucci, M; Victor, JD Nestabilní oko: Fáze zpracování informací, nikoli chyba // Trends in Neurosciences : deník. - Cell Press , 2015. - Vol. 38 , č. 4 . - S. 195-206 . - doi : 10.1016/j.tins.2015.01.005 . — PMID 25698649 .
↑ Engbert, R.; Mergenthaler, K.; Sinn, P.; Pikovsky, A. Integrovaný model fixačních očních pohybů a mikrosakád (anglicky) // Proceedings of the National Academy of Sciences of the United States of America : journal. - 2011. - Sv. 108 , č. 39 . - S. E765-70 . - doi : 10.1073/pnas.1102730108 . - . — PMID 21873243 .
↑ Nosofsky, R.M.; Palmeri, TJ Vzorový model náhodné procházky zrychlené klasifikace // Psychological Review : deník. - 1997. - Sv. 104 , č. 2 . - S. 266-300 . - doi : 10.1037/0033-295x.104.2.266 . — PMID 9127583 . Archivováno z originálu 10. prosince 2004.
↑ Codling, E. A; Plank, M. J; Benhamou, S. Náhodné modely chůze v biologii // Journal of the Royal Society Interface : deník. - 2008. - 6. srpna ( ročník 5 , č. 25 ). - S. 813-834 . - doi : 10.1098/rsif.2008.0014 . — PMID 18426776 .
↑ Gupta, Pankaj a kol. WTF: The who-to-follow system at Twitter , Sborník příspěvků z 22. mezinárodní konference o World Wide Web
↑ Karpenko A.P. Moderní algoritmy optimalizace pro vyhledávače. Algoritmy inspirované přírodou. M.: nakladatelství MSTU im. N. E. Bauman, 2014. 446 s.
↑ Stochastický algoritmus pro vysokorychlostní extrakci kapacity v integrovaných obvodech // Spolehlivost mikroelektroniky. — 1993-07. - T. 33 , č.p. 9 . - S. 1420-1421 . — ISSN 0026-2714 . - doi : 10.1016/0026-2714(93)90150-w .
↑ Je zajímavé poznamenat, že v obecném grafu se setkání dvou nezávislých náhodných chodců ne vždy redukuje na problém jediné náhodné procházky, která se vrátí do výchozího bodu.
↑ Krishnapur, Manjunath; Peres, Yuval. Opakující se grafy, kde se dvě nezávislé náhodné procházky nakonec často srazí // Elektronická komunikace v pravděpodobnosti : deník. - 2004. - Sv. 9 . - str. 72-81 . — ISSN 1083-589X . - doi : 10.1214/ECP.v9-1111 . - . — arXiv : math/0406487 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Rozdělení časů prvních zásahů náhodných procházek na sítích Erdős–Rényi // Journal of Physics A: Mathematical and Theoretical : deník. - 2017. - Sv. 50 , č. 11 . — S. 115001 . - doi : 10.1088/1751-8121/aa5af3 . — . - arXiv : 1606.01560 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Rozložení délek cest sebevyhýbajících se procházek na sítích Erdős–Rényi // Journal of Physics A: Mathematical and Theoretical : deník. - 2016. - Sv. 49 , č. 28 . — S. 285002 . - doi : 10.1088/1751-8113/49/28/285002 . - . - arXiv : 1603.06613 .
↑ Burda, Z.; Duda, J.; Štěstí, JM; Waclaw, B. Localization of the Maximal Entropy Random Walk // Physical Review Letters : journal . - 2009. - Sv. 102 , č. 16 . - S. 160602 . - doi : 10.1103/PhysRevLett.102.160602 . - . - arXiv : 0810.4113 . — PMID 19518691 .
↑ Madras, Neal a Slade, Gordon (1996) The Self-Avoiding Walk , Birkhäuser Boston. ISBN 0-8176-3891-1 .
↑ Hemmer, S.; Hemmer, PC Průměrná náhodná procházka po čtvercové mříži, která se vyhýbá, trvá 71 kroků // Journal of Chemical Physics : journal. - 1984. - Sv. 81 , č. 1 . - str. 584-585 . - doi : 10.1063/1.447349 . - .
↑ Lawler, Gregory (1996). Křižovatka náhodných procházek , Birkhäuser Boston. ISBN 0-8176-3892-X .
↑ Lawler, Gregory Conformally Invariant Processes in the Plane , book.ps .
↑ Pemantle, Robin. Průzkum náhodných procesů s výztuží // Pravděpodobnostní průzkumy : deník. - 2007. - Sv. 4 . - str. 1-79 . - doi : 10.1214/07-PS094 . — arXiv : math/0610076 .
↑ Alamgir, M a von Luxburg, U (2010). "Multi-agent random walks for local clustering on graphs" , IEEE 10th International Conference on Data Mining (ICDM) , str. 18-27.
↑ Peng, C.-K.; Mietus, J; Hausdorff, JM; Havlín, S; Stanley, H.E.; Goldberger, A.L. Antikorelace s dlouhým dosahem a negaussovské chování srdečního tepu // Phys . Rev. Lett. : deník. - 1993. - Sv. 70 , č. 9 . - S. 1343-1346 . - doi : 10.1103/PhysRevLett.70.1343 . - . — PMID 10054352 .
↑ Peng, CK; Buldyrev, SV; Goldberger, A. L.; Havlín, S; Sciortino, F; Simons, M; Stanley, H.E. Korelace dlouhého dosahu v nukleotidových sekvencích // Nature . - 1992. - Sv. 356 , č.p. 6365 . - S. 168-170 . - doi : 10.1038/356168a0 . — . — PMID 1301010 .
↑ Liu, Yanhui; Cizeau, Pierre; Meyer, Martin; Peng, C.-K.; Eugene Stanley, H. Korelace v ekonomických časových řadách // Physica A : deník. - 1997. - Sv. 245 , č.p. 3-4 . - str. 437 . - doi : 10.1016/S0378-4371(97)00368-3 . — . - arXiv : cond-mat/9706021 .
↑ Koscielny-Bunde, Eva; Bunde, Armin; Havlín, Šlomo; Roman, H. Eduardo; Goldreich, Yair; Schellnhuber, Hans-Joachim. Indikace univerzálního zákona perzistence řídící proměnlivost atmosféry // Phys . Rev. Lett. : deník. - 1998. - Sv. 81 , č. 3 . — S. 729 . - doi : 10.1103/PhysRevLett.81.729 . — .
↑ Bovet, Pierre; Benhamou, Simone. Prostorová analýza pohybu zvířat pomocí korelovaného modelu náhodné procházky // Journal of Theoretical Biology : deník. - 1988. - Sv. 131 , č.p. 4 . - str. 419-433 . - doi : 10.1016/S0022-5193(88)80038-9 .
↑ Kareiva, PM; Shigesada, N. Analýza pohybu hmyzu jako korelované náhodné procházky (anglicky) // Oecologia : journal. - 1983. - Sv. 56 , č. 2-3 . - str. 234-238 . - doi : 10.1007/BF00379695 . — . — PMID 28310199 .

Literatura

Aldous, Davide; Vyplňte, Jamesi Allene. Reverzibilní Markovovy řetězce a náhodné procházky po grafech . — 2002.
Ben-Avraham D.; Havlin S. , Diffusion and Reactions in Fractals and Disordered Systems Archived 4 October 2011 at Wayback Machine , Cambridge University Press, 2000.
Doyle, Peter G.; Snell, J. Laurie. Náhodné procházky a elektrické sítě. - Mathematical Association of America , 1984. - Vol. 22. - (Carus Mathematical Monographs). - ISBN 978-0-88385-024-4 .
Feller, William (1968), Úvod do teorie pravděpodobnosti a její aplikace (svazek 1). 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" Archivováno 4. března 2016 na Wayback Machine , Mathematische Annalen , 84(1-2):149-1921.
Révész, Pal (2013), Random Walk in Random and Non-random Environments (třetí vydání) , World Scientific Pub Co. ISBN 978-981-4447-50-8
Sunada, ToshikazuTopologická krystalografie: S výhledem na diskrétní geometrickou analýzu . - Springer, 2012. - Sv. 6. - (Průzkumy a konzultace v aplikovaných matematických vědách). — ISBN 978-4-431-54177-6 .
Weiss G. Aspects and Applications of the Random Walk , North-Holland, 1994.
Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups , Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3

Odkazy

Slovníky a encyklopedie	Velká dánština Velký Rus Britannica (online)
V bibliografických katalozích	BNF : 119358404 J9U : 987007563128805171 LCCN : sh85111357 NDL : 00571555