Náhodná procházka - Random walk

Pět osmikrokových náhodných procházek z centrálního bodu. Některé cesty vypadají kratší než osm kroků, kde se trasa zdvojnásobila. ( animovaná verze )

V matematice , je náhodná procházka je matematický objekt , známý jako stochastické nebo náhodný proces , který popisuje cestu, která se skládá z posloupnosti náhodných kroků na nějaké matematické prostoru , jako jsou celá čísla .

Elementárním příkladem náhodné procházky je náhodná procházka po celé řadě čísel , která začíná na 0 a v každém kroku se pohybuje se +1 nebo -1 se stejnou pravděpodobností . Mezi další příklady patří dráha vysledovaná molekulou při jízdě v kapalině nebo plynu (viz Brownův pohyb ), vyhledávací cesta pasoucího se zvířete, cena kolísající populace a finanční situace hráče : vše lze přiblížit modely náhodných procházek, přestože ve skutečnosti nemusí být skutečně náhodné. ${\ displaystyle \ mathbb {Z}}$

Jak ilustrují tyto příklady, náhodné procházky mají uplatnění ve strojírenství a mnoha vědních oborech, včetně ekologie , psychologie , informatiky , fyziky , chemie , biologie , ekonomie a sociologie . Náhodné procházky vysvětlují pozorované chování mnoha procesů v těchto polích, a slouží tak jako základní model pro zaznamenanou stochastickou aktivitu. Jako matematičtější aplikaci lze hodnotu $π$ aproximovat použitím náhodné procházky v modelovacím prostředí založeném na agentech . Pojem náhodná procházka poprvé zavedl Karl Pearson v roce 1905.

Zajímavé jsou různé druhy náhodných procházek, které se mohou lišit v několika ohledech. Samotný termín nejčastěji odkazuje na zvláštní kategorii Markovových řetězců , ale mnoho časově závislých procesů je označováno jako náhodné procházky, přičemž modifikátor označuje jejich specifické vlastnosti. Náhodné procházky (Markov nebo ne) mohou také probíhat na různých prostorech: běžně zkoumané zahrnují grafy , jiné na celá čísla nebo na skutečnou čáru, v rovině nebo ve vícerozměrných vektorových prostorech, na zakřivených plochách nebo ve vyšší dimenzi Riemannian rozdělovače , a také na skupiny konečné, konečně generované nebo lež . S parametrem času lze také manipulovat. V nejjednodušším kontextu je chůze v diskrétním čase, to je sekvence náhodných proměnných $(X t) = (X 1, X 2, ...)$ indexováno přirozenými čísly. Je však také možné definovat náhodné procházky, které provádějí své kroky v náhodných časech, a v takovém případě pozici $X t$ musí být definována pro všechny časy $t \in [0,+\infty)$ . Specifické případy nebo limity náhodných procházek zahrnují Lévyho letové a difúzní modely, jako je Brownův pohyb .

Náhodné procházky jsou základním tématem v diskusích o Markovových procesech. Jejich matematické studium bylo rozsáhlé. Aby bylo možné kvantifikovat jejich chování, bylo zavedeno několik vlastností, včetně distribuce rozptylu, doby prvního průchodu nebo zasažení, rychlosti setkání, opakování nebo pomíjivosti.

Náhodná procházka mříží

Populární model náhodné procházky je model náhodné procházky po pravidelné mřížce, kde v každém kroku umístění přeskočí na jiné místo podle určitého rozdělení pravděpodobnosti. Při jednoduché náhodné procházce může místo přeskočit pouze na sousední místa mřížky a vytvořit mřížovou cestu . V jednoduché symetrické náhodné procházce po místně konečné mřížce jsou pravděpodobnosti umístění, které skočí na každého z jeho bezprostředních sousedů, stejné. Nejlepší studovaný příklad je náhodná procházka po d -dimenzionální celočíselné mřížce (někdy se jí říká hyperkubická mřížka) . ${\ displaystyle \ mathbb {Z} ^{d}}$

Pokud je stavový prostor omezen na konečné rozměry, model náhodného procházení se nazývá jednoduchá ohraničená symetrická náhodná procházka a pravděpodobnosti přechodu závisí na umístění stavu, protože na okrajových a rohových stavech je pohyb omezený.

Jednorozměrná náhodná procházka

Elementárním příkladem náhodné procházky je náhodná procházka po celé řadě čísel , která začíná na 0 a v každém kroku se pohybuje se +1 nebo -1 se stejnou pravděpodobností. ${\ displaystyle \ mathbb {Z}}$

Tuto procházku lze ilustrovat následovně. Na číselné ose je umístěna značka na nulu a férová mince je převrácena. Pokud dopadne na hlavy, značka se přesune o jednu jednotku doprava. Pokud dopadne na ocasy, značka se přesune o jednu jednotku doleva. Po pěti otočeních může být značka nyní na -5, -3, -1, 1, 3, 5. S pěti otočkami, třemi hlavami a dvěma ocasy v libovolném pořadí přistane na 1. Existuje 10 způsobů přistání na 1 (převrácením tří hlav a dvou ocasů), 10 způsobů přistání na -1 (převrácením tří ocasů a dvou hlav), 5 způsobů přistání na 3 (převrácením čtyř hlav a jednoho ocasu), 5 způsobů přistání na −3 (převrácením čtyř ocasů a jedné hlavy), 1 způsob přistání na 5 (převrácením pěti hlav) a 1 způsob přistání na −5 (převrácením pěti ocasů). Na obrázku níže najdete ilustraci možných výsledků 5 otočení.

Všechny možné výsledky náhodných procházek po 5 hodech férovou mincí

Náhodná procházka ve dvou dimenzích ( animovaná verze )

Náhodná procházka ve dvou dimenzích s 25 tisíci kroky ( animovaná verze )

Náhodná procházka ve dvou dimenzích se dvěma miliony ještě menších kroků. Tento obrázek byl vytvořen tak, že body, které jsou častěji procházeny, jsou tmavší. V mezích, pro velmi malé kroky, člověk získá Brownův pohyb .

Pro definování tohoto chůze formálně, se nezávislé náhodné proměnné , kde každá proměnná je buď 1 nebo -1, s 50% pravděpodobností buď pro hodnotu a sadou a série se nazývá jednoduché náhodné procházky na . Tato řada (součet posloupnosti −1s a 1s) udává čistou ujetou vzdálenost, pokud má každá část chůze délku jedna. Očekávání z je nula. To znamená, že průměr všech mincí se blíží nule, jak se počet flipů zvyšuje. Následuje vlastnost konečné aditivity očekávání: ${\ displaystyle Z_ {1}, Z_ {2}, \ tečky}$ ${\ displaystyle S_ {0} = 0 \, \!}$ ${\ Displaystyle S_ {n} = \ sum _ {j = 1}^{n} Z_ {j}.}$ ${\ displaystyle \ {S_ {n} \} \, \!}$ ${\ displaystyle \ mathbb {Z}}$ ${\ displaystyle E (S_ {n}) \, \!}$ ${\ displaystyle S_ {n} \, \!}$

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

Podobný výpočet s využitím nezávislosti náhodných proměnných a skutečnosti, že ukazuje, že: ${\ Displaystyle E (Z_ {n}^{2}) = 1}$

{\ Displaystyle 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.}

To naznačuje , že očekávaná translační vzdálenost po n krocích by měla být řádově . Ve skutečnosti, ${\ Displaystyle E (| S_ {n} |) \, \!}$ ${\ displaystyle {\ sqrt {n}}}$

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

Tento výsledek ukazuje, že difúze je pro míchání neúčinná kvůli tomu, jak se odmocnina chová pro velké . ${\ displaystyle N}$

Kolikrát náhodná procházka překročí hraniční čáru, pokud je dovoleno pokračovat v chůzi navždy? Jednoduchá náhodná procházka překročí každý bod nekonečně mnohokrát. Tento výsledek má mnoho jmen: fenomén přejezdu , opakování nebo zkáza hazardního hráče . Důvod příjmení je následující: hazardní hráč s omezeným množstvím peněz nakonec prohraje, když hraje férovou hru proti bance s nekonečným množstvím peněz. Peníze hazardního hráče provedou náhodnou procházku a v určitém okamžiku dosáhnou nuly a hra skončí. ${\ displaystyle \ mathbb {Z}}$

Pokud a a b jsou kladná celá čísla, pak je očekávaný počet kroků, dokud jednorozměrná jednoduchá náhodná procházka začínající na 0 nejprve dosáhne b nebo- a, je ab . Pravděpodobnost, že tato procházka zasáhne b dříve - a je , což lze odvodit ze skutečnosti, že jednoduchá náhodná procházka je martingale . ${\ displaystyle a/(a+b)}$

Některé z výše uvedených výsledků lze odvodit z vlastností Pascalova trojúhelníku . Počet různých kroků n kroků, kde každý krok je +1 nebo −1, je 2 ⁿ . Pro jednoduchou náhodnou procházku je každá z těchto procházek stejně pravděpodobná. Aby se S _n rovnal číslu k , je nutné a dostatečné, aby počet +1 při chůzi překročil počet +1 při k . Z toho vyplývá, že +1 se musí objevit ( n + k )/2krát mezi n kroky chůze, proto počet procházek, které splňují, se rovná počtu způsobů výběru ( n + k )/2 prvků ze sady n prvků, označených . Aby to mělo význam, je nutné, aby n + k bylo sudé číslo, což znamená, že n a k jsou buď sudá, nebo obě lichá. Proto je pravděpodobnost, která se rovná . Představením záznamů Pascalova trojúhelníku z hlediska faktoriálů a použitím Stirlingova vzorce lze získat dobré odhady těchto pravděpodobností pro velké hodnoty . ${\ displaystyle S_ {n} = k}$ ${\ displaystyle n \ choose (n+k)/2}$ ${\ displaystyle S_ {n} = k}$ ${\ Displaystyle 2^{-n} {n \ choose (n+k)/2}}$ ${\ displaystyle n}$

Pokud je prostor pro stručnost omezen na +, může být počet způsobů, kterými náhodná procházka přistane na daném čísle s pěti převráceními, zobrazen jako {0,5,0,4,0,1}. ${\ displaystyle \ mathbb {Z}}$

Tento vztah s Pascalovým trojúhelníkem je demonstrován pro malé hodnoty n . Při nulových zatáčkách bude jedinou možností zůstat na nule. V jedné zatáčce však existuje jedna šance na přistání na −1 nebo jedna šance na přistání na 1. Ve dvou zatáčkách se značka na 1 mohla posunout na 2 nebo zpět na nulu. Značka na -1 by se mohla přesunout na -2 nebo zpět na nulu. Existuje tedy jedna šance na přistání na -2, dvě šance na přistání na nule a jedna šance na přistání na 2.

k	−5	−4	−3	−2	-1	0	1	2	3	4	5
${\ displaystyle P [S_ {0} = k]}$						1
${\ displaystyle 2P [S_ {1} = k]}$					1		1
${\ Displaystyle 2^{2} P [S_ {2} = k]}$				1		2		1
${\ Displaystyle 2^{3} P [S_ {3} = k]}$			1		3		3		1
${\ Displaystyle 2^{4} P [S_ {4} = k]}$		1		4		6		4		1
${\ Displaystyle 2^{5} P [S_ {5} = k]}$	1		5		10		10		5		1

Centrální limitní věta a zákon iterativní logaritmu popisují důležité aspekty chování jednoduchých náhodné procházky na . Zejména první znamená, že jak se n zvyšuje, pravděpodobnosti (úměrné číslům v každém řádku) se blíží normálnímu rozdělení . ${\ displaystyle \ mathbb {Z}}$

Jako přímou generalizaci lze považovat náhodné procházky po krystalových mřížích (nekonečně násobné abelian pokrývající grafy nad konečnými grafy). Ve skutečnosti je možné v tomto nastavení stanovit centrální limitní větu a větu o velkých odchylkách.

Jako řetězec Markov

Na jednorozměrnou náhodnou procházku lze také pohlížet jako na Markovův řetězec, jehož stavový prostor je dán celými čísly. U určitého počtu p uspokojujících jsou uvedeny pravděpodobnosti přechodu (pravděpodobnost P _{i, j} přechodu ze stavu i do stavu j ) podle ${\ Displaystyle i = 0, \ pm 1, \ pm 2, \ tečky.}$ ${\ displaystyle \, 0 <p <1}$

{\ Displaystyle \, P_ {i, i+1} = p = 1-P_ {i, i-1}.}

Heterogenní generalizace

Vyšší rozměry

Tři náhodné procházky ve třech dimenzích

Ve vyšších dimenzích má množina náhodně kráčených bodů zajímavé geometrické vlastnosti. Ve skutečnosti člověk získá diskrétní fraktál , tj. Množinu , která ve velkých měřítcích vykazuje stochastickou podobnost . Na malých měřítcích lze pozorovat „zubatost“ vyplývající z mřížky, na které se chůze provádí. Dobrým zdrojem na toto téma jsou dvě níže uvedené knihy Lawlera. Trajektorie náhodné procházky je souhrn navštívených bodů, považovaný za soubor bez ohledu na to, kdy procházka dorazila do bodu. V jedné dimenzi jsou trajektorií jednoduše všechny body mezi minimální výškou a maximální výškou dosažené chůze (oba jsou v průměru řádově ). ${\ displaystyle {\ sqrt {n}}}$

Pro představu dvojrozměrného případu si lze představit osobu, která náhodně kráčí po městě. Město je efektivně nekonečné a uspořádané do čtvercové mřížky 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ůvodně cestoval). Formálně se jedná o náhodnou procházku po sadě všech bodů v rovině s celočíselnými souřadnicemi .

Vrátí se ten člověk někdy do původního výchozího bodu procházky? Toto je 2-dimenzionální ekvivalent výše uvedeného problému přejezdu. V roce 1921 George Pólya dokázal, že osoba téměř jistě půjde na 2-dimenzionální náhodnou procházku, ale pro 3 dimenze nebo vyšší se pravděpodobnost návratu k původu snižuje se zvyšujícím se počtem dimenzí. Ve 3 dimenzích klesá pravděpodobnost zhruba na 34%. Matematik Shizuo Kakutani byl známý tím, že na tento výsledek odkazoval následujícím citátem: „Opilý člověk najde cestu domů, ale opilý pták se může navždy ztratit“.

Další variace této otázky, kterou si položil i Pólya, zní: pokud dva lidé opustí stejné výchozí místo, setkají se tedy ještě někdy? Je možné ukázat, ž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ě znovu setkají v 2-dimenzionální procházce, ale pro 3 dimenze a vyšší pravděpodobnost klesá s počtem rozměry. Paul Erdős a Samuel James Taylor v roce 1960 také ukázali, že pro rozměry menší nebo rovné 4 mají dvě nezávislé náhodné procházky začínající z jakýchkoli dvou daných bodů nekonečně mnoho křižovatek téměř jistě, ale u dimenzí vyšších než 5 se téměř jistě protínají jen konečně často .

Asymptotická funkce pro dvojrozměrnou náhodnou procházku, jak se zvyšuje počet kroků, je dána Rayleighovou distribucí . Rozdělení pravděpodobnosti je funkcí poloměru od počátku a délka kroku je pro každý krok konstantní.

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

Vztah k Wienerově procesu

Simulované kroky sbližování Wienerova procesu ve dvou dimenzích

Wiener proces je stochastický proces podobné chování na Brownova pohybu , fyzikální jev minutu částice difundující do kapaliny. (Někdy je Wienerův proces nazýván „Brownovým pohybem“, ačkoli toto je striktně řečeno záměna modelu s modelovaným jevem.)

Wienerův proces je limitem měřítka náhodné procházky v dimenzi 1. To znamená, že pokud se vydáte náhodnou procházkou s velmi malými kroky, získáte přiblížení k Wienerovu procesu (a méně přesně k Brownovu pohybu). Přesněji řečeno, v případě, že velikost kroku je ε, je třeba, aby se projít délky L / ε ² aproximovat délku Wiener z L . Vzhledem k tomu, že velikost kroku má tendenci k 0 (a počet kroků se úměrně zvyšuje), náhodné procházení konverguje k procesu Wiener ve vhodném smyslu. Formálně, pokud B je prostor všech cest délky L s maximálním topologie, a pokud M je prostor opatření nad B s topologií normy, pak je konvergence v prostoru M . Podobně Wienerův proces v několika dimenzích je limit škálování náhodné procházky ve stejném počtu dimenzí.

Náhodná procházka je diskrétní fraktál (funkce s celočíselnými dimenzemi; 1, 2, ...), ale trajektorie Wienerova procesu je skutečný fraktál a mezi nimi existuje spojení. Například udělejte náhodnou procházku, dokud nenarazí na kruh o poloměru r násobku délky kroku. Průměrný počet kroků, které provede, je r ² . Tato skutečnost je diskrétní verzí skutečnosti, že procházka Wienerovým procesem je fraktálem Hausdorffovy dimenze 2.

Ve dvou dimenzích je průměrný počet bodů, které má stejná náhodná procházka na hranici své trajektorie, r ^4/3 . To odpovídá skutečnosti, že hranicí trajektorie Wienerova procesu je fraktál dimenze 4/3, což je skutečnost, kterou Mandelbrot předpovídal pomocí simulací, ale dokázal ji až v roce 2000 Lawler , Schramm a Werner .

Proces Wiener má mnoho symetrií, náhodná procházka ne. Procházka Wienerovým procesem je například invariantní vůči rotacím, ale náhodná procházka není, protože podkladová mřížka není (náhodná procházka je invariantní vůči rotacím o 90 stupňů, ale Wienerovy procesy jsou invariantní vůči rotacím například o 17 stupňů také). To znamená, že v mnoha případech lze problémy na náhodné procházce snáze vyřešit tak, že je převedete do Wienerova procesu, tam problém vyřešíte a poté přeložíte zpět. Na druhou stranu některé problémy lze díky své diskrétní povaze snadněji vyřešit náhodnými procházkami.

Náhodné procházky a Wienerovy procesy mohou být spojeny , konkrétně se projevují na stejném pravděpodobnostním prostoru závislým způsobem, který je nutí být docela blízko. Nejjednodušší takovou spojkou je Skorokhodovo vložení, ale existují přesnější spojky, jako například aproximační věta Komlós – Major – Tusnády .

Konvergence náhodné procházky směrem k Wienerovu procesu je řízena centrální limitní větou a Donskerovou větou . U částice ve známé pevné poloze při t = 0 nám centrální limitní věta říká, že po velkém počtu nezávislých kroků v náhodné chůzi je pozice chodce rozdělena podle normálního rozdělení celkové variance :

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

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

To odpovídá funkci Greena na difúzní rovnice , které řídí Wiener proces, což naznačuje, že po velkém počtu kroků, o náhodné procházky konverguje směrem k procesu Wiener.

Ve 3D je rozptyl odpovídající Greenově funkci difúzní rovnice:

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

Vyrovnáváním této veličiny s rozptylem spojeným s polohou náhodného chodce se získá ekvivalentní difúzní koeficient, který je třeba vzít v úvahu u asymptotického Wienerova procesu, ke kterému se náhodná procházka sbíhá po velkém počtu kroků:

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

(platí pouze ve 3D).

Poznámka: výše uvedené dva výrazy rozptylu odpovídají distribuci spojené s vektorem, který spojuje dva konce náhodné procházky, ve 3D. Rozptyl spojený s každou komponentou , nebo je pouze jednou třetinou této hodnoty (stále ve 3D). ${\ displaystyle {\ vec {R}}}$ ${\ displaystyle R_ {x}}$ ${\ displaystyle R_ {y}}$ ${\ displaystyle R_ {z}}$

Pro 2D:

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

Pro 1D:

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

Gaussova náhodná procházka

Náhodná procházka s velikostí kroku, která se mění podle normální distribuce, se používá jako model pro data reálných časových řad, jako jsou finanční trhy. Například Black -Scholesův vzorec pro modelování cen opcí používá jako základní předpoklad Gaussovu náhodnou chůzi.

Velikost kroku je zde inverzní kumulativní normální rozdělení, kde 0 ≤ z ≤ 1 je rovnoměrně rozdělené náhodné číslo a μ a σ jsou průměr a standardní odchylky normálního rozdělení. ${\ Displaystyle \ Phi ^{-1} (z, \ mu, \ sigma)}$

Pokud μ je nenulové, náhodná procházka se bude lišit o lineární trend. Pokud v _s je počáteční hodnota náhodné procházky, očekávaná hodnota po n krocích bude v _s + n μ.

Pro speciální případ, kde μ je roven nule, je po n krocích rozdělení pravděpodobnosti translační vzdálenosti dáno N (0, n σ ² ), kde N () je zápis normálního rozdělení, n je počet kroků , a σ je z inverzního kumulativního normálního rozdělení, jak je uvedeno výše.

Důkaz: Gaussovu náhodnou chůzi lze považovat za součet posloupnosti nezávislých a identicky rozložených náhodných proměnných, X _i z inverzního kumulativního normálního rozdělení s průměrem rovným nule a σ původního inverzního kumulativního normálního rozdělení:

Z = ,

{\ displaystyle \ 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 proměnných, Z = X + Y, je dáno vztahem

{\ displaystyle {\ mathcal {N}}}

(μ _X + μ _Y , σ ²_X + σ ²_Y ) (viz zde) .

V našem případě, μ _X = μ _Y = 0 a σ ²_X = σ ²_Y = σ ² výnos

{\ displaystyle {\ mathcal {N}}}

(0, 2σ ² )

Indukcí pro n kroků máme

Z ~ (0, n σ ² ).

{\ displaystyle {\ mathcal {N}}}

Pro kroky distribuované podle libovolného rozdělení s nulovým průměrem a konečným rozptylem (ne nutně jen s normálním rozložením) je střední průměrná čtvercová translační vzdálenost po n krocích

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

Ale pro Gaussovu náhodnou procházku je to jen standardní odchylka distribuce překladové vzdálenosti po n krocích. Pokud je tedy μ rovno nule, a protože je translační vzdálenost odmocniny (RMS) jedna standardní odchylka, existuje 68,27% pravděpodobnost, že vzdálenost translace RMS po n krocích klesne mezi ± σ . Stejně tak je 50% pravděpodobnost, že se translační vzdálenost po n krocích bude pohybovat mezi ± 0,6745σ . ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle {\ sqrt {n}}}$

Anomální difúze

V neuspořádaných systémech, jako jsou porézní média a fraktály, nemusí být úměrné, ale . Exponent se nazývá exponent anomální difúze a může být větší nebo menší než 2. Anomální difúzi lze také vyjádřit jako σ _r² ~ Dt ^α, kde α je parametr anomálie. Některé difúze v náhodném prostředí jsou dokonce úměrné mocnině logaritmu doby, viz například Sinajská procházka nebo Broxova difúze. ${\ Displaystyle \ sigma ^{2}}$ ${\ displaystyle t}$ ${\ displaystyle t^{2/d_ {w}}}$ ${\ displaystyle d_ {w}}$

Počet odlišných webů

Počet různých míst navštívených jediným náhodným chodcem byl rozsáhle studován pro čtvercové a krychlové mříže a pro fraktály. Toto množství je užitečné pro analýzu problémů odchytových a kinetických reakcí. Souvisí to také s vibrační hustotou stavů, procesy difuzních reakcí a šířením populací v ekologii. Zobecnění tohoto problému na počet odlišných míst navštívených náhodnými chodci bylo nedávno studováno pro d-dimenzionální euklidovské mříže. Počet odlišných míst navštívených N chodci nesouvisí jednoduše s počtem odlišných míst, která každý chodec navštívil. ${\ Displaystyle S (t)}$ ${\ displaystyle N}$ ${\ displaystyle S_ {N} (t)}$

Informační rychlost

Informace o rychlosti z Gaussova náhodné procházky s ohledem na druhou mocninou vzdálenosti chyb, tedy jeho kvadratická rychlost funkce zkreslení , je dána tím, parametricky

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

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

kde . Proto není možné kódovat pomocí binárního kódu menšího než bitů a obnovit jej s očekávanou průměrnou čtvercovou chybou menší než . Na druhou stranu pro každého existuje dostatečně velký a binární kód, který neobsahuje více než odlišné prvky, takže očekávaná průměrná čtvercová chyba při obnově z tohoto kódu je nanejvýš . ${\ Displaystyle S (\ varphi) = \ left (2 \ sin (\ pi \ varphi /2) \ right)^{-2}}$ ${\ displaystyle {\ {Z_ {n} \} _ {n = 1}^{N}}}$ ${\ displaystyle NR (D _ {\ theta})}$ ${\ displaystyle D _ {\ theta}}$ ${\ displaystyle \ varepsilon> 0}$ ${\ displaystyle N \ in \ mathbb {N}}$ ${\ Displaystyle 2^{NR (D _ {\ theta})}}$ ${\ displaystyle {\ {Z_ {n} \} _ {n = 1}^{N}}}$ ${\ Displaystyle D _ {\ theta}-\ varepsilon}$

Aplikace

Antony Gormley ‚s Quantum Cloud socha v Londýně, byl navržen na počítači pomocí náhodného algoritmu chůze.

Jak již bylo zmíněno, rozsah přírodních jevů, které byly podrobeny pokusům o popis nějakou příchutí náhodných procházek, je značný, zejména ve fyzice a chemii, materiálových vědách , biologii a různých dalších oblastech. Následuje několik konkrétních aplikací náhodné procházky:

Ve finanční ekonomii se k modelování cen akcií a dalších faktorů používá hypotéza „ náhodné chůze “. Empirické studie zjistily určité odchylky od tohoto teoretického modelu, zejména v krátkodobých a dlouhodobých korelacích. Viz ceny akcií .
V populační genetice popisuje náhodná procházka statistické vlastnosti genetického driftu
Ve fyzice , náhodné procházky se používají jako zjednodušené modely fyzického Brownova pohybu a šíření, jako je například náhodný pohyb části molekul v kapalinách a plynech. Viz například agregace omezená na difúzi . Také ve fyzice hrají v kvantové teorii pole roli náhodné procházky a některé samostatně interagující procházky .
V matematické ekologii se náhodné procházky používají k popisu jednotlivých pohybů zvířat, k empirickému podpoření procesů biodifúze a příležitostně k modelování dynamiky populace .
V polymerní fyzice popisuje náhodná procházka ideální řetězec . Jedná se o nejjednodušší model pro studium polymerů .
V jiných oblastech matematiky se náhodná procházka používá k výpočtu řešení Laplaceovy rovnice , k odhadu harmonické míry a pro různé konstrukce v analýze a kombinatorice .
V informatice se k odhadování velikosti webu používají náhodné procházky .
Při segmentaci obrazu jsou k určení popisků (tj. „Objektu“ nebo „pozadí“), které mají být přiřazeny ke každému pixelu, použity náhodné procházky. Tento algoritmus se obvykle označuje jako algoritmus segmentace náhodných chodců .

Ve všech těchto případech je Brownův pohyb často nahrazen náhodnou chůzí.

Při výzkumu mozku se k modelování kaskád palby neuronů v mozku používají náhodné procházky a zesílené náhodné procházky.
Ve vědě o zraku se oční drift chová jako náhodná procházka. Podle některých autorů jsou fixační pohyby očí obecně také dobře popsány náhodnou procházkou.
V psychologii náhodné procházky přesně vysvětlují vztah mezi časem potřebným k rozhodnutí a pravděpodobností, že určité rozhodnutí bude učiněno.
Náhodné procházky lze použít k vzorkování ze stavového prostoru, který je neznámý nebo velmi velký, například k výběru náhodné stránky z internetu nebo pro výzkum pracovních podmínek náhodného pracovníka v dané zemi.

Když se tento poslední přístup používá v informatice , je známý jako Markovův řetězec Monte Carlo nebo zkráceně MCMC. Vzorkování z nějakého komplikovaného stavového prostoru také často umožňuje získat pravděpodobnostní odhad velikosti prostoru. Odhad trvalosti velké matice nul a jedniček byl prvním zásadním problémem řešeným pomocí tohoto přístupu.

Náhodné procházky byly také použity k vzorkování rozsáhlých online grafů, jako jsou služby sociálních sítí .
V bezdrátových sítích se k modelování pohybu uzlů používá náhodná procházka.
Pohyblivé bakterie se zapojují do zkreslené náhodné procházky .
K modelování hazardu slouží náhodné procházky .
Ve fyzice jsou náhodné procházky základem metody Fermiho odhadu .
Web na Twitteru pomocí náhodných procházek navrhuje, koho sledovat
Dave Bayer a Persi Diaconis dokázali, že k zamíchání balíčku karet stačí 7 rifflových shufflů (více podrobností viz shuffle ). Tento výsledek se promítá do prohlášení o náhodné chůzi na symetrické skupině, což je to, co dokazují, s klíčovým využitím struktury skupiny pomocí Fourierovy analýzy.

Varianty

Byla zvažována řada typů stochastických procesů, které jsou podobné čistým náhodným procházkám, ale kde je dovoleno více zobecnit jednoduchou strukturu. Čistý struktura může být charakterizován kroky je definován nezávislými a stejně rozdělené náhodné proměnné .

Na grafech

Náhodná procházka délky k na případně nekonečném grafu G s kořenem 0 je stochastický proces s náhodnými proměnnými tak, že a je vrchol zvolený rovnoměrně náhodně od sousedů . Pak číslo je pravděpodobnost, že náhodná procházka délky k začínající na v končí na w . Zejména pokud G je graf s kořenem 0 , je pravděpodobnost, že se náhodná procházka v krocích vrátí na 0 . ${\ Displaystyle X_ {1}, X_ {2}, \ tečky, X_ {k}}$ ${\ displaystyle X_ {1} = 0}$ ${\ displaystyle {X_ {i+1}}}$ ${\ displaystyle X_ {i}}$ ${\ Displaystyle p_ {v, w, k} (G)}$ ${\ displaystyle p_ {0,0,2k}}$ ${\ displaystyle 2k}$

Na základě analogie z předchozí části o vyšších dimenzích předpokládejme nyní, že naše město již není dokonalá čtvercová mřížka. Když náš člověk dosáhne určité křižovatky, se stejnou pravděpodobností vybírá mezi různými cestami. Pokud má tedy křižovatka sedm východů, osoba půjde do každého s pravděpodobností sedmou. Toto je náhodná procházka po grafu. Dostane se naše osoba do svého domova? Ukazuje se, že za poměrně mírných podmínek je odpověď stále ano, ale v závislosti na grafu odpověď na variantní otázku „Setkají se znovu dvě osoby?“ nemusí být, že se nekonečně často setkávají téměř jistě.

Příkladem případu, kdy se osoba téměř jistě dostane do svého domova, je situace, kdy jsou délky všech bloků mezi a a b (kde a a b jsou libovolná dvě konečná kladná čísla). Všimněte si, že nepředpokládáme, že je graf planární , tj. Město může obsahovat tunely a mosty. Jedním ze způsobů, jak tento výsledek prokázat, je připojení k elektrickým sítím . Pořiďte si mapu města a na každý blok umístěte odpor jednoho ohmu . Nyní změřte „odpor mezi bodem a nekonečnem“. Jinými slovy, vyberte nějaké číslo R a vezměte všechny body v elektrické síti se vzdáleností větší než R od našeho bodu a spojte je dohromady. Toto je nyní konečná elektrická síť a můžeme měřit odpor od našeho bodu k drátovým bodům. Vezměte R do nekonečna. Hranice se nazývá odpor mezi bodem a nekonečnem . Ukazuje se, že platí následující (elementární důkaz najdete v knize Doyla a Snella):

Věta : graf je přechodný právě tehdy, když je odpor mezi bodem a nekonečnem konečný. Není důležité, který bod je vybrán, pokud je graf propojen.

Jinými slovy, v přechodném systému musí člověk překonat pouze konečný odpor, aby se dostal do nekonečna z jakéhokoli bodu. V opakujícím se systému je odpor od jakéhokoli bodu k nekonečnu nekonečný.

Tato charakteristika pomíjivosti a opakování je velmi užitečná a konkrétně nám umožňuje analyzovat případ města nakresleného v rovině s ohraničenými vzdálenostmi.

Náhodná procházka grafem je velmi zvláštním případem 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é princip detailní rovnováhy , znamená, že pravděpodobnosti procházení danou cestou v jednom nebo druhém směru mezi sebou mají velmi jednoduché spojení (pokud je graf pravidelný , jsou si prostě rovni). Tato vlastnost má důležité důsledky.

Počínaje osmdesátými léty se hodně zkoumalo propojení vlastností grafu s náhodnými procházkami. Kromě výše popsaného připojení k elektrické síti existují ještě důležitá spojení s izoperimetrickými nerovnostmi , více viz zde , funkční nerovnosti jako Sobolevova a Poincarého nerovnost a vlastnosti řešení Laplaceovy rovnice . Významná část tohoto výzkumu byla zaměřena na Cayley grafů z konečně generovaných skupin . V mnoha případech se tyto diskrétní výsledky přenášejí do nebo jsou odvozeny z variet a Lieových skupin .

V kontextu náhodných grafů , zejména modelu Erdős – Rényi , byly získány analytické výsledky některých vlastností náhodných chodců. Patří sem rozdělení prvního a posledního úderu chodce, kde je první doba zasažení dána prvním krokem chodce do dříve navštíveného místa grafu a poslední doba zasažení odpovídá prvnímu, kdy chodec nemůže provést další přesun bez opětovného návštěvy dříve navštíveného webu.

Dobrou referencí pro náhodné procházení grafů je online kniha od Aldous and Fill . Skupiny najdete v knize Woess. Pokud je přechodové jádro samo náhodné (na základě prostředí ), pak se náhodné procházce říká „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á žíhaný zákon; na druhou stranu, pokud je zákon považován za pevný, nazývá se zákonem uhaseným. Podívejte se na knihu Hughese, knihu Revesz nebo poznámky ze přednášky Zeitouniho. ${\ displaystyle p (x, y)}$ ${\ displaystyle \ omega}$ ${\ displaystyle \ omega}$ ${\ displaystyle \ omega}$

Můžeme přemýšlet o výběru každé možné hrany se stejnou pravděpodobností, jako je maximalizace lokální nejistoty (entropie). Mohli bychom to také udělat globálně - při maximální entropii náhodné chůze (MERW) chceme, aby všechny cesty byly stejně pravděpodobné, nebo jinými slovy: pro každé dva vrcholy je každá cesta dané délky stejně pravděpodobná. Tato náhodná procházka má mnohem silnější lokalizační vlastnosti.

Samoobslužné náhodné procházky

Existuje řada zajímavých modelů náhodných cest, ve kterých každý krok složitě závisí na minulosti. Všechny jsou pro analytické řešení složitější než obvyklá náhodná procházka; chování jakéhokoli modelu náhodného chodce lze přesto získat pomocí počítačů. Mezi příklady patří:

Self-vyhnout chůze .

Vlastní vyhnout chůze délky n o je náhodná n -Step cesta, která začíná na počátku, je přechod pouze mezi sousedními míst v , nikdy znovu stránky, a je vybráno rovnoměrně ze všech těchto cest. Ve dvou dimenzích je díky sebepasti typická procházka bez sebe velmi krátká, zatímco ve vyšší dimenzi roste za všemi hranicemi. Tento model byl často používán ve fyzice polymerů (od 60. let 20. století). ${\ displaystyle \ mathbb {Z} ^{d}}$ ${\ displaystyle \ mathbb {Z} ^{d}}$

Dálkově korelované procházky

Korelované časové řady s dlouhým dosahem se nacházejí v mnoha biologických, klimatologických a ekonomických systémech.

Záznamy prezenčního signálu
Nekódující sekvence DNA
Časová řada volatility akcií
Teplotní rekordy po celém světě

Zkreslené náhodné procházky po grafech

Maximální náhodná procházka entropií

Náhodná procházka zvolená pro maximalizaci rychlosti entropie má mnohem silnější lokalizační vlastnosti.

Související náhodné procházky

Náhodné procházky, kde směr pohybu v jednom okamžiku koreluje se směrem pohybu v další době. Slouží k modelování pohybů zvířat.

Viz také

Reference

Bibliografie

Aldous, David ; Fill, James Allen (2002). Reverzibilní Markovovy řetězce a náhodné procházky grafy . Archivováno od originálu dne 27. února 2019.
Ben-Avraham D .; Havlin S. , Difúze a reakce ve fraktálech a neuspořádaných systémech , Cambridge University Press, 2000.
Doyle, Peter G .; Snell, J. Laurie (1984). Náhodné procházky a elektrické sítě . Carus matematické monografie. 22 . Mathematical Association of America . arXiv : matematika.PR/0001057 . ISBN 978-0-88385-024-4. MR 0920811 .
Feller, William (1968), Úvod do teorie pravděpodobnosti a jejích aplikací (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“ , Mathematische Annalen , 84 (1–2): 149–160, March 1921.
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
Sunada, Toshikazu (2012). Topologická krystalografie: Pohled na diskrétní geometrickou analýzu . Průzkumy a výukové programy z aplikované matematické vědy. 6 . Springer. ISBN 978-4-431-54177-6.
Weiss G. Aspekty a aplikace Random Walk , Severní Holandsko, 1994.
Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups , Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3

externí odkazy

Pólya's Random Walk Constants
Náhodná procházka v Java Appletu
Kvantová náhodná procházka
Gaussův odhad náhodných procházek
Modely elektronové vodivosti využívající projekt maximální entropie, náhodné procházky, Wolframův demonstrační projekt

Languages

In other projects