Tilfældig gåtur

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. oktober 2022; verifikation kræver 1 redigering .

En tilfældig gang er et matematisk objekt kendt som en stokastisk eller tilfældig proces , der beskriver en sti, der består af en sekvens af tilfældige trin i et matematisk rum (for eksempel på sættet af heltal ).

Det enkleste eksempel på en tilfældig gang er en tilfældig gang langs tallinjen af heltal, , som starter ved punkt 0 og skifter med +1 eller -1 ved hvert trin med lige stor sandsynlighed . Andre eksempler er bane for et molekyle i en væske eller gas ( Brownsk bevægelse ), stifinding hos dyr under fouragering , udsving i aktiekurser på aktiemarkedet , en spillers økonomiske situation : alle de beskrevne tilfælde kan tilnærmes ved tilfældig vandring modeller, selvom de måske ikke er helt tilfældige i det virkelige liv. $\mathbb {Z}$

Som du kan se fra eksemplerne, bruges random walk-modellen inden for ingeniørvidenskab og mange videnskabelige områder, herunder økologi, psykologi, datalogi, fysik, kemi, biologi, økonomi og sociologi. Den tilfældige vandring forklarer den observerede adfærd af mange processer i disse regioner og fungerer således som en grundlæggende model for den registrerede stokastiske aktivitet. Så i matematik kan værdien af π tilnærmes ved hjælp af en tilfældig gang og agent-baseret modellering. [1] [2] Konceptet med en tilfældig gåtur blev først introduceret af Karl Pearson i 1905. [3]

Typer af tilfældige gåture kan være af forskellig art. Selve begrebet refererer oftest til en særlig kategori af Markov-kæder eller Markov-processer, og mange tidsafhængige processer omtales som random walks med en modifikator, der angiver deres særlige egenskaber. Tilfældige vandringer (Markov eller ej) kan også forekomme inden for en række områder: de almindeligt studerede omfatter grafer , tallinjen af heltal eller reelle , vektorrum , buede overflader, multidimensionelle Riemann-manifolder og endelige , endeligt genererede grupper, Lie-grupper . Tidsparameteren kan også være anderledes. I det enkleste tilfælde foregår vandringen i diskret tid og er en sekvens af tilfældige variable ( X
t) = ( X
en, X
2, ...) , indekseret med naturlige tal. Der er dog også tilfældige ture, hvor trinene sker på et vilkårligt tidspunkt, og i dette tilfælde positionen X
tskal defineres for alle tidspunkter t ∈ [0,+∞) . Særlige tilfælde af tilfældig gang er Levy-flyvning og diffusionsmodeller såsom Brownsk bevægelse .

Random walk er et grundlæggende emne i diskussioner om Markov-processen, og dens matematiske undersøgelse er meget omfattende.

Tilfældig gang på et gitter

En velkendt model for en tilfældig gåtur er en tur på et regulært gitter, hvor placeringen ved hvert trin bevæger sig til et andet punkt i overensstemmelse med en vis sandsynlighedsfordeling.

I en simpel tilfældig gåtur kan en placering kun flyttes til tilstødende gitterpunkter og danne en gittersti. I en simpel symmetrisk tilfældig gang på et lokalt afgrænset gitter er sandsynligheden for, at et punkt går til hver af dets umiddelbare naboer lige store. Det bedst undersøgte eksempel er den tilfældige gang på et d - dimensionelt gitter af heltal (nogle gange kaldet et hyperkubisk gitter) . [fire] ${\displaystyle \mathbb {Z} ^{d))$

Hvis tilstandsrummet er begrænset til et begrænset antal dimensioner, kaldes en sådan tilfældig gangmodel en simpel afgrænset symmetrisk tilfældig gang , og overgangssandsynligheden afhænger af punktets placering, fordi bevægelsen er begrænset ved grænse- og hjørnepunkterne . [5]

En-dimensionel tilfældig gang

Det enkleste eksempel på en tilfældig gang er en tilfældig tur langs tallinjen med heltal , , som starter ved punkt 0 og flytter +1 eller −1 med lige stor sandsynlighed ved hvert trin. $\mathbb {Z}$

Denne vandring kan illustreres som følger. Mærket placeres på nummerlinjens nul, og der kastes en "fair" mønt. Hvis den kommer op ad hoveder, flytter etiketten en enhed til højre, og hvis den kommer op i haler, flytter den en enhed til venstre. Efter fem kast kan mærket være på -5, -3, -1, 1, 3, 5. For fem kast, inklusive tre hoveder og to haler, i en hvilken som helst rækkefølge, vil mærket være på 1. Der er 10 måder at komme til punkt 1 (ved at rulle tre hoveder og to haler), 10 måder at komme til punkt −1 (tre haler og to hoveder), 5 måder at komme til punkt 3 (fire hoveder) og en "haler"), 5 måder at komme til punkt -3 (fire "haler" og en "ørn"), 1 måde at komme til punkt 5 (fem "hoveder") og 1 måde at komme til punkt -5 (fem "haler"). ") . De mulige resultater af de fem ruller er illustreret nedenfor.

For at definere denne vandring formelt tager vi uafhængige tilfældige variable , hvor hver variabel er enten 1 eller −1, med en sandsynlighed lig med 50 % for hver værdi, kaldes mængden og serien en simpel tilfældig vandring på . Denne serie (summen af sekvensen −1 og 1) betyder den tilbagelagte afstand, hvis hver del af turen har en længde lig med én. Seriens matematiske forventning er nul. Det vil sige, at den gennemsnitlige værdi af alle møntkast har en tendens til nul, når antallet af kast stiger. Dette følger af forventningens endelige additivitetsegenskab: $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.

På samme måde bruger vi uafhængigheden af tilfældige variable og det faktum , at vi ser: $E(Z_{n}^{2})=1$

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

Dette gør det klart , at den forventede afstand efter at have flyttet n skridt, bør være af størrelsesordenen . Faktisk [6] $E(|S_{n}|)\,\!$ ${\sqrt n}$

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

Hvor mange gange vil den tilfældige gåtur krydse grænsen, hvis det er muligt at vandre i det uendelige? Den enkleste tilfældige walk on vil skære hvert punkt et uendeligt antal gange. Den resulterende effekt har mange navne: niveaukrydsningsfænomenet , gentagelse eller spillerruinproblemet . Grunden til at give den sidste sag navnet er denne: en spiller med et begrænset beløb vil tabe før eller siden, hvis han spiller et fair spil mod en pulje med et ubegrænset beløb. Spillerens penge er en tilfældig gåtur, og på et tidspunkt når de nul, og spillet vil være slut. $\mathbb {Z}$

Lad a og b være positive heltal, så er det forventede antal trin, når en simpel endimensionel tilfældig gang, der starter ved 0, først når b eller −a , ab . Sandsynligheden for at en given gang når b før den når −a er , hvilket følger af at en simpel tilfældig gang er en martingal . $a/(a+b)$

Nogle af resultaterne nævnt ovenfor kan udledes af egenskaberne for Pascals trekant . Antallet af alle distinkte ture over n

trin, hvor hvert trin er enten +1 eller −1 er lig med 2 n . For en simpel tilfældig gåtur er hvert af disse trin lige sandsynligt. For at være lig med tallet k , er det nødvendigt og tilstrækkeligt, at antallet af skridt med +1 i gåturen overstiger dem med −1 med tallet k . Derfor skal et trin på +1 forekomme (n + k)/2 gange blandt n gåture, derfor er antallet af gåture, der opfylder betingelsen , lig med antallet af måder at vælge (n + k)/2 elementer fra en n -elementsæt. [7] Dette er betegnet som . For at dette udtryk skal give mening, er det nødvendigt, at summen n + k er et lige tal, hvilket betyder, at tallene n og k skal være enten lige eller ulige på samme tid. Derfor er den sandsynlighed, der vil være lig med . Ved at repræsentere indgangene i Pascals trekant i form af factorialer og ved at bruge Stirlings formel , kan man få gode estimater af disse sandsynligheder for store værdier på . $S_{n}\,\!$ $S_{n}=k$ $n \choose (n+k)/2$ $S_{n}=k$ ${\displaystyle 2^{-n}{n \choose (n+k)/2))$ $n$

Hvis pladsen er begrænset til + for korthedens skyld, kan antallet af måder, hvorpå den tilfældige gåtur stopper ved et eller andet tal efter fem trin, vises som {0,5,0,4,0,1}. $\mathbb {Z}$

Lad os demonstrere denne korrespondance til Pascals trekant for små værdier af n . Ved nultrinnet er den eneste mulighed at blive ved nul. Allerede ved første træk er der dog mulighed for at ende enten på -1 eller på 1. På andet træk, fra 1, kan du rykke til punkt 2, eller tilbage til nul. Du kan flytte fra -1 til -2 eller tilbage til nul. Derfor er der et tilfælde, når vi er ved punkt -2, to tilfælde, når vi er på nul, og et tilfælde, når vi er ved punkt 2.

k	−5	−4	−3	−2	−1	0	en	2	3	fire	5
$P[S_{0}=k]$						en
$2P[S_{1}=k]$					en		en
$2^{2}P[S_{2}=k]$				en		2		en
$2^{3}P[S_{3}=k]$			en		3		3		en
$2^{4}P[S_{4}=k]$		en		fire		6		fire		en
$2^{5}P[S_{5}=k]$	en		5		ti		ti		5		en

Den centrale grænsesætning og loven om den itererede logaritme beskriver vigtige aspekter af adfærden ved en simpel tilfældig gåtur på . Især når n stiger, tenderer sandsynligheden (i forhold til tallene i hver række) mod en normalfordeling . $\mathbb {Z}$

Tilfældige vandringer på krystalgitter (uendeligt mange Abeliske dækkende grafer af endelige grafer) kan betragtes som en direkte generalisering. Faktisk er det under sådanne forhold endda muligt at hævde den centrale grænsesætning og den store afvigelsessætning. [8] [9]

Som en Markov-kæde

En en-dimensionel diskret tilfældig gang er en heltal-tilstand Markov-kæde, hvis indledende fordeling er givet af sandsynlighedsfunktionen af den stokastiske variabel , og overgangssandsynlighedsmatrixen er $X_{0}$

P\equiv (p_{{ij}})_{{i,j\in {\mathbb {Z}}}}=\venstre({\begin{matrix}\ddots &\ddots &\ddots &\\&q_ {{-1}}&0&p_{{-1}}&\\&&q_{0}&0&p_{0}\\&&&q_{1}&0&p_{1}\\&&&&&\ddots &\ddots &\ddots \end{matrix} }\ret)

det er

p_{{i,i+1}}\equiv {\mathbb {P}}(X_{{n+1}}=i+1\midt 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 \i {\mathbb {Z}),

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

Forhøjede dimensioner

I højere dimensioner har sættet af tilfældige gangpunkter ret interessante geometriske egenskaber. Faktisk får vi en diskret fraktal , det vil sige et sæt, der viser stokastisk selvlighed, når der zoomes ind. I lille skala kan du observere "jaggedness" på gitteret, hvorpå vandringen udføres. Lawlers to citerede bøger er gode kilder til materiale om emnet. Banen for en tilfældig gåtur er en samling af besøgte punkter, betragtet som et sæt op til det tidspunkt, hvor gåturen nåede punktet. I én dimension er banen simpelthen alle punkterne mellem minimumshøjden og den maksimale højde, som vandreren har nået (begge i gennemsnit i størrelsesordenen ). ${\sqrt {n}}$

For at visualisere en todimensionel sag kan man forestille sig en person, der tilfældigt går rundt i byen. Denne by er praktisk talt uendelig og er anlagt i et firkantet gitter af fortove. Ved hvert vejkryds vælger en person tilfældigt en af fire mulige ruter (inklusive den, han kom fra). Formelt er dette en tilfældig gåtur over sættet af alle punkter på flyet med heltalskoordinater .

Vil denne person nogensinde vende tilbage til udgangspunktet for at vandre? Dette tilfælde er 2D-ækvivalenten til niveauoverskæringsproblemet beskrevet ovenfor. I 1921 beviste György Pólya , at en person næsten helt sikkert ville vende tilbage i tilfælde af en todimensionel tilfældig gåtur, men for tre dimensioner eller mere falder sandsynligheden for at vende tilbage, når antallet af dimensioner stiger. I det tredimensionelle tilfælde falder sandsynligheden til omkring 34%. [10] Matematikeren Shizuo Kakutani er berømt for sit citat om dette resultat: "En drukkenbolt vil før eller siden finde vej hjem, men en beruset fugl kan gå tabt for evigt." [elleve]

En anden version af dette spørgsmål, som også blev stillet af Poya, er: Hvis to mennesker forlader det samme udgangspunkt, vil de så nogensinde mødes? [12] Man kan begrunde, at forskellen mellem deres placeringer (to uafhængige tilfældige gåture) også er en simpel tilfældig gåtur, så de vil næsten helt sikkert mødes i en todimensionel gåtur, men for tre dimensioner eller mere er sandsynligheden for tilbagevenden samme som i det foregående tilfælde, falder med stigende antal målinger. Pal Erdős og Samuel James Taylor viste også i 1960, at for dimensioner mindre end eller lig med 4, to uafhængige tilfældige ture, der starter ved et hvilket som helst to givne punkter, næsten helt sikkert har uendeligt mange skæringspunkter, men for dimensioner større end 5 er de næsten helt sikkert skærer kun et begrænset antal gange. [13]

Den asymptotiske funktion for en 2D tilfældig gang, når antallet af skridt stiger, er givet af Rayleigh-fordelingen . Sandsynlighedsfordelingen er en funktion af radius fra origo, og for hvert trin er trinlængden konstant.

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

Relation til Wiener-processen

Wiener-processen er en stokastisk proces, der i sin adfærd ligner Brownsk bevægelse , et fysisk fænomen med diffusion af små partikler i en væske. (Nogle gange kaldes en Wiener-proces en Brownsk bevægelse, selvom strengt taget en Wiener-proces er en model, og en Brownsk bevægelse er et modelleret fænomen.)

Wiener-processen er den skalerbare grænse for en endimensionel tilfældig gåtur. Det betyder, at hvis du tager en tilfældig gåtur med meget små skridt, så kan du få en tilnærmelse til Wiener-processen (og, med mindre nøjagtighed, til Brownsk bevægelse). Mere præcist, hvis skridtlængden er ε, skal man gå en tur med længden L /ε 2 for at tilnærme Wiener-stien L . Efterhånden som trinlængden nærmer sig nul (og antallet af trin stiger forholdsmæssigt), dækker den tilfældige gang Wiener-processen i en passende forstand. Formelt, hvis B er rummet af alle baner af længde L med den maksimale topologi, og hvis M er rummet af foranstaltninger over B med den normale topologi, så er konvergensen i rummet M . Analogt er en Wiener-proces i flere dimensioner den skalerbare grænse for en tilfældig gang i det samme antal dimensioner.

En random walk er en diskret fraktal (en funktion med et heltal af dimensioner; 1, 2, ...), mens Wiener-processens bane er en rigtig fraktal, og der er en vis sammenhæng mellem de to. Lad os for eksempel gå en tilfældig gåtur, og vi vil "gå", indtil vi passerer en cirkel med radius r gange længden af skridtet. Så vil det gennemsnitlige antal skridt, der kræves for at fuldføre gåturen, være lig med r 2 . Dette faktum er en diskret version af det faktum, at Wiener-procesvandringen er en fraktal af Hausdorff-dimension 2.

I todimensionelt rum er det gennemsnitlige antal punkter, som en tilfældig gåtur passerer på grænsen af sin bane, r 4/3 . Dette er i overensstemmelse med det faktum, at banegrænsen for en Wiener-proces er en 4/3 fraktal, som blev foreslået af Mandelbrot ved brug af simuleringer, men som først blev bevist i 2000 af Lawler, Schramm og Werner . [fjorten]

Wiener-processen har mange symmetrier i modsætning til den tilfældige gang. For eksempel er en Wiener-procesgang rotationsinvariant, men en tilfældig gang er det ikke, fordi dens gitter ikke er rotationsinvariant (tilfældig gang er rotationsinvariant med 90 grader, mens Wienerprocesser er rotationsinvariant med f.eks. yderligere 17 grader). ). Det betyder, at problemer givet på en tilfældig gåtur i mange tilfælde er nemmere at løse på følgende måde: overfør problemet til Wiener-processen, løs problemet der, og overfør det derefter tilbage. På den anden side er nogle problemer lettere at løse på en tilfældig gåtur på grund af dens diskrete karakter.

Konvergensen af en tilfældig gåtur til en Wiener-proces udføres ved hjælp af den centrale grænsesætning og Donskers sætning. For en partikel i en kendt fast position ved t = 0 fortæller den centrale grænsesætning os, at efter et stort antal uafhængige tilfældige gangtrin, vil vandrerens position blive fordelt i henhold til den normale variansfordeling :

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

hvor t er den tid, der er gået siden starten af den tilfældige gåtur, er skridtstørrelsen på gåturen og er den tid, der er forløbet mellem to på hinanden følgende skridt. $\varepsilon$ $\delta t$

Dette tilfælde svarer til den grønnes funktion af diffusionsligningen , som beskriver Wiener-processen, hvilket antyder, at efter et tilstrækkeligt stort antal trin konvergerer den tilfældige gang til Wiener-processen.

I 3D-tilfældet er variansen svarende til den grønnes funktion af diffusionsligningen:

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

Ved at udligne denne værdi med variansen forbundet med positionen af den tilfældige walker, kan man opnå den ækvivalente diffusionskoefficient, taget i betragtning for en asymptotisk Wiener-proces, hvortil den tilfældige gang konvergerer efter et tilstrækkeligt stort antal trin:

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

(giver kun mening i tilfælde af tre dimensioner).

Bemærk: Ovenstående to variansudtryk svarer til en fordeling forbundet med en vektor , der forbinder de to ender af en tilfældig gang i tre dimensioner. Forskellen forbundet med hver komponent, eller , er kun en tredjedel af den samlede værdi (stadig 3D). $\vec R$ $R_{x}$ $R_{y}$ $R_{z}$

Til 2D: [15]

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

For 1D: [16]

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

Donskers sætning

Overvej en tilfældig gåtur , hvor . $Y_{n}=\sum \limits _{{i=1}}^{{n}}{X_{i}}$ $EX_{i}=0,DX_{i}=\sigma ^{2}<\infty$

Den centrale grænsesætning siger, at ved fordeling ved . ${\frac {Y_{n}}{\sigma {\sqrt {n}}}}\højrepil N(0,1)$ $n\højrepil\infty$

For tilfældige gåture kan denne påstand dog styrkes betydeligt.

Vi konstruerer en tilfældig proces med hensyn til , definerer den som følger: , og for resten definerer vi processen ved en lineær fortsættelse: $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}\venstre({\frac {k}{n}}\right)+(nt-k)S_{n}\venstre({\ frac {k+1}{n}}\right),t\in \left({\frac {k}{n));{\frac {k+1}{n}}\right)$

Fra den centrale grænsesætning om fordeling for $\foralt t$ $S_{n}(t)\højrepil N(0,t)$ $n\højrepil\infty$

Dette betyder konvergensen af processens endimensionelle fordelinger til Wiener-processens endimensionelle fordelinger . Donskers sætning, også kaldet invariansprincippet, siger, at der er en svag konvergens af processer, $S_{n}(t)$ $S_{n}(t)\højrepil W(t),n\højrepil \infty$

Svag konvergens af processer betyder konvergensen af funktionaler, der er kontinuerlige i forhold til Wiener-målet, det vil sige, det gør det muligt at beregne værdierne af funktionaler fra Brownsk bevægelse (f.eks. maksimum, minimum, sidste nul, tidspunktet for først at nå niveauet og andre) ved at gå til grænsen fra en simpel tilfældig gåtur.

Gaussisk tilfældig gang

En tilfældig gåtur med en skridtlængde, der varierer med en normalfordeling , bruges som tidsseriedata fra den virkelige verden, såsom finansielle markeder. Black-Schools-formlen bruger for eksempel en Gaussisk tilfældig gang som sin underliggende antagelse.

I dette tilfælde er trinstørrelsen den inverse kumulative normalfordeling, hvor 0 ≤ z ≤ 1 og er et ensartet fordelt tilfældigt tal, og μ og σ er henholdsvis middelværdien og standardafvigelsen af normalfordelingen. $\Phi ^{-1}(z,\mu ,\sigma )$

Hvis μ er ikke-nul, vil den tilfældige gang følge en lineær tendens. Hvis v s er startværdien af den tilfældige gang, så er den forventede værdi efter n trin v s + n μ.

For det specielle tilfælde, hvor μ er nul, efter n trin, er sandsynlighedsfordelingen for den tilbagelagte afstand defineret som N (0, n σ 2 ), hvor N () er notationen for normalfordelingen, n er antallet af trin , og σ er taget fra ovenstående inverse kumulative normalfordeling.

Bevis: En Gaussisk tilfældig gang kan repræsenteres som summen af en sekvens af uafhængige og identisk fordelte stokastiske variable, X i fra en invers kumulativ normalfordeling, hvor middelværdien er nul og σ er taget fra den oprindelige inverse kumulative normalfordeling:

Z = ,

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

men vi har en fordeling for summen af to uafhængige normalfordelte stokastiske variable, Z = X + Y, opnået takket være

\mathcal{N}

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

I vores tilfælde giver μ X = μ Y = 0 og σ 2 X = σ 2 Y = σ 2 :

\mathcal{N}

(0, 2σ 2 )

Ved induktion har vi for n trin:

Z ~ ( 0, n σ2 ).

\mathcal{N}

For trin fordelt i overensstemmelse med enhver fordeling med nul middelværdi og endelig varians (ikke nødvendigvis kun en normalfordeling), er rodmiddelværdien af den tilbagelagte afstand efter n trin givet ved:

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

Men for en Gaussisk tilfældig gåtur er dette kun standardafvigelsen af fordelingen af den tilbagelagte afstand efter n skridt. Derfor, hvis μ er nul, og hvis den tilbagelagte rms-afstand er én standardafvigelse, er der en 68,27 % chance for, at den tilbagelagte rms-afstand efter n trin vil være mellem ± σ . Der er også en 50 % chance for, at afstanden tilbagelagt efter n trin vil være mellem ± 0,6745σ . ${\sqrt {n}}$ ${\sqrt {n}}$

Anomal diffusion

I uordnede systemer, såsom porøse medier og fraktaler, kan det være proportionalt ikke til , men . Eksponenten kaldes den anomale diffusionseksponent og kan være større eller mindre end 2. [17] Den anomale diffusion kan også udtrykkes som σ r 2 ~ Dt α hvor α er anomaliparameteren. Nogle diffusioner i et tilfældigt miljø er endda proportionale med styrken af tidens logaritme, såsom Sinais gang eller Brox's diffusion. $\sigma ^{2}$ $t$ $t^{2/d_{w))$ $d_{w}$

Antal forskellige steder

Antallet af forskellige steder besøgt af en enkelt tilfældig vandrer er blevet grundigt undersøgt for kvadratiske og kubiske gitter og fraktaler. [18] [19] Denne værdi er nyttig til at analysere problemer med dødvande (engelsk fældefangst ) og kinetiske reaktioner. Det er også relateret til tilstandens vibrationstæthed, [20] [21] diffusionsreaktioner af processer [22] og fordelingen af populationer i økologi. [23] [24] En generalisering af dette problem til antallet af forskellige steder besøgt af tilfældige vandrere, betegnet som , er for nylig blevet undersøgt for d -dimensionelle euklidiske gitter. [25] Antallet af forskellige steder besøgt af N vandrere er ikke blot relateret til antallet af forskellige steder, som hver vandrer besøger. $S(t)$ $N$ $S_{N}(t)$

Estimering af mængden af information

Estimering af informationsmængden af en Gaussisk tilfældig gang i forhold til kvadratet af fejlafstanden, dvs. dens kvadratiske forvrængningsfunktion, givet parametrisk: [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 ,

hvor . Derfor er det ikke muligt at binærkode med mindre end antallet af bit og derefter afkode med en forventet RMS-fejl mindre end . På den anden side, for enhver , er der en tilstrækkelig stor og binær kode med ikke mere end elementer, således at den forventede gennemsnitlige kvadratfejl ved gendannelse fra denne kode ikke er mere end . ${\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$

Ansøgninger

Som allerede nævnt er rækken af naturfænomener, som nogle varianter af tilfældige vandreture har forsøgt at beskrive, betydelig. Især inden for fysik, [27] [28] kemi, [29] materialevidenskab , [30] [31] biologi [32] og andre forskellige videnskaber. [33] [34] Her er nogle anvendelser af den tilfældige gåtur:

I finansiel økonomi bruges "random walk-hypotesen" til at modellere aktiekurser og andre faktorer. Men empiriske undersøgelser har fundet uoverensstemmelser med den teoretiske model, især i kort- og langsigtede forhold.
I populationsgenetik beskriver random walk de statistiske egenskaber ved genetisk drift .
I fysik bruges tilfældige gåture som forenklede modeller af Brownsk bevægelse og diffusion , såsom den tilfældige bevægelse af molekyler i væsker og gasser. For eksempel diffust begrænset aggregering. Også i fysik spiller tilfældige gåture og nogle af de selvinteragerende gåture en vigtig rolle i kvantefeltteorien .
I matematisk økologi bruges tilfældige gåture til at beskrive de individuelle bevægelser af dyr, til empirisk at understøtte biodiffusionsprocesser og nogle gange til at modellere populationsdynamik .
I polymerfysik beskriver en tilfældig gåtur en ideel kæde, den enkleste model til at studere polymerer . [35]
På andre områder af matematikken bruges den tilfældige gang til at finde løsninger på Laplaces ligning , til at estimere det harmoniske mål og til forskellige konstruktioner inden for analyse og kombinatorik .
Inden for datalogi bruges tilfældige gåture til at vurdere størrelsen af internettet . [36]
I billedsegmentering bruges tilfældige ture til at bestemme etiketter (såsom "objekt" eller "baggrund"), der skal knyttes til hver pixel. [37] Denne algoritme omtales almindeligvis som "random walker"-segmenteringsalgoritmen.

I alle disse tilfælde erstattes den tilfældige gang ofte af Brownsk bevægelse:

I hjerneforskning bruges tilfældige gåture til at modellere neuronale affyringskaskader.
I videnskaben om syn har øjendrift en tendens til at opføre sig som en tilfældig gåtur. [38] Ifølge nogle forfattere beskrives fikserende øjenbevægelser generelt også ved en tilfældig gåtur. [39]
Inden for psykologi forklarer tilfældige vandreture nøjagtigt forholdet mellem den tid, det tager at træffe en beslutning og sandsynligheden for, at en bestemt beslutning bliver truffet. [40]
Tilfældige vandreture kan bruges til at udtage prøver fra et statsområde, der er meget stort eller ukendt, såsom at vælge en tilfældig side på internettet eller til at undersøge arbejdsforholdene for en tilfældig arbejder i et givet land.

Når den bruges i datalogi, er sidstnævnte tilgang kendt som Markov-kæden Monte Carlo (MCMC). Ofte giver prøveudtagning fra et komplekst tilstandsrum også et sandsynligt skøn over rummets størrelse. Estimering af permanentheden af en stor matrix af nuller og ettaller var det første store problem forbundet med at bruge denne tilgang.

Tilfældige gåture bruges ofte til at prøve massive online grafer såsom sociale netværk .
I trådløse computernetværk bruges random walk til at modellere bevægelsen af en knude.
Motile bakterier udfører forudindtaget tilfældige gåture . [41]
Tilfældige gåture bruges til at modellere gambling .
I fysik er tilfældige gåture kernen i Fermi-estimeringsmetoden.
Twitter bruger tilfældige gåture til at foreslå, hvem der kunne være værd at følge [42]
Dave Byer og Percy Diaconis beviste, at 7 blander er nok til at blande et sæt kort (se afsnittet Blanding for mere ). Dette resultat udmønter sig i et udsagn om en tilfældig gang i en symmetrisk gruppe, hvilket er, hvad de beviser, med en afgørende brug af gruppens struktur ved hjælp af Fourier-analyse.
Ved brug af tilfældige gåture er det muligt at organisere bevægelsesbanen i rummet af parametre for den optimerede objektivfunktion , som bruges til at løse optimeringsproblemer [43] . Når man bruger en særlig lov om fordeling af tilfældige variabler kan man opnå en modifikation af den tilfældige , kaldet Levy-flyvninger
Ved hjælp af random walks kan man løse grænseværdiproblemet for Maxwells ligninger i integralform. Integralet beregnes ved hjælp af Monte Carlo-metoden, mens integranden udtages ved hjælp af en random walk. Det er således muligt at finde de gensidige kapacitanser af ledere i integrerede kredsløb ved at omgå kravene til endelige og grænseelementmetoder til rumdiskretisering, hvilket spiller en afgørende rolle ved valg af metode under hensyntagen til stigningen i antallet af porte i moderne integrerede kredsløb. I modsætning til finite- og boundary element-metoderne finder random walk-metoden straks feltets integral og ikke feltet i hvert punkt, som så integreres for at finde kapaciteten. [44] Random walk-metoder blev de facto standarden i begyndelsen af det 21. århundrede til at finde parasitære kapacitanser i integrerede kredsløb.
Anvendes til at løse ligningen for optisk strålingsoverførsel i et medium ved hjælp af Monte Carlo-metoden.h*

Indstillinger

Flere slags tilfældige processer har vist sig at ligne rene tilfældige gåture, men hvor den simple struktur kan generaliseres mere. En ren struktur kan karakteriseres ved trin defineret af uafhængige og identisk fordelte stokastiske variable .

På grafer

En tilfældig gåtur af længden k på en muligvis uendelig graf G med rod 0 er en stokastisk proces med tilfældige variable sådan, at , og dette er et toppunkt ensartet tilfældigt valgt blandt naboer . Så er tal sandsynligheden for, at en tilfældig gåtur af længden k starter ved v og slutter ved w . Især hvis G er en graf med rod til 0 , er sandsynligheden for, at den trinvise tilfældige gang vender tilbage til 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$

I analogi med det tidligere beskrevne afsnit (øgede dimensioner), antag, at nu er vores by ikke længere et perfekt firkantet gitter. Når vores person når et bestemt kryds, vælger han med lige stor sandsynlighed mellem forskellige tilgængelige veje. Således, hvis der er syv udgange i krydset, vil en person gå til hver med en sandsynlighed på en syvendedel. Dermed får vi en tilfældig gang på grafen. Kommer vores mand til sit hjem? Det viser sig, at svaret under ret gode forhold forbliver ja, [45] , men afhængigt af grafen, for det næste spørgsmål ('Vil to personer mødes?') er svaret "uendeligt ofte" måske ikke længere et næsten bestemt begivenhed. [46]

Et eksempel, hvor en person næsten helt sikkert vil nå huset, er, når længderne af alle blokke er i området fra a til b (hvor a og b er to endelige positive tal). Vigtigt: vi antager ikke, at grafen er plan , det vil sige, at der kan eksistere tunneler og broer i byen. En måde at bevise dette resultat på er ved at oprette forbindelse til elektriske netværk . Tag et bykort og placer en 1 ohm modstand på hver blok. Lad os nu måle "modstanden mellem punkt og uendelighed". Med andre ord, lad os vælge et tal R og tage alle punkterne i det elektriske netværk med en afstand mellem dem og vores punkt større end R, og forbinde dem sammen. Vi får et begrænset elektrisk netværk, hvor vi kan måle modstanden mellem vores punkt og andre punkter i netværket. Lad R vende mod det uendelige. Den resulterende grænse kaldes modstanden mellem punkt og uendelighed .

Det viser sig, at følgende formodning er sand (et elementært bevis kan findes i Doyle og Snells bog):

Sætning : En graf er forbigående, hvis og kun hvis modstanden mellem punkt og uendelighed er endelig. Desuden er valget af et punkt ligegyldigt, hvis grafen er forbundet.

Med andre ord, i et forbigående system behøver man kun at overvinde endelig modstand for at nå uendeligheden fra ethvert punkt. I et tilbagevendende system er modstanden mellem ethvert punkt og uendelig uendelig.

En tilfældig gang på en graf er et specialtilfælde af en Markov-kæde . I modsætning til en generel Markov-kæde har en tilfældig gang på en graf en egenskab kaldet tidssymmetri eller reversibilitet . Groft sagt betyder denne egenskab, også kaldet princippet om detaljeret ligevægt , at sandsynligheden for at krydse en given vej i den ene eller den anden retning har et meget simpelt forhold mellem dem (hvis grafen er regulær , så er de lige store). Denne egenskab har vigtige konsekvenser.

Siden 1980'erne er der blevet forsket meget i at relatere grafegenskaber til tilfældige gåture. Ud over det elektriske netværk beskrevet ovenfor er der også forbindelser til isoperimetriske uligheder, funktionelle uligheder såsom Sobolev- og Poincaré- ulighederne og til egenskaber ved løsninger til Laplace-ligningen . Meget af denne forskning har fokuseret på Cayley-graferne for endeligt genererede grupper. I mange tilfælde overføres disse diskrete resultater til eller er afledt af manifolds og Lie-grupper .

Når vi taler om tilfældige grafer , især om Erdős-Rényi-modellen , er der opnået analytiske resultater for nogle egenskaber ved tilfældige vandrere. De omfatter fordelingen af rollatorens første [47] og sidste [48] hits (eng. hiting time), hvor det første hit er første gang rollatoren træder første gang på et tidligere besøgt sted, og det sidste falder sammen med rollatoren. tilfældet, hvor vandreren ikke har andre steder at gå, bortset fra det tidligere besøgte sted.

En god reference til en tilfældig gåtur på en graf er denne online bog. Til studiet af grupper er Wöss bøger velegnede. Hvis selve overgangskernen er tilfældig (baseret på miljøet ), så kaldes den tilfældige gang en "tilfældig gang i et tilfældigt miljø". Når loven om tilfældig gang omfatter tilfældighed , kaldes loven annealed (eng. annealed ); på den anden side, hvis den betragtes som fast, kaldes loven hærdet (eng. quenched ). $p(x,y)$ $\omega$ $\omega$ $\omega$

Vi kan vælge alle mulige kanter af grafen med samme sandsynlighed som det lokale maksimum af usikkerhed (entropi). Vi kan også gøre dette globalt - i en maksimal entropy random walk (eng. maximum entropy random walk, MERW ) er det nødvendigt, at alle stier er lige sandsynlige, eller med andre ord, for alle to hjørner er hver vej af en given længde lige så sandsynligt. [49] En sådan gåtur har meget stærkere lokaliserende egenskaber.

Selvinteragerende tilfældige gåture

Der er en separat form for tilfældig vandring, hvor hvert trin afhænger af det foregående på en kompleks måde. De er sværere at løse analytisk end almindelige tilfældige gåture; dog kan opførselen af enhver random walker-model opnås ved hjælp af computere. For eksempel:

Selvundgående vandring. [halvtreds]

En selvundgående tur af længden n er en tilfældig sti med længden n trin, startende ved origo, der kun passerer gennem nabopunkter i og aldrig passerer gennem det samme punkt to gange. I det todimensionale tilfælde er sådan en sti normalt meget kort [51] , mens den i den forhøjede dimension vokser ubegrænset. Denne model bruges ofte i polymerfysik (siden 1960'erne). ${\displaystyle \mathbb {Z} ^{d))$ ${\displaystyle \mathbb {Z} ^{d))$

Tilfældig gåtur med cykelsletning. [52] [53]
Styrket tilfældig gang. [54]
Forskningsproces.
Multi-agent random walk. [55]

Langsigtede korrelerede gåture

Langsigtede korrelerede tidsserier findes i mange biologiske, klimatologiske og økonomiske systemer:

Hjerteslagsoptagelse [56]
Ikke-kodende DNA-sekvenser [57]
Tidsserier for aktievolatilitet [58]
Temperaturrekorder rundt om i verden [59]

Korrelerende tilfældige gåture

Tilfældige vandreture, hvor bevægelsesretningen på et tidspunkt korrelerer med bevægelsesretningen på det næste tidspunkt. Bruges til at simulere bevægelse af dyr. [60] [61]

Se også

Noter

↑ Wirth, E.; Szabó, G.; Czinkóczky, A. Mål landskabsdiversitet med logiske spejderagenter // ISPRS – International Archives of the Photogrammetry, Remote Sening and Spatial Information Sciences : tidsskrift. - 2016. - 8. juni ( vol. XLI-B2 ). - S. 491-495 . - doi : 10.5194/isprs-archives-xli-b2-491-2016 . - .
↑ Wirth E. (2015). Pi fra agent grænseovergange af NetLogo-pakke . Wolfram biblioteksarkiv
↑ Pearson, K. Problemet med den tilfældige gåtur // Nature . - 1905. - Bd. 72 , nr. 1865 . — S. 294 . - doi : 10.1038/072294b0 . — .
↑ Pal, Révész (1990) Tilfældig gåtur i tilfældige og ikke-tilfældige miljøer , World Scientific
↑ Kohls, Moritz; Hernandez, Tanja. Forventet dækning af Random Walk Mobility Algorithm (engelsk) : tidsskrift. - 2016. - . - arXiv : 1611.02861 .
↑ Random Walk-1-Dimensional - fra Wolfram MathWorld . Mathworld.wolfram.com (26. april 2000). Hentet: 2. november 2016. (ubestemt)
↑ Edward A. Colding et al., Random walk models in biology, Journal of the Royal Society Interface, 2008
↑ Kotani, M. og Sunada, T. Spektralgeometri af krystalgitre. — Nutidige. Matematik. - 2003. - T. 338. - S. 271-305. — (Samtidig matematik). — ISBN 9780821833834 . - doi : 10.1090/conm/338/06077 .
↑ Kotani, M. og Sunada, T. Stor afvigelse og tangentkeglen ved uendelig af et krystalgitter , Math . Z. : journal. - 2006. - Bd. 254 , nr. 4 . - S. 837-870 . - doi : 10.1007/s00209-006-0951-9 .
↑ Polias tilfældige gangkonstanter . Mathworld.wolfram.com. Hentet: 2. november 2016. (ubestemt)
↑ Durrett, Rick. Sandsynlighed: Teori og eksempler . - Cambridge University Press , 2010. - S. 191 . — ISBN 9781139491136 .
↑ Polya, George. Sandsynlighed ; kombinatorier; Undervisning og læring i matematik (engelsk) . — Cambridge, Mass.: MIT Press , 1984. — S. 582–585 . — ISBN 0-262-16097-8 .
↑ Erdős, P.; Taylor, SJ Nogle skæringsegenskaber for tilfældige gangstier // Acta Mathematica Academiae Scientiarum Hungaricae : tidsskrift . - 1960. - Bd. 11 , nr. 3-4 . - S. 231-248 . — ISSN 0001-5954 . - doi : 10.1007/BF02020942 .
↑ MacKenzie, D. MATHEMATICS: Take the Measure of the Wildest Dance on Earth // Science : journal. - 2000. - Vol. 290 , nr. 5498 . - S. 1883-1884 . doi : 10.1126 / science.290.5498.1883 . — PMID 17742050 .
↑ Kapitel 2 DIFFUSION Arkiveret 9. februar 2015 på Wayback Machine . dartmouth.edu.
↑ Diffusionsligning for den tilfældige gåtur Arkiveret 21. april 2015 på Wayback Machine . physics.uakron.edu.
↑ D. Ben-Avraham og S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems Arkiveret 4. oktober 2011 på Wayback Machine , Cambridge University Press, 2000.
↑ Weiss, George H.; Rubin, Robert J. Random Walks: Theory and Selected Applications // Fremskridt i kemisk fysik. - 1982. - T. 52. - S. 363-505. — ISBN 9780470142769 . - doi : 10.1002/9780470142769.ch5 .
↑ Blumen, A.; Klafter, J.; Zumofen, G. Modeller for reaktionsdynamik i briller // Optisk spektroskopi af briller. - 1986. - T. 1. - S. 199-265. - (Fysik og kemi af materialer med lavdimensionelle strukturer). - ISBN 978-94-010-8566-3 . - doi : 10.1007/978-94-009-4650-7_5 .
↑ Alexander, S.; Orbach, R. Densitet af tilstande på fraktaler: "fraktoner" // Journal de Physique Lettres. - 1982. - T. 43 , nr. 17 . - S. 625-631 . doi : 10.1051/jphyslet : 019820043017062500 .
↑ Rammal, R.; Toulouse, G. Random walks on fraktale strukturer og percolation clusters (engelsk) // Journal de Physique Lettres : journal. - 1983. - Bd. 44 , nr. 1 . - S. 13-22 . - doi : 10.1051/jphyslet:0198300440101300 .
↑ Smoluchowski, MV Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen (tysk) // Z. Phys. Chem. : butik. - 1917. - S. 129-168 . , Rice, SA Diffusionsbegrænsede reaktioner . - Elsevier , 1985. - V. 25. - (Comprehensive Chemical Kinetics). — ISBN 978-0-444-42354-2 .
↑ Skellam, JG Random Dispersal in Theoretical Populations // Biometrika : journal. - 1951. - Bd. 38 , nr. 1/2 . - S. 196-218 . - doi : 10.2307/2332328 . — PMID 14848123 . — .
↑ Skellam, JG Studies in Statistical Ecology: I. Spatial Pattern (engelsk) // Biometrika : journal. - 1952. - Bd. 39 , nr. 3/4 . - S. 346-362 . - doi : 10.2307/2334030 . — .
↑ Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. Territorium dækket af N-diffunderende partikler // Nature . - 1992. - Bd. 355 , nr. 6359 . - S. 423-426 . - doi : 10.1038/355423a0 . - . , Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George. Antal forskellige steder besøgt af N tilfældige vandrere // Fysisk gennemgang A : tidsskrift . - 1992. - Bd. 45 , nr. 10 . - P. 7128-7138 . - doi : 10.1103/PhysRevA.45.7128 . - . — PMID 9906785 . ; for indsigt vedrørende problemet med N random walkers, se Shlesinger, Michael F. New paths for random walkers // Nature . - 1992. - Bd. 355 , nr. 6359 . - S. 396-397 . - doi : 10.1038/355396a0 . — . og farvekunstværket, der illustrerer artiklen.
↑ Berger, T. Informationshastigheder for Wiener-processer // IEEE Transactions on Information Theory : journal. - 1970. - Bd. 16 , nr. 2 . - S. 134-139 . - doi : 10.1109/TIT.1970.1054423 .
↑ Risken H. (1984) Fokker-Planck-ligningen . Springer, Berlin.
↑ De Gennes PG (1979) Skaleringsbegreber i polymerfysik . Cornell University Press, Ithaca og London.
↑ Van Kampen NG (1992) Stokastiske processer i fysik og kemi , revideret og udvidet udgave. Nordholland, Amsterdam.
↑ Weiss, George H.Aspekter og anvendelser af Random Walk . - North-Holland Publishing Co., Amsterdam, 1994. - (Random Materials and Processes). - ISBN 978-0-444-81606-1 .
↑ Doi M. og Edwards SF (1986) The Theory of Polymer Dynamics . Clarendon Press, Oxford
↑ Goel NW og Richter-Dyn N. (1974) Stokastiske modeller i biologi . Academic Press, New York.
↑ Redner S. (2001) En vejledning til første-passage-processen . Cambridge University Press, Cambridge, Storbritannien.
↑ Cox D. R. (1962) Fornyelsesteori . Methuen, London.
↑ Jones , RAL Blødt kondenseret stof . — Genoptryk.. — Oxford [ua]: Oxford University Press , 2004. — S. 77–78 . — ISBN 978-0-19-850589-1 .
↑ Bar-Yossef, Ziv; Gurevich, Maxim. Stikprøver fra en søgemaskines indeks // Journal of the ACM : journal. - Association for Computing Machinery (ACM), 2008. - Vol. 55 , nr. 5 . - S. 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 : journal. - 2006. - Bd. 28 , nr. 11 . - P. 1768-1783 . - doi : 10.1109/TPAMI.2006.233 . — PMID 17063682 .
↑ Rucci, M; Victor, JD The unsteady eye: An information-processing stage, not a bug // Trends in Neurosciences : journal. - Cell Press , 2015. - Vol. 38 , nr. 4 . - S. 195-206 . - doi : 10.1016/j.tins.2015.01.005 . — PMID 25698649 .
↑ Engbert, R.; Mergenthaler, K.; Sinn, P.; Pikovsky, A. En integreret model af fikserende øjenbevægelser og mikrosaccades (engelsk) // Proceedings of the National Academy of Sciences of the United States of America : journal. - 2011. - Bd. 108 , nr. 39 . - P. E765-70 . - doi : 10.1073/pnas.1102730108 . - . — PMID 21873243 .
↑ Nosofsky, R.M.; Palmeri, TJ En eksemplarisk baseret tilfældig gangmodel for hurtig klassificering // Psychological Review : journal. - 1997. - Bd. 104 , nr. 2 . - S. 266-300 . - doi : 10.1037/0033-295x.104.2.266 . — PMID 9127583 . Arkiveret fra originalen den 10. december 2004.
↑ Codling, E. A; Plank, M.J; Benhamou, S. Random walk-modeller i biologi // Journal of the Royal Society Interface : journal. - 2008. - 6. august ( bind 5 , nr. 25 ). - s. 813-834 . - doi : 10.1098/rsif.2008.0014 . — PMID 18426776 .
↑ Gupta, Pankaj et al. WTF: Who-to-follow-systemet på Twitter , Proceedings of the 22nd international conference on World Wide Web
↑ Karpenko A.P. Moderne søgemaskineoptimeringsalgoritmer. Algoritmer inspireret af naturen. M.: forlag af MSTU im. N. E. Bauman, 2014. 446 s.
↑ En stokastisk algoritme til højhastigheds-kapacitansudvinding i integrerede kredsløb // Microelectronics Reliability. - 1993-07. - T. 33 , no. 9 . - S. 1420-1421 . — ISSN 0026-2714 . - doi : 10.1016/0026-2714(93)90150-w .
↑ Det er interessant at bemærke, at mødet mellem to uafhængige tilfældige vandrere i en generel graf ikke altid reducerer til problemet med en enkelt tilfældig gåtur, der vender tilbage til sit udgangspunkt.
↑ Krishnapur, Manjunath; Peres, Yuval. Tilbagevendende grafer, hvor to uafhængige tilfældige gange kolliderer endeligt ofte // Elektronisk kommunikation i sandsynlighed : journal. - 2004. - Bd. 9 . - S. 72-81 . — ISSN 1083-589X . - doi : 10.1214/ECP.v9-1111 . - . — arXiv : math/0406487 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Fordelingen af første slagtider for randomwalks på Erdős–Rényi-netværk // Journal of Physics A: Mathematical and Theoretical : journal. - 2017. - Bd. 50 , nej. 11 . — S. 115001 . - doi : 10.1088/1751-8121/aa5af3 . — . - arXiv : 1606.01560 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Fordelingen af vejlængder for selvundgående gåture på Erdős–Rényi-netværk // Journal of Physics A: Mathematical and Theoretical : journal. - 2016. - Bd. 49 , nr. 28 . — S. 285002 . - doi : 10.1088/1751-8113/49/28/285002 . - . - arXiv : 1603.06613 .
↑ Burda, Z.; Duda, J.; Held, JM; Waclaw, B. Localization of the Maximal Entropy Random Walk // Physical Review Letters : journal . - 2009. - Bd. 102 , nr. 16 . - S. 160602 . - doi : 10.1103/PhysRevLett.102.160602 . - . - arXiv : 0810.4113 . — PMID 19518691 .
↑ Madras, Neal og Slade, Gordon (1996) The Self-Avoiding Walk , Birkhäuser Boston. ISBN 0-8176-3891-1 .
↑ Hemmer, S.; Hemmer, PC En gennemsnitlig selvundgående tilfældig gang på det firkantede gitter varer 71 trin // Journal of Chemical Physics : journal. - 1984. - Bd. 81 , nr. 1 . - S. 584-585 . - doi : 10.1063/1.447349 . - .
↑ Lawler, Gregory (1996). Skæringspunktet mellem tilfældige gåture , Birkhäuser Boston. ISBN 0-8176-3892-X .
↑ Lawler , Gregory Conformally Invariant Processes in the Plane , book.ps.
↑ Pemantle, Robin. En undersøgelse af tilfældige processer med forstærkning // Sandsynlighedsundersøgelser : journal. - 2007. - Bd. 4 . - S. 1-79 . - doi : 10.1214/07-PS094 . — arXiv : math/0610076 .
↑ Alamgir, M og von Luxburg, U (2010). "Multi-agent random walks for local clustering on graphs" , IEEE 10th International Conference on Data Mining (ICDM) , pp. 18-27.
↑ Peng, C.-K.; Mietus, J; Hausdorff, JM; Havlin, S; Stanley, H.E.; Goldberger, A.L. Langrækkende anti-relationer og ikke-gaussisk opførsel af hjerteslag // Phys . Rev. Lett. : journal. - 1993. - Bd. 70 , nr. 9 . - S. 1343-1346 . - doi : 10.1103/PhysRevLett.70.1343 . - . — PMID 10054352 .
↑ Peng, CK; Buldyrev, SV; Goldberger, A.L.; Havlin, S; Sciortino, F; Simons, M; Stanley, H.E. Langrækkende korrelationer i nukleotidsekvenser // Nature . - 1992. - Bd. 356 , nr. 6365 . - S. 168-170 . - doi : 10.1038/356168a0 . — . — PMID 1301010 .
↑ Liu, Yanhui; Cizeau, Pierre; Meyer, Martin; Peng, C.-K.; Eugene Stanley, H. Korrelationer i økonomiske tidsserier // Physica A : journal. - 1997. - Bd. 245 , nr. 3-4 . - S. 437 . - doi : 10.1016/S0378-4371(97)00368-3 . — . - arXiv : cond-mat/9706021 .
↑ Koscielny-Bunde, Eva; Bunde, Armin; Havlin, Shlomo; Roman, H. Eduardo; Goldreich, Yair; Schellnhuber, Hans-Joachim. Angivelse af en universel persistenslov, der regulerer atmosfærisk variabilitet // Fysisk . Rev. Lett. : journal. - 1998. - Bd. 81 , nr. 3 . — S. 729 . - doi : 10.1103/PhysRevLett.81.729 . — .
↑ Bovet, Pierre; Benhamou, Simon. Rumlig analyse af dyrenes bevægelser ved hjælp af en korreleret tilfældig gangmodel // Journal of Theoretical Biology : journal. - 1988. - Bd. 131 , nr. 4 . - S. 419-433 . - doi : 10.1016/S0022-5193(88)80038-9 .
↑ Kareiva, PM; Shigesada, N. Analyse af insektbevægelser som en korreleret tilfældig gåtur (engelsk) // Oecologia : journal. - 1983. - Bd. 56 , nr. 2-3 . - S. 234-238 . - doi : 10.1007/BF00379695 . — . — PMID 28310199 .

Litteratur

Aldous, David; Fyld, James Allen. Vendbare Markov-kæder og tilfældige ture på grafer . - 2002.
Ben-Avraham D.; Havlin S. , Diffusion and Reactions in Fractals and Disordered Systems Arkiveret 4. oktober 2011 på Wayback Machine , Cambridge University Press, 2000.
Doyle, Peter G.; Snell, J. Laurie. Tilfældige gåture og elektriske netværk. - Mathematical Association of America , 1984. - Vol. 22. - (Carus Mathematical Monographs). - ISBN 978-0-88385-024-4 .
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 Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz" Arkiveret 4. marts 2016 på Wayback Machine , Mathematische Annalen , 84(1-2):149-160, marts 1921.
Révész, Pal (2013), Random Walk in Random and Non-random Environments (tredje udgave) , World Scientific Pub Co. ISBN 978-981-4447-50-8
Sunada, ToshikazuTopologisk krystallografi: Med henblik på diskret geometrisk analyse . - Springer, 2012. - Vol. 6. - (Undersøgelser og vejledninger i de anvendte matematiske videnskaber). — ISBN 978-4-431-54177-6 .
Weiss G. Aspects and Applications of the 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

Links

Polyas Random Walk Constants
Random walk in Java Applet Arkiveret 31. august 2007 på Wayback Machine
Kvante tilfældig gåtur
Gaussisk tilfældig gang-estimator
Elektronkonduktansmodeller, der bruger maksimal entropi tilfældige gange Wolfram-demonstrationsprojekt

Ordbøger og encyklopædier	Flot dansk Stor russer Britannica (online)
I bibliografiske kataloger	BNF : 119358404 J9U : 987007563128805171 LCCN : sh85111357 NDL : 00571555