Tilfældig gåtur - Random walk

Fem otte-trins tilfældige gåture fra et centralt punkt. Nogle stier vises kortere end otte trin, hvor ruten er fordoblet tilbage på sig selv. ( animeret version )

I matematik er en tilfældig gåtur et matematisk objekt , kendt som en stokastisk eller tilfældig proces , der beskriver en sti, der består af en række tilfældige trin på et matematisk rum, såsom heltal .

Et elementært eksempel på en tilfældig gåtur er den tilfældige gang på den heltallige talelinje , som starter ved 0 og ved hvert trin bevæger sig +1 eller -1 med samme sandsynlighed . Andre eksempler omfatter stien, der spores af et molekyle, når det bevæger sig i en væske eller en gas (se Brownsk bevægelse ), et foderdyrs søgesti , prisen på en svingende bestand og en gamblers økonomiske status : alt kan tilnærmes ved random walk -modeller, selvom de måske ikke er tilfældige i virkeligheden. ${\ displaystyle \ mathbb {Z}}$

Som illustreret af disse eksempler har tilfældige gåture anvendelser inden for teknik og mange videnskabelige områder, herunder økologi , psykologi , datalogi , fysik , kemi , biologi , økonomi og sociologi . Tilfældige gåture forklarer den observerede adfærd ved mange processer på disse felter og tjener således som en grundlæggende model for den registrerede stokastiske aktivitet. Som en mere matematisk applikation kan værdien af $π$ tilnærmes ved brug af en tilfældig gåtur i et agentbaseret modelleringsmiljø . Begrebet tilfældig gåtur blev først introduceret af Karl Pearson i 1905.

Forskellige typer tilfældige gåture er af interesse, som kan variere på flere måder. Selve udtrykket refererer oftest til en særlig kategori af Markov-kæder , men mange tidsafhængige processer omtales som tilfældige gåture, hvor en modifikator angiver deres specifikke egenskaber. Tilfældige gåture (Markov eller ej) kan også finde sted på en række forskellige rum: almindeligt studerede omfatter grafer , andre på heltal eller den reelle linje, i flyet eller højere dimensionelle vektorrum, på buede overflader eller højere dimensionelle Riemannian manifolds , og også på grupper endelige, endeligt genererede eller Lie . Tidsparameteren kan også manipuleres. I den enkleste kontekst går turen i diskret tid, det vil sige en sekvens af tilfældige variabler $(X t) = (X 1, X 2, ...)$ indekseret af de naturlige tal. Det er imidlertid også muligt at definere tilfældige gåture, der tager skridt på tilfældige tidspunkter, og i så fald positionen $X t$ skal defineres for alle tider $t \in [0,+\infty)$ . Specifikke tilfælde eller grænser for tilfældige gåture inkluderer Lévy -flyvning og diffusionsmodeller , såsom brunisk bevægelse .

Tilfældige gåture er et grundlæggende emne i diskussioner om Markov -processer. Deres matematiske undersøgelse har været omfattende. Adskillige egenskaber, herunder spredningsfordelinger, første passage eller slagtid, stødfrekvenser, gentagelse eller forgængelighed, er blevet indført for at kvantificere deres adfærd.

Gitter tilfældig gang

En populær random walk -model er en tilfældig gåtur på et almindeligt gitter, hvor placeringen ved hvert trin springer til et andet sted i henhold til en vis sandsynlighedsfordeling. I en simpel tilfældig gåtur kan placeringen kun hoppe til gitterets tilgrænsende steder og danne en gittersti . I en simpel symmetrisk tilfældig gåtur på et lokalt begrænset gitter er sandsynlighederne for at placeringen hopper til hver enkelt af sine nærmeste naboer de samme. Det bedst studerede eksempel er tilfældig gang på det d -dimensionelle heltal gitter (undertiden kaldet det hyperkubiske gitter) . ${\ displaystyle \ mathbb {Z} ^{d}}$

Hvis tilstandsrummet er begrænset til begrænsede dimensioner, kaldes tilfældig gå -modellen simpel kantet symmetrisk tilfældig gåtur, og overgangssandsynlighederne afhænger af statens placering, fordi bevægelsen er begrænset i margen- og hjørnetilstande.

En-dimensionel tilfældig gåtur

Et elementært eksempel på en tilfældig gåtur er den tilfældige gang på den heltallige talelinje , som starter ved 0 og ved hvert trin bevæger sig +1 eller -1 med samme sandsynlighed. ${\ displaystyle \ mathbb {Z}}$

Denne gåtur kan illustreres som følger. En markør placeres på nul på tallinjen, og en fair mønt vendes. Hvis den lander på hoveder, flyttes markøren en enhed til højre. Hvis den lander på haler, flyttes markøren en enhed til venstre. Efter fem vendinger kunne markøren nu være på -5, -3, -1, 1, 3, 5. Med fem vendinger, tre hoveder og to haler, i en hvilken som helst rækkefølge, lander den på 1. Der er 10 måder at landing på 1 (ved at vende tre hoveder og to haler), 10 måder at lande på -1 (ved at vende tre haler og to hoveder), 5 måder at lande på 3 (ved at vende fire hoveder og en hale), 5 måder at lande på på −3 (ved at vende fire haler og et hoved), 1 måde at lande på 5 (ved at vende fem hoveder) og 1 måde at lande på −5 (ved at vende fem haler). Se figuren herunder for en illustration af de mulige resultater af 5 vendinger.

Alle mulige tilfældige gangresultater efter 5 slag med en fair mønt

Tilfældig gåtur i to dimensioner ( animeret version )

Tilfældig gåtur i to dimensioner med 25 tusind trin ( animeret version )

Tilfældig gåtur i to dimensioner med to millioner endnu mindre trin. Dette billede blev genereret på en sådan måde, at punkter, der oftere krydses, er mørkere. I grænsen, for meget små trin, opnår man brunsk bevægelse .

At definere denne gang formelt tage uafhængige stokastiske variable , hvor hver variabel er enten 1 eller -1, med en 50% sandsynlighed for enten værdi, og sæt og The serien kaldes simple random walk på . Denne serie (summen af sekvensen af −1s og 1s) giver den nettodistance, der er gået, hvis hver del af turen er af en længde. Den forventning af er nul. Det vil sige, at middelværdien af alle møntflip nærmer sig nul, når antallet af vendinger stiger. Dette følger af forventningens begrænsede additivitet: ${\ displaystyle Z_ {1}, Z_ {2}, \ dots}$ ${\ 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.}

En lignende beregning, der anvender uafhængigheden af de tilfældige variabler og det faktum, at , viser at: ${\ 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.}

Dette antyder, at den forventede oversættelsesafstand efter n trin skal være af størrelsesordenen . Faktisk, ${\ displaystyle E (| S_ {n} |) \, \!}$ ${\ displaystyle {\ sqrt {n}}}$

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

Dette resultat viser, at diffusion er ineffektiv til blanding på grund af den måde, kvadratroden opfører sig for stort . ${\ displaystyle N}$

Hvor mange gange vil en tilfældig gåtur krydse en grænse, hvis det får lov at fortsætte med at gå for evigt? En simpel tilfældig gåtur vil krydse hvert punkt et uendeligt antal gange. Dette resultat har mange navne: niveauoverskridelsesfænomenet , gentagelse eller gamblerens ruin . Årsagen til efternavnet er som følger: en spiller med et begrænset beløb vil til sidst tabe, når han spiller et fair spil mod en bank med et uendeligt beløb. Gamblerens penge udfører en tilfældig gåtur, og de når på et tidspunkt nul, og spillet er slut. ${\ displaystyle \ mathbb {Z}}$

Hvis a og b er positive heltal, så er det forventede antal trin indtil en endimensionel enkel tilfældig gåtur, der starter ved 0, først rammer b eller- a er ab . Sandsynligheden for at denne gåtur vil ramme b før - a er , hvilket kan udledes af, at simpel tilfældig gåtur er en martingale . ${\ displaystyle a/(a+b)}$

Nogle af de ovennævnte resultater kan stamme fra egenskaber ved Pascals trekant . Antallet af forskellige trin på n trin, hvor hvert trin er +1 eller −1 er 2 ⁿ . For den simple tilfældige gang er hver af disse ture lige så sandsynlige. For at S _n er lig med et tal k, er det nødvendigt og tilstrækkeligt, at antallet af +1 i turen overstiger antallet af -1 med k . Det følger +1 skal vises ( n + k )/2 gange blandt n trin i en gåtur, derfor er antallet af gåture, der tilfredsstiller, lig med antallet af måder at vælge ( n + k )/2 elementer fra et n element sæt, angivet . For at dette skal have betydning, er det nødvendigt, at n + k er et lige tal, hvilket indebærer, at n og k enten er lige eller begge ulige. Derfor sandsynligheden, der er lig med . Ved at repræsentere indtastninger af Pascals trekant med hensyn til factorials og bruge Stirlings formel kan man opnå gode skøn for disse sandsynligheder for store værdier af . ${\ displaystyle S_ {n} = k}$ ${\ displaystyle n \ vælg (n+k)/2}$ ${\ displaystyle S_ {n} = k}$ ${\ displaystyle 2^{-n} {n \ vælg (n+k)/2}}$ ${\ displaystyle n}$

Hvis pladsen er begrænset til + for korthed, kan antallet af måder, hvorpå en tilfældig gåtur lander på et givet tal med fem vendinger, vises som {0,5,0,4,0,1}. ${\ displaystyle \ mathbb {Z}}$

Denne relation til Pascals trekant er demonstreret for små værdier på n . Ved nul omdrejninger vil den eneste mulighed være at forblive på nul. Men ved et sving er der en chance for at lande på −1 eller en chance for at lande på 1. Ved to sving kan en markør ved 1 flytte til 2 eller tilbage til nul. En markør på −1, kan flytte til −2 eller tilbage til nul. Derfor er der en chance for at lande på −2, to chancer for at lande på nul, og en chance for at lande på 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

Den centrale grænsesætning og loven i den itererede logaritme beskriver vigtige aspekter af adfærden ved simple tilfældige gåture . Især den første indebærer, at når n stiger, nærmer sandsynlighederne (proportionalt med tallene i hver række) en normalfordeling . ${\ displaystyle \ mathbb {Z}}$

Som en direkte generalisering kan man overveje tilfældige gåture på krystalgitter (uendeligt foldede abeliske grafer frem for endelige grafer). Faktisk er det muligt at fastslå den centrale grænsesætning og store afvigelsesteorem i denne indstilling.

Som en Markov -kæde

En endimensionel tilfældig gåtur kan også ses på som en Markov-kæde, hvis tilstandsrum er givet af heltalene For et vist antal p tilfredsstillende er overgangssandsynlighederne (sandsynligheden P _{i, j} for at flytte fra tilstand i til tilstand j ) givet ved ${\ displaystyle i = 0, \ pm 1, \ pm 2, \ prikker.}$ ${\ displaystyle \, 0 <p <1}$

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

Heterogen generalisering

Højere dimensioner

Tre tilfældige gåture i tre dimensioner

I højere dimensioner har sættet tilfældigt gåede punkter interessante geometriske egenskaber. Faktisk får man en diskret fraktal , det vil sige et sæt, der udviser stokastisk selvlighed på store skalaer. På små skalaer kan man observere "ujævnhed" som følge af gitteret, som turen udføres på. To Lawler -bøger, der refereres herunder, er en god kilde til dette emne. Banen for en tilfældig gåtur er samlingen af besøgte punkter, betragtet som et sæt uden hensyn til, hvornår turen ankom til punktet. I en dimension er banen simpelthen alle punkter mellem minimumshøjden og den maksimale højde, der er opnået (begge er i gennemsnit i størrelsesordenen ). ${\ displaystyle {\ sqrt {n}}}$

For at visualisere den todimensionelle sag kan man forestille sig en person, der går tilfældigt rundt i en by. Byen er effektivt uendelig og arrangeret i et firkantet gitter med fortove. Ved hvert kryds vælger personen tilfældigt en af de fire mulige ruter (inklusive den oprindeligt rejste fra). Formelt er dette en tilfældig gåtur på sættet af alle punkter i flyet med heltals koordinater .

Vil personen nogensinde komme tilbage til det oprindelige udgangspunkt for turen? Dette er den 2-dimensionelle ækvivalent til niveauoverskridelsesproblemet diskuteret ovenfor. I 1921 beviste George Pólya , at personen næsten helt sikkert ville i en 2-dimensionel tilfældig gåtur, men for 3 dimensioner eller højere falder sandsynligheden for at vende tilbage til oprindelsen, når antallet af dimensioner stiger. I 3 dimensioner falder sandsynligheden til cirka 34%. Matematikeren Shizuo Kakutani var kendt for at henvise til dette resultat med følgende citat: "En beruset mand finder vej hjem, men en beruset fugl kan gå tabt for evigt".

En anden variant af dette spørgsmål, som også blev stillet af Pólya er: Hvis to mennesker forlader det samme udgangspunkt, vil de så nogensinde mødes igen? Det kan vises, at forskellen mellem deres placeringer (to uafhængige tilfældige gåture) også er en simpel tilfældig gåtur, så de næsten sikkert mødes igen i en 2-dimensionel gåtur, men for 3 dimensioner og højere falder sandsynligheden med antallet af dimensioner. Paul Erdős og Samuel James Taylor viste også i 1960, at for dimensioner mindre eller lig med 4 har to uafhængige tilfældige gåture, der starter fra to givne punkter, uendeligt mange krydsninger næsten sikkert, men for dimensioner højere end 5 skærer de næsten sikkert kun endeligt ofte .

Den asymptotiske funktion for en todimensionel tilfældig gåtur, når antallet af trin stiger, er givet ved en Rayleigh-fordeling . Sandsynlighedsfordelingen er en funktion af radius fra oprindelsen, og trinlængden er konstant for hvert trin.

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

Forholdet til Wiener -processen

Simulerede trin, der nærmer sig en Wiener -proces i to dimensioner

En Wiener -proces er en stokastisk proces med lignende adfærd til brunisk bevægelse , det fysiske fænomen med en minutpartikel, der diffunderer i en væske. (Nogle gange kaldes Wiener -processen "Brownsk bevægelse", selvom dette strengt taget er en forvirring af en model med fænomenet, der modelleres.)

En Wiener -proces er skaleringsgrænsen for tilfældig gåtur i dimension 1. Det betyder, at hvis du tager en tilfældig gåtur med meget små trin, får du en tilnærmelse til en Wiener -proces (og, mindre præcist, til brunisk bevægelse). For at være mere præcis, hvis trinstørrelsen er ε, man har brug for at tage en tur med længden L / ε ² at tilnærme en Wiener længde L . Da trinstørrelsen har en tendens til 0 (og antallet af trin stiger proportionelt), konvergerer tilfældig gåtur til en Wiener -proces i passende forstand. Formelt hvis B er rummet af alle veje med længden L med den maksimale topologi, og hvis M er rummet af foranstaltningen i B med normen topologi, så konvergensen er i rummet M . På samme måde er en Wiener -proces i flere dimensioner skaleringsgrænsen for tilfældig gang i samme antal dimensioner.

En tilfældig gåtur er en diskret fraktal (en funktion med heltalsdimensioner; 1, 2, ...), men en Wiener -procesbane er en sand fraktal, og der er en forbindelse mellem de to. Tag for eksempel en tilfældig gåtur, indtil den rammer en cirkel med radius r gange trinlængden. Det gennemsnitlige antal trin, den udfører, er r ² . Denne kendsgerning er den diskrete version af det faktum, at en Wiener -procesgang er en fraktal af Hausdorff -dimension 2.

I to dimensioner er det gennemsnitlige antal punkter, den samme tilfældige gang har på grænsen til dets bane, r ^4/3 . Dette svarer til det faktum, at grænsen for banen i en Wiener -proces er en fraktal af dimension 4/3, et faktum forudsagt af Mandelbrot ved hjælp af simuleringer, men først blev påvist i 2000 af Lawler , Schramm og Werner .

En Wiener -proces nyder mange symmetrier, tilfældige gåture gør det ikke. For eksempel er en Wiener procesgang invariant for rotationer, men den tilfældige gang er ikke, da det underliggende gitter ikke er (tilfældig gang er invariant for rotationer med 90 grader, men Wiener processer er invariante for rotationer med for eksempel 17 grader også). Det betyder, at problemer i en tilfældig gåtur i mange tilfælde er lettere at løse ved at oversætte dem til en Wiener -proces, løse problemet der og derefter oversætte tilbage. På den anden side er nogle problemer lettere at løse med tilfældige gåture på grund af dens diskrete natur.

Tilfældig gang og Wiener -proces kan kobles , nemlig manifesteret på det samme sandsynlighedsrum på en afhængig måde, der tvinger dem til at være ganske tætte. Den enkleste sådan kobling er Skorokhod -indlejringen , men der findes mere præcise koblinger, såsom Komlós – Major – Tusnády tilnærmelse sætning.

Konvergensen af en tilfældig gåtur mod Wiener -processen styres af den centrale grænsesætning og af Donskers sætning . For en partikel i en kendt fast position ved t = 0 fortæller den centrale grænsesætning os , at rollatorens position efter et stort antal uafhængige trin i den tilfældige gang fordeles efter en normal fordeling af total varians :

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

hvor t er den tid, der er gået siden starten på den tilfældige gåtur, er størrelsen på et trin i den tilfældige gåtur og er den tid, der er gået mellem to på hinanden følgende trin. ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ delta t}$

Dette svarer til Greenens funktion af diffusionsligningen, der styrer Wiener -processen, hvilket tyder på, at den tilfældige gåtur efter et stort antal trin konvergerer mod en Wiener -proces.

I 3D er variansen, der svarer til Greenens funktion af diffusionsligningen:

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

Ved at udligne denne mængde med den varians, der er forbundet med placeringen af den tilfældige rollator, opnår man den ækvivalente diffusionskoefficient, der skal tages i betragtning for den asymptotiske Wiener -proces, hvortil den tilfældige gang konvergerer efter et stort antal trin:

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

(gælder kun i 3D).

Bemærk: de to udtryk for variansen ovenfor svarer til fordelingen forbundet med vektoren, der forbinder de to ender af tilfældig gang i 3D. Variansen, der er knyttet til hver komponent , eller er kun en tredjedel af denne værdi (stadig i 3D). ${\ displaystyle {\ vec {R}}}$ ${\ displaystyle R_ {x}}$ ${\ displaystyle R_ {y}}$ ${\ displaystyle R_ {z}}$

Til 2D:

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

Til 1D:

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

Gaussisk tilfældig gåtur

En tilfældig gåtur med en trinstørrelse, der varierer i henhold til en normal fordeling , bruges som model for tidsseriedata i virkeligheden, såsom finansielle markeder. Den Black-Scholes formel til modellering optionspriserne, for eksempel, bruger en Gauss random walk som en underliggende antagelse.

Her er trinstørrelsen den inverse kumulative normalfordeling, hvor 0 ≤ z ≤ 1 er et ensartet fordelt tilfældigt tal, og μ og σ er henholdsvis middel- og standardafvigelser for normalfordelingen. ${\ displaystyle \ Phi ^{-1} (z, \ mu, \ sigma)}$

Hvis μ er nul, vil den tilfældige gang variere omkring en lineær tendens. Hvis v _s er startværdien for den tilfældige gang, vil den forventede værdi efter n trin være v _s + n μ.

For det særlige tilfælde, hvor μ er lig med nul, efter n trin, er translationens afstands sandsynlighedsfordeling givet ved N (0, n σ ² ), hvor N () er notationen for normalfordelingen, n er antallet af trin , og σ er fra den inverse kumulative normalfordeling som angivet ovenfor.

Bevis: Den gaussiske tilfældige gang kan betragtes som summen af en sekvens af uafhængige og identisk fordelte tilfældige variabler, X _i fra den inverse kumulative normalfordeling med middelværdi lig nul og σ for den oprindelige inverse kumulative normalfordeling:

Z = ,

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

men vi har fordelingen for summen af to uafhængige normalt fordelte tilfældige variabler, Z = X + Y, er givet ved

{\ displaystyle {\ mathcal {N}}}

(μ _X + μ _Y , σ ²_X + σ ²_Y ) (se her) .

I vores tilfælde er μ _X = μ _Y = 0 og σ ²_X = σ ²_Y = σ ² udbytte

{\ displaystyle {\ mathcal {N}}}

(0, 2σ ² )

Ved induktion har vi n trin

Z ~ (0, n σ ² ).

{\ displaystyle {\ mathcal {N}}}

For trin fordelt i henhold til enhver fordeling med nul middelværdi og en begrænset varians (ikke nødvendigvis bare en normal fordeling) er rodmidlets kvadratiske oversættelsesafstand efter n trin

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

Men for den gaussiske tilfældige gang er dette bare standardafvigelsen af oversættelsesafstandens fordeling efter n trin. Derfor, hvis μ er lig med nul, og da root -mean square (RMS) oversættelsesafstand er en standardafvigelse, er der 68,27% sandsynlighed for, at RMS -oversættelsesafstanden efter n trin vil falde mellem ± σ . Ligeledes er der 50% sandsynlighed for, at oversættelsesafstanden efter n trin vil falde mellem ± 0,6745σ . ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle {\ sqrt {n}}}$

Uregelmæssig diffusion

I uordnede systemer som porøse medier og fraktaler er muligvis ikke proportionale med, men til . Eksponenten kaldes den anomale diffusionseksponent og kan være større eller mindre end 2. Anomal diffusion kan også udtrykkes som σ _r² ~ Dt ^α, hvor α er anomali -parameteren. Nogle diffusioner i tilfældige omgivelser er endda proportionale med en effekt af datidens logaritme, se f.eks. Sinais gang eller Brox -diffusion. ${\ displaystyle \ sigma ^{2}}$ ${\ displaystyle t}$ ${\ displaystyle t^{2/d_ {w}}}$ ${\ displaystyle d_ {w}}$

Antal forskellige steder

Antallet af forskellige steder besøgt af en enkelt tilfældig rollator er blevet undersøgt grundigt for firkantede og kubiske gitter og for fraktaler. Denne mængde er nyttig til analyse af problemer med fangst og kinetiske reaktioner. Det er også relateret til tilstandenes vibrationstæthed, diffusionsreaktionsprocesser og spredning af befolkninger i økologi. Generaliseringen af dette problem til antallet af forskellige steder besøgt af tilfældige vandrere , er for nylig blevet undersøgt for d-dimensionelle euklidiske gitter. Antallet af forskellige steder, som N -vandrere besøger, er ikke blot relateret til antallet af forskellige steder, som hver rollator besøger. ${\ displaystyle S (t)}$ ${\ displaystyle N}$ ${\ displaystyle S_ {N} (t)}$

Informationshastighed

De oplysninger rate af en Gauss random walk med hensyn til den kvadrerede fejl afstand, dvs. dens kvadratiske sats forvrængning funktion , er givet parametrisk ved

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

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

hvor . Derfor er det umuligt at kode ved hjælp af en binær kode på mindre end bits og gendanne den med forventet gennemsnitlig kvadratfejl mindre end . På den anden side, for enhver , eksisterer der en stor nok og en binær kode på ikke mere end forskellige elementer, således at den forventede gennemsnitlige kvadratfejl ved at gendanne fra denne kode højst er . ${\ 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}$

Ansøgninger

Antony Gormley 's Quantum Cloud skulptur i London er designet af en computer ved hjælp af en random walk algoritme.

Som nævnt er rækken af naturlige fænomener, der har været genstand for forsøg på beskrivelse af en smag af tilfældige gåture, betydelig, især inden for fysik og kemi, materialevidenskab , biologi og forskellige andre områder. Følgende er nogle specifikke anvendelser af tilfældig gang:

I finansiel økonomi , den " random walk hypotesen er" bruges til model aktier priser og andre faktorer. Empiriske undersøgelser fandt nogle afvigelser fra denne teoretiske model, især i kortsigtede og langsigtede korrelationer. Se aktiekurser .
I populationsgenetik beskriver random walk de statistiske egenskaber ved genetisk drift
I fysik bruges tilfældige gåture som forenklede modeller for fysisk brunisk bevægelse og diffusion, såsom tilfældig bevægelse af molekyler i væsker og gasser. Se for eksempel diffusionsbegrænset aggregering . Også i fysik spiller tilfældige gåture og nogle af de selvinteragerende gåture en rolle i kvantefeltteorien .
I matematisk økologi bruges tilfældige gåture til at beskrive individuelle dyrs bevægelser, til empirisk at understøtte biodiffusionsprocesser og lejlighedsvis til at modellere populationsdynamik .
I polymerfysik beskriver random walk en ideel kæde . Det er den enkleste model at studere polymerer .
I andre matematikfelter bruges tilfældig gang til at beregne løsninger til Laplaces ligning , til at estimere det harmoniske mål og til forskellige konstruktioner inden for analyse og kombinatorik .
I datalogi , er tilfældige gåture anvendes til at anslå størrelsen af nettet .
Ved billedsegmentering bruges tilfældige vandringer til at bestemme etiketterne (dvs. "objekt" eller "baggrund"), der skal associeres med hver pixel. Denne algoritme kaldes typisk algoritmen for tilfældig rollator -segmentering.

I alle disse tilfælde er tilfældig gåtur ofte erstattet af brunsk bevægelse.

I hjerneforskning bruges tilfældige gåture og forstærkede tilfældige gåture til at modellere kaskader af neuronfyring i hjernen.
I synsvidenskab har okulær drift en tendens til at opføre sig som en tilfældig gåtur. Ifølge nogle forfattere er fikserende øjenbevægelser generelt også godt beskrevet ved en tilfældig gåtur.
I psykologi forklarer tilfældige gåture nøjagtigt forholdet mellem den tid, der er nødvendig til at træffe en beslutning, og sandsynligheden for, at en bestemt beslutning vil blive truffet.
Tilfældige gåture kan bruges til at prøve fra et statsrum, der er ukendt eller meget stort, for eksempel at vælge en tilfældig side fra internettet eller, til undersøgelse af arbejdsforhold, en tilfældig arbejder i et givet land.

Når denne sidste tilgang bruges inden for datalogi , er den kendt som Markov -kæden Monte Carlo eller MCMC for kort. Ofte giver prøveudtagning fra et kompliceret statsrum også mulighed for at få et sandsynligt estimat af rummets størrelse. Estimatet af den permanente af en stor matrix af nuller og dem var det første store problem, der blev løst ved hjælp af denne tilgang.

Tilfældige gåture er også blevet brugt til at prøve massive online grafer såsom sociale netværkstjenester .
I trådløst netværk bruges en tilfældig gåtur til at modellere knudebevægelser.
Motile bakterier deltager i en forudindtaget tilfældig gåtur .
Tilfældige gåture bruges til at modellere spil .
I fysik ligger tilfældige gåture til grund for metoden til Fermi -estimering .
På internettet bruger Twitter -webstedet tilfældige gåture til at komme med forslag til, hvem man skal følge
Dave Bayer og Persi Diaconis har bevist, at 7 riffel shuffles er nok til at blande en pakke kort (se flere detaljer under shuffle ). Dette resultat oversætter til en erklæring om tilfældig gang på den symmetriske gruppe, hvilket er hvad de beviser med en afgørende brug af gruppestrukturen via Fourier -analyse.

Varianter

En række typer af stokastiske processer er blevet overvejet, der ligner de rene tilfældige gåture, men hvor den enkle struktur får lov til at blive mere generaliseret. Den rene struktur kan karakteriseres ved, at trinene defineres af uafhængige og identisk fordelte tilfældige variabler .

På grafer

En tilfældig gåtur i længden k på en muligvis uendelig graf G med en rod 0 er en stokastisk proces med tilfældige variabler , der er og er et toppunkt valgt ensartet tilfældigt blandt naboerne til . Derefter er tallet sandsynligheden for, at en tilfældig gåtur i længden k startende ved v ender ved w . Især hvis G er en graf med rod 0 , er sandsynligheden for, at et tilfældigt skridt -trin vender tilbage til 0 . ${\ displaystyle X_ {1}, X_ {2}, \ dots, 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}$

Bygger på analogien fra det tidligere afsnit om højere dimensioner, antag nu, at vores by ikke længere er et perfekt firkantet gitter. Når vores person når et bestemt kryds, vælger han med lige sandsynlighed mellem de forskellige tilgængelige veje. Således, hvis krydset har syv udgange, vil personen gå til hver enkelt med sandsynlighed en syvende. Dette er en tilfældig gåtur på en graf. Vil vores person nå sit hjem? Det viser sig, at svaret på temmelig milde betingelser stadig er ja, men afhængigt af grafen er svaret på variantspørgsmålet 'Vil to personer mødes igen?' kan ikke være, at de mødes uendeligt ofte næsten sikkert.

Et eksempel på et tilfælde, hvor personen næsten sikkert vil nå sit hjem, er når længden af alle blokke er mellem a og b (hvor a og b er to endelige positive tal). Bemærk, at vi ikke går ud fra, at grafen er plan , dvs. byen kan indeholde tunneler og broer. En måde at bevise dette resultat på er at bruge forbindelsen til elektriske netværk . Tag et kort over byen, og placer en modstand på en ohm på hver blok. Mål nu "modstanden mellem et punkt og uendeligt". Med andre ord, vælg et nummer R og tag alle punkterne i det elektriske netværk med afstand større end R fra vores punkt og led dem sammen. Dette er nu et begrænset elektrisk netværk, og vi kan måle modstanden fra vores punkt til de kablede punkter. Tag R til det uendelige. Grænsen kaldes modstanden mellem et punkt og uendeligt . Det viser sig, at følgende er sandt (et elementært bevis kan findes i bogen af Doyle og Snell):

Sætning : en graf er forbigående, hvis og kun hvis modstanden mellem et punkt og uendeligt er begrænset. Det er ikke vigtigt, hvilket punkt der vælges, hvis grafen er forbundet.

Med andre ord, i et forbigående system behøver man kun at overvinde en begrænset modstand for at komme til uendelig fra ethvert punkt. I et tilbagevendende system er modstanden fra ethvert punkt til uendelig uendelig.

Denne karakterisering af forgængelighed og tilbagefald er meget nyttig, og specifikt giver det os mulighed for at analysere sagen om en by trukket i flyet med afstande begrænset.

En tilfældig gåtur på en graf er et helt specielt tilfælde af en Markov -kæde . I modsætning til en almindelig Markov -kæde nyder tilfældig gang på en graf en egenskab kaldet tidssymmetri eller reversibilitet . Groft sagt betyder denne egenskab, også kaldet princippet om detaljeret balance , at sandsynlighederne for at krydse en given vej i den ene eller den anden retning har en meget enkel forbindelse mellem dem (hvis grafen er regelmæssig , er de bare lige). Denne ejendom har vigtige konsekvenser.

Fra 1980'erne er der gået meget forskning i at forbinde grafens egenskaber med tilfældige gåture. Ud over den elektriske netværksforbindelse, der er beskrevet ovenfor, er der vigtige forbindelser til isoperimetriske uligheder , se mere her , funktionelle uligheder som Sobolev og Poincaré uligheder og egenskaber ved løsninger af Laplaces ligning . En væsentlig del af denne forskning var fokuseret på Cayley -grafer over endeligt genererede grupper . I mange tilfælde går disse diskrete resultater videre til eller er afledt af manifolder og Lie -grupper .

I forbindelse med tilfældige grafer , især Erdős – Rényi -modellen , er der opnået analytiske resultater for nogle egenskaber for tilfældige vandrere. Disse omfatter fordelingen af rollatorens første og sidste slagtid, hvor den første slagtid er givet ved den første gang rollatoren træder ind på et tidligere besøgt sted i grafen, og den sidste slagtid svarer til den første gang, rollatoren ikke kan udføre et ekstra træk uden at besøge et tidligere besøgt websted.

En god reference til tilfældig gang på grafer er online -bogen af Aldous og Fill . For grupper se Woess 'bog. Hvis overgangskernen selv er tilfældig (baseret på et miljø ), kaldes den tilfældige gang en "tilfældig gåtur i tilfældigt miljø". Når loven om den tilfældige gang inkluderer tilfældigheden af , kaldes loven den annealede lov; på den anden side, hvis den ses som fast, kaldes loven en slukket lov. Se Hughes 'bog, Revesz' bog eller Zeitounis forelæsningsnotater. ${\ displaystyle p (x, y)}$ ${\ displaystyle \ omega}$ ${\ displaystyle \ omega}$ ${\ displaystyle \ omega}$

Vi kan tænke på at vælge enhver mulig kant med samme sandsynlighed som at maksimere usikkerhed (entropi) lokalt. Vi kunne også gøre det globalt - ved maksimal entropi random walk (MERW) ønsker vi, at alle stier er lige sandsynlige, eller med andre ord: for hver to toppunkter er hver sti med en given længde lige så sandsynlig. Denne tilfældige gang har meget stærkere lokaliseringsegenskaber.

Selvinteragerende tilfældige gåture

Der er en række interessante modeller af tilfældige stier, hvor hvert trin afhænger af fortiden på en kompliceret måde. Alle er mere komplekse til at løse analytisk end den sædvanlige tilfældige gang; alligevel kan adfærden for enhver model af en tilfældig rollator opnås ved hjælp af computere. Eksempler omfatter:

Den selvundgående gåtur .

Den selvundgående gåtur med længden n på er den tilfældige n -trinsti, der starter ved oprindelsen, kun foretager overgange mellem tilstødende steder i , besøger aldrig et sted igen og vælges ensartet blandt alle sådanne stier. I to dimensioner, på grund af selvfangst, er en typisk selvundgående gåtur meget kort, mens den i højere dimension vokser ud over alle grænser. Denne model er ofte blevet brugt i polymerfysik (siden 1960'erne). ${\ displaystyle \ mathbb {Z} ^{d}}$ ${\ displaystyle \ mathbb {Z} ^{d}}$

Langtrækkende korrelerede gåture

Langtrækkende korrelerede tidsserier findes i mange biologiske, klimatologiske og økonomiske systemer.

Hjerteslagsrekorder
Ikke-kodende DNA-sekvenser
Volatilitet tidsserier af aktier
Temperaturrekorder over hele kloden

Partisk tilfældig vandring på grafer

Maksimal entropi tilfældig gang

Tilfældig gåtur valgt for at maksimere entropihastigheden har meget stærkere lokaliseringsegenskaber.

Korrelerede tilfældige gåture

Tilfældige gåture, hvor bevægelsesretningen på et tidspunkt er korreleret med bevægelsesretningen på det næste tidspunkt. Det bruges til at modellere dyrebevægelser.

Se også

Referencer

Bibliografi

Aldous, David ; Fill, James Allen (2002). Reversible Markov -kæder og tilfældige vandringer på grafer . Arkiveret fra originalen den 27. februar 2019.
Ben-Avraham D .; Havlin S. , Diffusion and Reactions in Fractals and Disordered Systems , Cambridge University Press, 2000.
Doyle, Peter G .; Snell, J. Laurie (1984). Tilfældige gåture og elektriske netværk . Carus matematiske monografier. 22 . Mathematical Association of America . arXiv : matematik.PR/0001057 . ISBN 978-0-88385-024-4. MR 0920811 .
Feller, William (1968), En introduktion til sandsynlighedsteori og dens anvendelser (bind 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 Wahrscheinlechlichkeitsrechnung betreffend die Irrfahrt im Strassennetz" , Mathematische Annalen , 84 (1–2): 149–160, marts 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). Topologisk krystallografi: Med udsigt til diskret geometrisk analyse . Undersøgelser og selvstudier i de anvendte matematiske videnskaber. 6 . Springer. ISBN 978-4-431-54177-6.
Weiss G. Aspekter og anvendelser af Random Walk , Nordholland, 1994.
Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups , Cambridge -traktater i matematik 138, Cambridge University Press. ISBN 0-521-55292-3

eksterne links

Pólyas tilfældige gåkonstanter
Tilfældig gåtur i Java Applet
Quantum random walk
Gaussisk random walk estimator
Elektronledningsmodeller ved hjælp af maksimal entropi Tilfældige gås Wolfram demonstrationsprojekt

Languages

In other projects