Tilfeldig tur

Random walk eller random walk eller random walk , forkortet på engelsk som RW ( Random Walks ), er en matematisk formalisering av banen som er resultatet av å gjøre påfølgende tilfeldige skritt. For eksempel kan banen et molekyl tar når det beveger seg gjennom en væske eller gass, banen som følges av et dyr i jakten på mat, prisen på en svingende aksje og den økonomiske situasjonen til en spiller alle behandles som tilfeldig. går. Begrepet random walk ble introdusert av Karl Pearson i 1905. [ 1 ] Resultatene av studiet av random walks har blitt brukt på mange felt som databehandling , fysikk , kjemi , økologi , biologi , psykologi eller vitenskap . [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] Spesielt i dette siste feltet, den tilfeldige vandre-teorien til Burton G. Malkiel i hans arbeid En tilfeldig spasertur nedover Wall Street er basert på hypotesen om effektive markeder, utviklet i tre former eller hypoteser. I fysikk har modellen for eksempel tjent til å modellere banen etterfulgt av et molekyl som beveger seg gjennom en væske eller gass ( Brownsk bevegelse ). I økologi brukes det til å modellere bevegelsene til et beitedyr osv. Flere forskjellige typer tilfeldige turer er av interesse. Tilfeldige turer antas ofte å være Markov-kjeder eller Markov- prosesser , men andre mer kompliserte stier er også av interesse. Noen tilfeldige turer forekommer i endelige grafer, andre i linjen, i planet eller i høyere dimensjoner, mens noen tilfeldige turer skjer i grupper.

I sin mest generelle form er random walks enhver tilfeldig prosess der posisjonen til en partikkel på et tidspunkt bare avhenger av dens posisjon på et tidligere øyeblikk og en tilfeldig variabel som bestemmer dens påfølgende retning og trinnlengde. Tilfeldige turer varierer også med hensyn til tid. Spesifikke tilfeller eller grenser for disse inkluderer beruset gange, Lévy-flyging og Brownsk bevegelse . Random walks er relatert til diffusjonsmodeller og er et grunnleggende tema i diskusjonen om Markov-prosesser. Ulike egenskaper ved tilfeldige turer inkluderer sparsomme fordelinger, første kryssingstider og møtestier.

Definisjon

La oss si at du definerer en bane som starter ved posisjon . En tilfeldig tur er modellert av følgende uttrykk: $X(t)\,$ $X(0)=X_0\,$

$X(t+\tau)=X(t)+\Phi(\tau)$

hvor er den tilfeldige variabelen som beskriver sannsynlighetsloven for å ta neste steg og er tidsintervallet mellom påfølgende trinn. Siden lengden og retningen til et gitt trinn bare avhenger av posisjon og ikke av noen tidligere posisjon, sies den tilfeldige vandringen å ha Markov-egenskapen . Vanligvis vil tonehøydefordelingen være uavhengig av posisjon eller medgått tid, en egenskap som kalles homogenitet. I alle fall er formuleringen ekstremt generell. Tilfeldige turer kan forekomme i et hvilket som helst antall dimensjoner, være partisk eller objektiv, diskrete eller kontinuerlige i tid og/eller rom, og kan krenke homogenitet på en rekke måter. $\phi$ $\tau$ $X(t)$

Tilfeldige turer i grafer

I studiet av den generelle teorien om tilfeldige turer, ser det ofte ut til at plassen der vandringen skal utføres kan modelleres som en bestemt graf. Den vanlige situasjonen er som følger: Gitt en graf og starter ved en av dens toppunkter, velger vi på en eller annen måte tilfeldig en av dens naboer og flytter til den; så velger vi en nabo til dette siste toppunktet og flytter igjen, osv. Den tilfeldige sekvensen av toppunkter oppnådd på denne måten er en tilfeldig vandring på grafen . Teorien knyttet til random walks er utviklet innenfor den generelle rammen av teorien om stokastiske prosesser, mer presist med den som er knyttet til Markov-kjeder , og ikke bare det; Det er ikke stor forskjell mellom teorien om tilfeldige turer på grafer og teorien om endelige Markov-kjeder, siden hver av disse Markov-kjedene kan sees på som en tilfeldig vandring på en eller annen rettet graf. På samme måte kan reversible Markov-kjeder sees på som tilfeldige turer i urettede grafer, og symmetriske Markov-kjeder som tilfeldige turer i vanlige grafer . $G$ $G$

Tilfeldige turer i grafer oppstår i mange modeller i matematikk og i fysikk. Faktisk er dette en av de forestillingene som begynner å dukke opp overalt når du begynner å lete etter dem. Vurder for eksempel utformingen av en kortstokk, konstruer en graf hvis toppunkter er alle permutasjonene til kortene i bunken slik at to permutasjoner er tilstøtende hvis og bare hvis den ene er hentet fra den andre ved å endre posisjonen til to av kort. Blanding av kortstokken tilsvarer en tilfeldig tur på denne grafen. [ 10 ]

Tilfeldige turer i mer generelle, om enn endelige, grafer har nylig fått mer oppmerksomhet, og aspektene som er studert er mer kvantitative: hvor langt man skal gå for å nå utgangsposisjonen, for å nå et gitt toppunkt eller for å passere gjennom alle toppunktene i grafen . Tilfeldige turer er også relatert til andre grener av grafteori ; Grunnleggende egenskaper til tilfeldige turer bestemmes av spekteret til grafen og også av den elektriske motstanden til nettverket som er naturlig forbundet med det; Dette er grunnen til at mye av terminologien som tilsvarer slike turer er gitt i termer av elektrisk nettverksteori, noe som viser seg å være ganske nyttig siden det er mulig å ekstrapolere resultater fra slik teori til tilfeldige turer i grafer og omvendt. Alle disse forbindelsene er fruktbare og gir både verktøy for studier og muligheter for å finne nye bruksområder.

Definisjon

La være en rettet graf med ikke-trivielle tilkoblede komponenter og et sett med kanter slik at med den ekstra betingelsen at den ikke har noen løkker, det vil si . La være settet av naboer av og dens grad. En funksjon symmetrisk i betydningen og hvor hvis og ellers vil bli kalt en konduktans . Som terminologien antyder, kan man forestille seg et elektron som reiser gjennom grafen der dette sammen med funksjonen ville modellere et elektrisk nettverk der toppunktene er dets noder og kantene har en elektrisk konduktans gitt av . La og hvis vi antar for hver . Markov -kjeden med tilstandsrom og overgangsmatrise gitt av: $G = (V,E)$ $E\delsett V^2$ $(x,y)\i E \iff (y,x)\i E$ $(x,x)\ikke\i E$ $N(x)=\{ y\in V : (x,y)\in E\}$ $x\i V$ $d(x) = |N(x)|$ $c: V^2\mapsto\mathbb{R}$ $c(x,y)=c(y,x)$ $c(x,y)>0$ $(x,y)\i E$ $c(x,y)=0$ $c$ $c$ $C(x)= \sum_{y\in V} c(x,y)$ $c(x)<\infty$ $x\i V$ $X=(X_n)_{n\in\mathbb{N}}$ $v$ $P$

\pi_{xy}:= P(X_{n+1}=y|X_n=x) = \displaystyle\frac{c(x,y)}{C(x)}, \mbox{ }(x,y )\i V^2

Det kalles en random walk on . Denne strengen beskriver den tilfeldige bevegelsen til en partikkel langs toppunktene til . Hvis partikkelen er i et toppunkt på et tidspunkt, vil partikkelen være ved en nabo til på neste tidspunkt, hvor naboen vil bli valgt tilfeldig i henhold til konduktans. Når det gjelder et elektrisk nettverk, vil partikkelen mer presist være et elektron . Merk at ved å multiplisere konduktansen med en positiv konstant, er det ingen endring i den tilhørende tilfeldige vandringen. $G$ $G$ $x\i V$ $x$ $c$

Symmetrisk tilfeldig gåtur

Forutsatt at hver kant har samme konduktans, det vil si at hvert toppunkt har en endelig grad. Deretter

$C(x) = c \cdot d(x) \mbox{ for hver } x\i V$
Overgangsmatrisen er gitt av:

$\pi_{xy} = \begin{cases} 1/d(x), & \mbox{if }y\in N(x) \\ 0, & \mbox{if }y\not\in N(x) \end{cases}$

En kjede som den som er beskrevet ovenfor, der hvis partikkelen er i et toppunkt den har samme sannsynlighet for å flytte til hver nabo av , kalles en symmetrisk tilfeldig walk in . $x$ $x$ $G$

Tilfeldige turer på rutenett

De tilfeldige turene på rutenettene med er spesielt interessante. Tenk først på den enkle tilfeldige vandringen med overgangssannsynligheter: $\mathbb{Z}^k$ $k\in\mathbb{N}^{+}$ $X=(X_n)_{n\in\mathbb{N}}$ $\mathbb{Z}$

$\pi_{xy} = P(X_{n+1} = y|X_n = x) = \begin{cases} p, & \mbox{if }y = x+1 \\ 1-p, & \mbox{ hvis }y = x-1 \\ 0, og \mbox{else}\\ \end{cases}$

hvor er en parameter. Merk at kjeden som er definert på denne måten er irreduserbar . Videre er kjeden periodisk med periode 2 (siden kjeden er irreduserbar er det nok å sjekke om perioden på 0 er 2): [ 11 ] Siden start ved toppunkt 0 kan kjeden bare nå 0 igjen med et antall trinn og kjeden går tilbake til 0 i tide hvis og bare hvis det er trinn til høyre og n trinn til venstre da $p\in (0,1)$ $2n$ $n$

\pi_{00}^{(2n)} = \displaystyle\binom{2n}{n}p^n(1-p)^n \mbox{ y } \pi_{00}^{(2n-1)} =0 \mbox{ for alle } n\geq 1

Fra dette er det oppnådd ved å bruke Stirling-formelen og dermed hvis eller det som er det samme som 0 er forbigående og siden kjeden er irreduserbar, viser det seg å være forbigående. Tvert imot, hvis , og 0 er rekursivt, det samme er strengen . [ 11 ] Således, for det tilfellet hvor er den symmetriske gå på , vil en partikkel som starter fra et hvilket som helst toppunkt på et tidspunkt gå tilbake til den. $\pi_{00}^{(2n)} \ca. \frac{1}{\sqrt{\pi n}}(4p(1-p))^n$ $\pi_{00}^{*} = \sum_{n=0}^\infty \pi_{00}^{(2n)} < \infty$ $p\nekv 1/2$ $X$ $p = 1/2$ $\pi_{00}^{*} = \sum_{n=0}^\infty \pi_{00}^{(2n)} = \infty$ $X$ $p = 1/2$ $X$ $\mathbb{Z}$

Anta at vi tegner et merke i en viss avstand fra opprinnelsen til turen. Hvor mange ganger vil den tilfeldige vandringen krysse et slikt merke? Løsningen er følgende teorem (som utvider det ovennevnte): for enhver endimensjonal tilfeldig vandring vil hvert punkt i definisjonsdomenet til en funksjon nesten helt sikkert bli krysset et uendelig antall ganger. (I to dimensjoner sier det analoge resultatet at enhver linje vil bli krysset et uendelig antall ganger.) Dette problemet har forskjellige navn: crossover-problemet, gjentakelsesproblemet eller gamblerens ruinproblem. Opprinnelsen til dette etternavnet er følgende: Hvis en spiller med en begrenset sum penger spiller et objektivt spill mot en bank med uendelig mye penger, ender han alltid opp med å tape. Spillerens pengebeløp vil gå tilfeldig mens de vinner eller taper, og vil alltid, på et tidspunkt, nå 0 og spillet vil være over.

I det generelle tilfellet vurdere med . Å være enhetsvektoren med en 1 i posisjon og 0 ved alle andre. Den enkle tilfeldige walk-in har overgangssannsynligheter: $\mathbb{Z}^k$ $k\in\mathbb{N}^+$ $i\in\{ 1,2,\cdots ,k\}$ $e_i\in\mathbb{Z}^k$ $Yo$ $\mathbb{Z}^k$

\pi_{x,x+e_i} = p_i, \pi_{x,x-e_i} = q_i;\mbox{ } x\in\mathbb{Z}^k, \mbox{ } i\in\{ 1, 2,\cdots ,k\}

hvor , for hver og . Når den er stor, er det tydeligvis mindre sannsynlig at den kan nås igjen fra et toppunkt. Likevel er oppførselen når lik oppførselen når . Kjeden er rekursiv bare i det symmetriske tilfellet når . Når dimensjonen til er 3 eller mer, er kjeden forbigående for alle verdiene av parameterne , selv i det symmetriske tilfellet. Testene ligner på den som nettopp er utført, selv om detaljene er noe mer komplekse. Det kan du se $p_i>0$ $q_i>0$ $Yo$ $\sum_{i=1}^k (p_i+q_i) = 1$ $k$ $k=2$ $k=1$ $p_1 = q_1 = p_2 = q_2 = 1/4$ $k$ $p_i,q_i$

\pi_{00}^{(2n)} \approx \displaystyle\frac{C_k}{n^{k/2}}

hvor er en positiv konstant som avhenger av dimensjonen til . Dermed og strengen er rekursiv hvis , mens og strengen er forbigående hvis . $C_k$ $k$ $\pi_{00}^{*} = \infty$ $k\in\{ 1,2 \}$ $\pi_{00}^{*} < \infty$ $k \i \{ 3,4, \cdots \}$

Som en illustrasjon av det ovennevnte, la oss nå forestille oss en full som går tilfeldig gjennom en by hvis gater danner et firkantet rutenett. Ved hvert kryss velger den fulle en av fire mulige retninger som fører til det krysset (inkludert det han kom fra) med like stor sannsynlighet. Formelt sett ville dette vært en tilfeldig tur på . Problemet med å vite om den fulle til slutt kommer til huset ditt fra baren og går tilfeldig, har et positivt svar. Men hvis vi utfører et lignende problem med 3 eller flere dimensjoner, er dette ikke tilfelle. Med andre ord, en fugl uten peiling kan tilfeldig vandre over himmelen for alltid uten å finne reiret. $\mathbb{Z}^2$

Andre resultater

Vi går tilbake til det generelle tilfellet med en tilfeldig tur på en graf . Følgende fakta er klare: $X$ $G$

Hvis den er tilkoblet, er den irreduserbar. $G$ $X$
Hvis den er tilkoblet og begrenset, så er den rekursiv. $G$ $X$
Spesielt, hvis den ikke er tilkoblet, er de tilkoblede komponentene som er endelige tilbakevendende. $G$ $G$

Videre, forutsatt at det er en tilfeldig vandring i en tilkoblet endelig graf, er den enten aperiodisk eller har periode 2. Videre har den periode 2 hvis og bare hvis den er todelt. Det vil si at settet med toppunkter kan deles inn i sett og slik at hver kant i har et endepunkt i og et endepunkt i . $X$ $X$ $G$ $v$ $EN$ $B.$ $OG$ $EN$ $B.$

I hovedsak alle reversible Markov-kjeder kan tolkes som tilfeldige turer på grafer. Dette faktum er en av grunnene til at slike turer er av interesse, og følgende resultater oppnås:

En tilbakevendende positiv tilfeldig vandring i en graf er alltid reversibel. $X$ $G$
Omvendt, anta er en reversibel Markov-kjede med overgangsmatrise og invariant sannsynlighetstetthetsfunksjon . Anta for hver . Da kan det tolkes som en tilfeldig tur på grafen med y med konduktansfunksjon gitt av: $X$ $P$ $F$ $P_{xx}=0$ $x \i S$ $X$ $G$ $V=S$ $E =\{(x,y)\i S^2 : P_{xy}>0 \}$

\mbox{ }c(x,y) = f(x) \cdot P_{xy}, \mbox{ }(x,y) \in S^2

Applikasjoner

Noen bruksområder for den tilfeldige vandringen er:

I populasjonsgenetikk beskriver den tilfeldige vandringen de statistiske egenskapene til genetisk drift .
I fysikk brukes tilfeldige turer som forenklede modeller for Brownsk bevegelse og diffusjon, for eksempel tilfeldig bevegelse av molekyler i væsker og gasser. Se for eksempel diffusjonsbegrenset aggregering . Også tilfeldige turer og noen av de selvsamvirkende stiene spiller en rolle i kvantefeltteorien .
I matematisk biologi brukes tilfeldige turer for å beskrive individuelle dyrebevegelser, for å empirisk støtte biodiffusjonsprosesser , og noen ganger for å utvikle populasjonsdynamikk .
I andre felt av matematikk brukes den tilfeldige vandringen til å beregne løsningene av Laplaces ligning , for å estimere det harmoniske gjennomsnittet , og for ulike konstruksjoner innen analyse og kombinatorikk .
I databehandling brukes tilfeldige turer for å estimere størrelsen på nettet . På World Wide Web-konferansen-2006 , Bar-Yossef et al. publiserte sine oppdagelser og algoritmer for det samme.
I bildebehandling brukes tilfeldige turer for å bestemme etikettene (dvs. "objekt" eller "bakgrunn") som skal assosieres med hver piksel. Denne algoritmen blir ofte referert til som den tilfeldige gangsegmenteringsalgoritmen.

Forhold til Brownsk bevegelse

Når i en endimensjonal tilfeldig vandring (som ) trinnlengden reduseres til svært små verdier , oppnås en Wiener-prosess , en stokastisk prosess som oppfører seg som en Brownsk bevegelse . $\mathbb{Z}$

For å være mer presis, hvis trinnlengden er ε, må gåturen ha lengde L /ε² for å tilnærme en wienergang med lengde L . [ 12 ] Etter hvert som trinnlengdegrensen nærmer seg 0 (og dermed antall trinn som trengs for å fullføre vandringen øker), konvergerer den tilfeldige vandringen til en Wiener-prosess i passende forstand. Formelt, hvis B er rommet til alle banene med lengde L med topologien til maksimumet, og hvis M er et målrom over B med den normerte topologien, så er det konvergens på M . Tilsvarende kan en wienerprosess i flere dimensjoner uttrykkes som grensen for en tilfeldig vandring i samme dimensjoner.

En tilfeldig tur er en diskret fraktal , men banen til en Wiener-prosess er en ekte fraktal , relatert til den forrige. Tenk for eksempel på en todimensjonal tilfeldig tur som berører en sirkel med radius r ganger trinnlengden. Gjennomsnittlig antall skritt turen vil ta innenfor sirkelen er r² . Dette er den diskrete versjonen av det faktum at todimensjonale Wiener-vandringer har en fraktal Hausdorff-dimensjon på 2

I to dimensjoner er gjennomsnittlig antall skritt som en tilfeldig spasertur tar i nærheten av banen . Dette tilsvarer det faktum at Wiener-prosessmiljøet er en fraktal med dimensjon 4/3, som forutsagt av Mandelbrot gjennom simuleringer, og kunne endelig bevises i år 2000. $r^{4/3}$

Referanser

^ Pearson, K. (1905). Problemet med den tilfeldige vandringen. Natur . 72 , 294.
↑ Van Kampen NG, Stokastiske prosesser i fysikk og kjemi, revidert og utvidet utgave (Nord-Holland, Amsterdam) 1992.
↑ Redner S., A Guide to First-Passage Process ( Cambridge University Press , Cambridge, Storbritannia) 2001.
↑ Goel NW og Richter-Dyn N., Stochastic Models in Biology (Academic Press, New York) 1974.
↑ Doi M. og Edwards SF, The Theory of Polymer Dynamics (Clarendon Press, Oxford) 1986
↑ De Gennes PG, Scaling Concepts in Polymer Physics (Cornell University Press, Ithaca og London) 1979.
↑ Risken H., Fokker-Planck-ligningen (Springer, Berlin) 1984.
↑ Weiss, George H. (1994), Aspects and Applications of the Random Walk , Random Materials and Processes, North-Holland Publishing Co., Amsterdam, ISBN 0-444-81606-2 , MR 1280031 ..
↑ Cox DR, Renewal Theory (Methuen, London) 1962.
↑ P. Diaconis, Group Representations in Probability and Statistics, Inst. of Math. Statistikk, Hayward, California, 1988
^ a b Blanco, Liliana (2013). sannsynlighet . National University of Colombia. ISBN 9789587195767 .
↑ Morters, Peter; Peres, Yuval (25. mai 2008). Brownsk bevegelse (PDF). Hentet 25. mai 2008.

Bibliografi

Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs , [1]

White, Liliana, Probability , National University of Colombia. ISBN 978-958-719-576-7

Doyle, Peter G.; Snell, J. Laurie (1984). Tilfeldige turer og elektriske nettverk . Carus Mathematical Monographs 22. Mathematical Association of America. [2] ( brutt lenke tilgjengelig på Internet Archive ; se historikk , første og siste versjon ). . ISBN 978-0-88385-024-4 . MR 920811

Feller, William (1968), An Introduction to Probability Theory and its Applications (Volum 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, mars 1921.

Révész, Pal (2013), Random Walk in Random and Non-random Environments (tredje utgave), World Scientific Pub Co. ISBN 978-981-4447-50-8

Rincón, Luis, Introduksjon til stokastiske prosesser [3] .

Weiss G. Aspects and Applications of the Random Walk , Nord-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

Tilfeldig tur

Definisjon

Tilfeldige turer i grafer

Definisjon

Symmetrisk tilfeldig gåtur

Tilfeldige turer på rutenett

Andre resultater

Applikasjoner

Forhold til Brownsk bevegelse

Referanser

Bibliografi

Se også

Eksterne lenker