En spontan promenad

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 oktober 2022; verifiering kräver 1 redigering .

En slumpmässig vandring är ett matematiskt objekt som kallas en stokastisk eller slumpmässig process som beskriver en bana som består av en sekvens av slumpmässiga steg i något matematiskt utrymme (till exempel på uppsättningen heltal ).

Det enklaste exemplet på en slumpmässig vandring är en slumpmässig vandring längs tallinjen med heltal, , som börjar vid punkt 0 och skiftar med +1 eller −1 vid varje steg med lika sannolikhet . Andra exempel är en molekyls bana i en vätska eller gas ( Brownsk rörelse ), sökväg hos djur under födosök , fluktuationer i aktiekurser på aktiemarknaden , en aktörs ekonomiska situation : alla de beskrivna fallen kan approximeras genom slumpmässig promenad modeller, även om de kanske inte är helt slumpmässiga i verkligheten. $\mathbb {Z}$

Som du kan se från exemplen används random walk-modellen inom teknik och många vetenskapliga områden, inklusive ekologi, psykologi, datavetenskap, fysik, kemi, biologi, ekonomi och sociologi. Den slumpmässiga vandringen förklarar det observerade beteendet hos många processer i dessa regioner, och fungerar således som en grundläggande modell för den registrerade stokastiska aktiviteten. Så i matematik kan värdet på π approximeras med hjälp av en slumpmässig promenad och agentbaserad modellering. [1] [2] Konceptet med en slumpmässig promenad introducerades först av Karl Pearson 1905. [3]

Typer av slumpmässiga promenader kan vara av olika slag. Termen i sig syftar oftast på en speciell kategori av Markov-kedjor eller Markov-processer, och många tidsberoende processer kallas slumpmässiga promenader med en modifierare som indikerar deras speciella egenskaper. Slumpmässiga vandringar (Markov eller inte) kan också förekomma inom en mängd olika områden: de som vanligtvis studeras inkluderar grafer , tallinjen av heltal eller reella , vektorrum , krökta ytor, flerdimensionella Riemannska grenrör och finita , ändligt genererade grupper, Lie-grupper . Tidsparametern kan också vara annorlunda. I det enklaste fallet sker vandringen i diskret tid och är en sekvens av slumpvariabler ( X
t) = ( X
ett, X
2, ...) , indexerad med naturliga tal. Men det finns också slumpmässiga vandringar där stegen sker vid ett godtyckligt ögonblick, och i detta fall positionen X
tmåste definieras för alla tider t ∈ [0,+∞) . Speciella fall av slumpmässig promenad är Levy-flygning och diffusionsmodeller som Brownsk rörelse .

Random walk är ett grundläggande ämne i diskussioner om Markovprocessen, och dess matematiska studier är mycket omfattande.

Slumpmässig gång på ett galler

En välkänd modell av en slumpmässig promenad är en promenad på ett vanligt galler, där platsen vid varje steg flyttar sig till en annan punkt i enlighet med en viss sannolikhetsfördelning.

I en enkel slumpmässig vandring kan en plats bara flytta till angränsande rutnätspunkter och bilda en rutnätsbana. I en enkel symmetrisk slumpmässig vandring på ett lokalt begränsat gitter är sannolikheten för att en punkt går till var och en av dess omedelbara grannar lika. Det bäst studerade exemplet är den slumpmässiga vandringen på ett d - dimensionellt gitter av heltal (kallas ibland ett hyperkubiskt gitter) . [fyra] ${\displaystyle \mathbb {Z} ^{d))$

Om tillståndsutrymmet är begränsat till ett ändligt antal dimensioner, kallas en sådan slumpmässig vandringsmodell en enkel avgränsad symmetrisk slumpgång , och övergångssannolikheterna beror på punktens placering, eftersom rörelsen är begränsad vid gräns- och hörnpunkterna . [5]

Endimensionell slumpmässig promenad

Det enklaste exemplet på en slumpmässig vandring är en slumpmässig vandring längs tallinjen med heltal , , som börjar vid punkt 0 och flyttar +1 eller −1 med lika stor sannolikhet vid varje steg. $\mathbb {Z}$

Denna vandring kan illustreras på följande sätt. Märket sätts på nollan på tallinjen, och ett "rättvist" mynt kastas. Om det kommer upp huvuden, flyttar etiketten en enhet till höger, och om den kommer upp svansar, flyttar den en enhet till vänster. Efter fem kast kan märket vara på -5, -3, -1, 1, 3, 5. För fem kast, inklusive tre huvuden och två svansar, i valfri sekvens kommer märket att vara på 1. Det finns 10 sätt att komma till punkt 1 (genom att rulla tre huvuden och två svansar), 10 sätt att komma till punkt −1 (tre svansar och två huvuden), 5 sätt att komma till punkt 3 (fyra huvuden) och en "svans"), 5 sätt att komma till punkt -3 (fyra "svansar" och en "örn"), ett sätt att komma till punkt 5 (fem "huvuden") och ett sätt att komma till punkt -5 (fem "svansar"). ") . De möjliga resultaten av de fem rullarna illustreras nedan.

För att definiera denna promenad formellt tar vi oberoende slumpvariabler , där varje variabel är antingen 1 eller −1, med en sannolikhet lika med 50 % för varje värde, mängden och Serien kallas en enkel slumpmässig vandring på . Denna serie (summan av sekvensen −1 och 1) betyder tillryggalagd sträcka om varje del av promenaden har en längd lika med en. Seriens matematiska förväntan är noll. Det vill säga att medelvärdet av alla myntkast tenderar att bli noll när antalet kast ökar. Detta följer av förväntans finita additivitetsegenskap: $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})=\summa _{j=1}^{n}E(Z_{j})=0.

På liknande sätt använder vi oberoendet av slumpvariabler och det faktum att vi ser: $E(Z_{n}^{2})=1$

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

Detta gör det klart att , det förväntade avståndet efter att ha flyttat n steg, bör vara i storleksordningen . Faktum är att [6] $E(|S_{n}|)\,\!$ ${\sqrt n}$

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

Hur många gånger kommer den slumpmässiga promenaden att passera gränsen om det är möjligt att vandra på obestämd tid? Den enklaste slumpmässiga promenaden kommer att skära varje punkt ett oändligt antal gånger. Den resulterande effekten har många namn: plankorsningsfenomenet , återfall eller spelarförstöringsproblemet . Anledningen till att ge det sista fallet namnet är detta: en spelare med en ändlig summa pengar kommer att förlora förr eller senare om han spelar ett rättvist spel mot en pott med en obegränsad summa pengar. Spelarens pengar är en slumpmässig promenad, och någon gång i tiden kommer de att nå noll och spelet kommer att vara över. $\mathbb {Z}$

Låt a och b vara positiva heltal , då är det förväntade antalet steg när en enkel endimensionell slumpmässig gång som börjar vid 0 först når b eller −a ab . Sannolikheten att en given promenad når b innan den når −a är , vilket följer av att en enkel slumpmässig promenad är en martingal . $a/(a+b)$

Några av resultaten som nämns ovan kan härledas från egenskaperna hos Pascals triangel . Antalet alla distinkta promenader över n

steg, där varje steg är antingen +1 eller −1 är lika med 2 n . För en enkel slumpmässig promenad är vart och ett av dessa steg likvärdigt. För att vara lika med talet k är det nödvändigt och tillräckligt att antalet steg med +1 i promenaden överstiger de med −1 med talet k . Därför måste ett steg på +1 ske (n + k)/2 gånger bland n promenader, därför är antalet promenader som uppfyller villkoret lika med antalet sätt att välja (n + k)/2 element från en n -elementuppsättning. [7] Detta betecknas som . För att detta uttryck ska vara meningsfullt är det nödvändigt att summan n + k är ett jämnt tal, vilket betyder att talen n och k måste vara antingen jämna eller udda samtidigt. Därför är sannolikheten som kommer att vara lika med . Genom att representera posterna i Pascals triangel i termer av faktorialer och använda Stirlings formel kan man få bra uppskattningar av dessa sannolikheter för stora värden på . $S_{n}\,\!$ $S_{n}=k$ $n \choose (n+k)/2$ $S_{n}=k$ $2^{-n}{n \choose (n+k)/2}$ $n$

Om utrymmet är begränsat till + för korthetens skull kan antalet sätt på vilka den slumpmässiga promenaden stannar vid något nummer efter fem steg visas som {0,5,0,4,0,1}. $\mathbb {Z}$

Låt oss demonstrera denna överensstämmelse med Pascals triangel för små värden på n . Vid nollsteget är enda möjligheten att stanna på noll. Men redan vid första draget finns det en möjlighet att hamna antingen på -1 eller på 1. Vid det andra draget, från 1, kan du gå till punkt 2, eller tillbaka till noll. Du kan flytta från -1 till -2 eller tillbaka till noll. Därför finns det ett fall när vi är i punkt −2, två fall när vi är på noll och ett fall när vi är i punkt 2.

k	−5	−4	−3	−2	−1	0	ett	2	3	fyra	5
$P[S_{0}=k]$						ett
$2P[S_{1}=k]$					ett		ett
$2^{2}P[S_{2}=k]$				ett		2		ett
$2^{3}P[S_{3}=k]$			ett		3		3		ett
$2^{4}P[S_{4}=k]$		ett		fyra		6		fyra		ett
$2^{5}P[S_{5}=k]$	ett		5		tio		tio		5		ett

Den centrala gränssatsen och lagen för den itererade logaritmen beskriver viktiga aspekter av beteendet hos en enkel slumpmässig promenad på . I synnerhet när n ökar, tenderar sannolikheterna (i proportion till siffrorna i varje rad) mot en normalfördelning . $\mathbb {Z}$

Slumpmässiga vandringar på kristallgitter (oändligt många Abeliska täckande grafer av ändliga grafer) kan betraktas som en direkt generalisering. I själva verket är det under sådana förhållanden till och med möjligt att hävda den centrala gränssatsen och den stora avvikelsesatsen. [8] [9]

Som en Markov-kedja

En endimensionell diskret slumpmässig gång är en Markov-kedja i heltalstillstånd vars initiala fördelning ges av sannolikhetsfunktionen för den slumpmässiga variabeln , och övergångssannolikhetsmatrisen är $X_{0}$

P\equiv (p_{{ij}})_{{i,j\in {\mathbb {Z}}}}=\left({\begin{matrix}\ddots &\ddots &\ddots &\\&q_ {{-1}}&0&p_{{-1}}&\\&&q_{0}&0&p_{0}\\&&&q_{1}&0&p_{1}\\&&&&\ddots &\ddots &\ddots \end{matris} }\höger)

det är

p_{{i,i+1}}\equiv {\mathbb {P}}(X_{{n+1}}=i+1\mid X_{n}=i)=p_{i},

p_{{i,i-1}}\equiv {\mathbb {P}}(X_{{n+1}}=i-1\mid X_{n}=i)=q_{i},\quad i \i {\mathbb {Z}),

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

Förhöjda mått

I högre dimensioner har uppsättningen av slumpmässiga gångpunkter ganska intressanta geometriska egenskaper. Faktum är att vi får en diskret fraktal , det vill säga en uppsättning som visar stokastisk självlikhet när den zoomas in. I liten skala kan du observera "jaggedness" på rutnätet som promenaden genomförs på. Lawlers två citerade böcker är bra källor till material i ämnet. Banan för en slumpmässig promenad är en samling av besökta punkter, betraktad som en uppsättning fram till den tidpunkt då vandringen nådde punkten. I en dimension är banan helt enkelt alla punkter mellan den lägsta höjden och den maximala höjden som vandringen har nått (båda, i genomsnitt, i storleksordningen ). ${\sqrt {n}}$

För att visualisera ett tvådimensionellt fall kan man föreställa sig en person som slumpmässigt går runt i staden. Denna stad är praktiskt taget oändlig och är anlagd i ett fyrkantigt rutnät av trottoarer. Vid varje korsning väljer en person slumpmässigt en av fyra möjliga vägar (inklusive den han kom ifrån). Formellt är detta en slumpmässig vandring över uppsättningen av alla punkter på planet med heltalskoordinater .

Kommer den här personen någonsin att återvända till utgångspunkten för vandringen? Detta fall är 2D-motsvarigheten till plankorsningsproblemet som diskuterats ovan. 1921 bevisade György Pólya att en person nästan säkert skulle återvända vid en tvådimensionell slumpmässig promenad, men för tre dimensioner eller mer minskar sannolikheten att återvända när antalet dimensioner ökar. I det tredimensionella fallet minskar sannolikheten till cirka 34 %. [10] Matematikern Shizuo Kakutani är känd för sitt citat om detta resultat: "En fyllare kommer förr eller senare att hitta hem, men en berusad fågel kan gå förlorad för alltid." [elva]

En annan version av denna fråga, som också ställdes av Poya, är: om två personer lämnar samma utgångspunkt, kommer de någonsin att träffas? [12] Man kan resonera att skillnaden mellan deras platser (två oberoende slumpmässiga promenader) också är en enkel slumpmässig promenad, så de kommer nästan säkert att mötas i en tvådimensionell promenad, men för tre dimensioner eller mer är sannolikheten för att återvända samma som i föregående fall, minskar med ökande antal mätningar. Pal Erdős och Samuel James Taylor visade också 1960 att, för dimensioner mindre än eller lika med 4, två oberoende slumpmässiga promenader, som börjar vid två givna punkter, nästan säkert har oändligt många skärningspunkter, men för dimensioner större än 5 är de nästan säkert skär endast ett ändligt antal gånger. [13]

Den asymptotiska funktionen för en slumpmässig 2D-vandring när antalet steg ökar ges av Rayleigh-fördelningen . Sannolikhetsfördelningen är en funktion av radien från origo, och för varje steg är steglängden konstant.

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

Relation till Wienerprocessen

Wienerprocessen är en stokastisk process som i sitt beteende liknar Brownsk rörelse , ett fysiskt fenomen med diffusion av små partiklar i en vätska. (Ibland kallas en Wienerprocess för en Brownsk rörelse, även om en Wienerprocess strikt sett är en modell, och en Brownsk rörelse är ett modellerat fenomen.)

Wienerprocessen är den skalbara gränsen för en endimensionell slumpmässig promenad. Det betyder att om du tar en slumpmässig promenad med mycket små steg, så kan du få en approximation till Wienerprocessen (och, med mindre noggrannhet, till Brownsk rörelse). Mer exakt, om steglängden är ε, måste man ta en promenad med längden L /ε 2 för att approximera Wienerbanan L . När steglängden närmar sig noll (och antalet steg ökar proportionellt) täcker den slumpmässiga promenaden Wiener-processen på lämpligt sätt. Formellt, om B är rymden av alla banor av längd L med den maximala topologin, och om M är rymden av mått över B med normal topologi, så är konvergensen i rummet M . I analogi är en Wiener-process i flera dimensioner den skalbara gränsen för en slumpmässig promenad i samma antal dimensioner.

En random walk är en diskret fraktal (en funktion med ett heltal av dimensioner; 1, 2, ...), medan Wienerprocessens bana är en riktig fraktal, och det finns ett visst samband mellan de två. Låt oss till exempel ta en slumpmässig promenad och vi kommer att "gå" tills vi passerar en cirkel med radien r gånger stegets längd. Då kommer det genomsnittliga antalet steg som krävs för att slutföra promenaden att vara lika med r 2 . Detta faktum är en diskret version av det faktum att Wiener process walk är en fraktal av Hausdorff dimension 2.

I tvådimensionell rymd är det genomsnittliga antalet punkter som en slumpmässig promenad passerar på gränsen för sin bana r 4/3 . Detta överensstämmer med det faktum att banans gräns för en Wienerprocess är en 4/3 fraktal, vilket föreslogs av Mandelbrot genom användning av simuleringar, men bevisades först 2000 av Lawler, Schramm och Werner . [fjorton]

Wienerprocessen har många symmetrier till skillnad från random walk. Till exempel, en Wiener-processgång är rotationsinvariant, men en slumpmässig gång är det inte, eftersom dess rutnät inte är rotationsinvariant (slumpmässig gång är rotationsinvariant med 90 grader, medan Wienerprocesser är rotationsinvariant med, säg, ytterligare 17 grader). ). Detta innebär att problem som ges på en slumpmässig promenad i många fall är lättare att lösa på följande sätt: överför problemet till Wiener-processen, lös problemet där och överför det sedan tillbaka. Å andra sidan är vissa problem lättare att lösa på en slumpmässig promenad på grund av dess diskreta karaktär.

Konvergensen av en slumpmässig promenad till en Wiener-process görs med hjälp av den centrala gränssatsen och Donskers sats. För en partikel vid en känd fast position vid t = 0, säger centralgränssatsen att efter ett stort antal oberoende slumpmässiga vandringssteg kommer vandrarens position att fördelas enligt normalvariansfördelningen :

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

där t är tiden som förflutit sedan starten av den slumpmässiga promenaden, är stegstorleken för promenaden och är tiden som förflutit mellan två på varandra följande steg. $\varepsilon$ $\delta t$

Detta fall motsvarar Greens funktion av diffusionsekvationen , som beskriver Wienerprocessen, vilket antyder att efter ett tillräckligt stort antal steg konvergerar den slumpmässiga vandringen till Wienerprocessen.

I 3D-fallet är variansen som motsvarar Greenens funktion av diffusionsekvationen:

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

Genom att utjämna detta värde med variansen som är förknippad med positionen för den slumpmässiga vandraren, kan man få den ekvivalenta diffusionskoefficienten, övervägd för en asymptotisk wienerprocess till vilken den slumpmässiga promenaden konvergerar efter ett tillräckligt stort antal steg:

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

(förnuftigt endast i fallet med tre dimensioner).

Obs: Ovanstående två variansuttryck motsvarar en fördelning associerad med en vektor som förbinder de två ändarna av en slumpmässig promenad i tre dimensioner. Skillnaden associerad med varje komponent, eller , är bara en tredjedel av det totala värdet (fortfarande 3D). $\vec R$ $R_{x}$ $R_{y}$ $R_{z}$

För 2D: [15]

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

För 1D: [16]

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

Donskers sats

Överväg en slumpmässig promenad , där . $Y_{n}=\summa \limits _{{i=1}}^{{n}}{X_{i}}$ $EX_{i}=0,DX_{i}=\sigma ^{2}<\infty$

Den centrala gränssatsen säger att genom fördelning vid . ${\frac {Y_{n}}{\sigma {\sqrt {n}}}}\högerpil N(0,1)$ $n\högerpil\infty$

Men för slumpmässiga promenader kan detta påstående stärkas avsevärt.

Vi konstruerar en slumpmässig process med avseende på , definierar den enligt följande: , och för resten definierar vi processen med en linjär fortsättning: $Y_{n}$ $S_{n}(t),t\in [0,1]$ $S_{n}\left({\frac {k}{n}}\right)={\frac {Y_{{k}}}{\sigma {\sqrt {n}}}}$ $t$

$S_{n}(t)=(k+1-nt)S_{n}\left({\frac {k}{n}}\right)+(nt-k)S_{n}\left({\ frac {k+1}{n}}\höger),t\in \left({\frac {k}{n));{\frac {k+1}{n}}\höger)$

Från centrala gränssatsen om distribution för $\förallt t$ $S_{n}(t)\högerpil N(0,t)$ $n\högerpil\infty$

Detta innebär konvergensen av de endimensionella fördelningarna av processen till de endimensionella fördelningarna av Wienerprocessen . Donskers teorem, även kallad invariansprincipen, säger att det finns en svag konvergens av processer, $S_{n}(t)$ $S_{n}(t)\högerpil W(t),n\högerpil \infty$

Svag konvergens av processer betyder konvergensen av funktionaler som är kontinuerliga med avseende på Wienermåttet, det vill säga det tillåter beräkning av värdena för funktionaler från Brownsk rörelse (till exempel maximum, minimum, sista nollan, ögonblicket för första nådd nivån och andra) genom att passera till gränsen från en enkel slumpmässig promenad.

Gaussisk random walk

En slumpmässig promenad med en steglängd som varierar med en normalfördelning används som tidsseriedata i verkliga världen, såsom finansmarknader. Black-Schools-formeln använder till exempel en Gaussisk slumpmässig promenad som sitt underliggande antagande.

I detta fall är stegstorleken den inversa kumulativa normalfördelningen där 0 ≤ z ≤ 1 och är ett enhetligt fördelat slumptal, och μ och σ är medelvärdet respektive standardavvikelsen för normalfördelningen. $\Phi ^{-1}(z,\mu ,\sigma )$

Om μ inte är noll kommer den slumpmässiga vandringen att följa en linjär trend. Om v s är startvärdet för den slumpmässiga promenaden, är det förväntade värdet efter n steg v s + n μ.

För det speciella fallet där μ är noll, efter n steg, definieras sannolikhetsfördelningen av tillryggalagd sträcka som N (0, n σ 2 ), där N () är notationen för normalfördelningen, n är antalet steg och σ är hämtat från ovanstående inversa kumulativa normalfördelning.

Bevis: En Gaussisk slumpgång kan representeras som summan av en sekvens av oberoende och identiskt fördelade slumpvariabler, X i från en invers kumulativ normalfördelning, där medelvärdet är noll och σ är hämtat från den ursprungliga inversa kumulativa normalfördelningen:

Z = ,

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

men vi har en fördelning för summan av två oberoende normalfördelade stokastiska variabler, Z = X + Y, erhållen tack vare

\mathcal{N}

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

I vårt fall ger μ X = μ Y = 0 och σ 2 X = σ 2 Y = σ 2 :

\mathcal{N}

(0, 2σ 2 )

Genom induktion har vi för n steg:

Z~ (O, n o2 ) .

\mathcal{N}

För steg fördelade enligt någon fördelning med noll medelvärde och ändlig varians (inte nödvändigtvis bara en normalfördelning), ges rotmedelvärdet för avståndet tillryggalagt efter n steg av:

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

Men för en Gaussisk slumpmässig promenad är detta bara standardavvikelsen för fördelningen av tillryggalagd sträcka efter n steg. Därför, om μ är noll, och om det tillryggalagda effektiva avståndet är en standardavvikelse, finns det en 68,27 % chans att det effektiva avståndet som tillryggaläggs efter n steg kommer att vara mellan ± σ . Det finns också en 50% chans att avståndet tillryggalagt efter n steg kommer att vara mellan ± 0,6745σ . ${\sqrt {n}}$ ${\sqrt {n}}$

Anomal diffusion

I oordnade system, såsom porösa medier och fraktaler, kan det vara proportionellt inte mot , utan . Exponenten kallas den anomala diffusionsexponenten och kan vara större eller mindre än 2. [17] Den anomala diffusionen kan också uttryckas som σ r 2 ~ Dt α där α är anomaliparametern. Vissa diffusioner i en slumpmässig miljö är till och med proportionella mot kraften i tidens logaritm, som Sinais vandring eller Brox diffusion. $\sigma ^{2}$ $t$ $t^{2/d_{w))$ $d_{w}$

Antal olika platser

Antalet distinkta platser som besöks av en enda slumpmässig vandrare har studerats omfattande för kvadratiska och kubiska gitter och fraktaler. [18] [19] Detta värde är användbart för att analysera problem med dödläge (engelsk fällning ) och kinetiska reaktioner. Det är också relaterat till tillståndens vibrationstäthet, [20] [21] diffusionsreaktioner av processer [22] och fördelningen av populationer i ekologi. [23] [24] En generalisering av detta problem till antalet distinkta platser som besöks av slumpmässiga vandrare, betecknade som , har nyligen studerats för d -dimensionella euklidiska gitter. [25] Antalet olika platser som besöks av N vandrare är inte bara relaterat till antalet olika platser som varje vandrare besöker. $S(t)$ $N$ $S_{N}(t)$

Uppskattning av informationsmängden

Uppskattning av informationsmängden för en Gaussisk slumpmässig gång med avseende på kvadraten på felavståndet, dvs dess kvadratiska distorsionsfunktion, given parametriskt: [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 ,

var . Därför är det inte möjligt att binärkoda med mindre än antalet bitar och sedan avkoda med ett förväntat RMS-fel mindre än . Å andra sidan, för alla , finns det en tillräckligt stor och binär kod med högst element, så att det förväntade medelkvadratfelet vid återställning från denna kod inte är mer än . ${\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$

Applikationer

Som redan nämnts är den mängd naturfenomen som vissa varianter av slumpmässiga promenader har försökt beskriva betydande. I synnerhet inom fysik, [27] [28] kemi, [29] materialvetenskap , [30] [31] biologi [32] och andra olika vetenskaper. [33] [34] Här är några tillämpningar av random walk:

Inom finansiell ekonomi används "random walk-hypotesen" för att modellera aktiekurser och andra faktorer. Men empiriska studier har funnit diskrepanser med den teoretiska modellen, särskilt i kort- och långvariga relationer.
Inom populationsgenetik beskriver random walk de statistiska egenskaperna hos genetisk drift .
Inom fysiken används slumpmässiga vandringar som förenklade modeller av Brownsk rörelse och diffusion som slumpmässig rörelse av molekyler i vätskor och gaser. Till exempel diffust begränsad aggregering. Även inom fysiken spelar slumpmässiga promenader och några av de självinteragerande promenaderna en viktig roll i kvantfältteorin .
Inom matematisk ekologi används slumpmässiga vandringar för att beskriva djurs individuella rörelser, för att empiriskt stödja biodiffusionsprocesser och ibland för att modellera populationsdynamik .
Inom polymerfysik beskriver en slumpmässig promenad en ideal kedja, den enklaste modellen för att studera polymerer . [35]
Inom andra områden av matematiken används random walk för att hitta lösningar på Laplaces ekvation , för att uppskatta det harmoniska måttet och till olika konstruktioner inom analys och kombinatorik .
Inom datavetenskap används slumpmässiga vandringar för att uppskatta storleken på Internet . [36]
I bildsegmentering används slumpmässiga vandringar för att bestämma etiketter (som "objekt" eller "bakgrund") som ska associeras med varje pixel. [37] Denna algoritm kallas vanligen för segmenteringsalgoritmen för "random walker".

I alla dessa fall ersätts den slumpmässiga promenaden ofta av Brownsk rörelse:

I hjärnforskning används slumpmässiga promenader för att modellera neuronala avfyrningskaskader.
Inom synvetenskapen tenderar okulär drift att bete sig som en slumpmässig promenad. [38] Enligt vissa författare beskrivs fixerande ögonrörelser i allmänhet också genom en slumpmässig promenad. [39]
Inom psykologi förklarar slumpmässiga promenader förhållandet mellan den tid det tar att fatta ett beslut och sannolikheten att ett visst beslut kommer att fattas. [40]
Slumpmässiga promenader kan användas för att ta prov från ett statligt utrymme som är mycket stort eller okänt, till exempel för att välja en slumpmässig sida på Internet eller för att undersöka arbetsförhållandena för en slumpmässig arbetare i ett visst land.

När det används inom datavetenskap är det senare tillvägagångssättet känt som Markovkedjan Monte Carlo (MCMC). Ofta ger provtagning från något komplext tillståndsutrymme också en probabilistisk uppskattning av utrymmets storlek. Att uppskatta permanentheten av en stor matris av nollor och ettor var det första stora problemet som associerades med att använda detta tillvägagångssätt.

Slumpmässiga promenader används ofta för att ta prov på massiva onlinegrafer som sociala nätverk .
I trådlösa datornätverk används random walk för att modellera rörelsen av en nod.
Motila bakterier utför partiska slumpmässiga promenader . [41]
Slumpmässiga promenader används för att modellera hasardspel .
Inom fysiken är slumpmässiga promenader kärnan i Fermi-uppskattningsmetoden.
Twitter använder slumpmässiga promenader för att föreslå vem som kan vara värd att följa [42]
Dave Byer och Percy Diaconis bevisade att 7 blandningar är tillräckligt för att blanda en kortlek (se avsnittet Blanda för mer ). Detta resultat översätts till ett uttalande om en slumpmässig vandring i en symmetrisk grupp, vilket är vad de bevisar, med en avgörande användning av gruppens struktur med hjälp av Fourier-analys.
Med användning av slumpmässiga promenader är det möjligt att organisera rörelsebanan i utrymmet för parametrar för den optimerade objektivfunktionen , som används för att lösa optimeringsproblem [43] . När man använder en speciell lag för fördelning av slumpvariabler kan en modifiering av slumpmässiga , kallad Levy flights erhållas
Med hjälp av random walks kan man lösa gränsvärdesproblemet för Maxwells ekvationer i integralform. Integralen beräknas med Monte Carlo-metoden, medan integranden tas med en slumpmässig promenad. Således är det möjligt att hitta de ömsesidiga kapacitanserna för ledare i integrerade kretsar, förbi kraven på finita och gränselementmetoder för rymddiskretisering, vilket spelar en avgörande roll vid val av metod, med hänsyn till ökningen av antalet grindar i moderna integrerade kretsar. Till skillnad från finita och gränselementmetoderna, hittar random walk-metoden omedelbart fältets integral, och inte fältet vid varje punkt, som sedan integreras för att hitta kapaciteten. [44] Random walk-metoder blev de facto standarden i början av 2000-talet för att hitta parasitiska kapacitanser i integrerade kretsar.
Används för att lösa ekvationen för optisk strålningsöverföring i ett medium med Monte Carlo-metoden.h*

Alternativ

Flera sorters slumpmässiga processer har visat sig likna rena random walks, men där den enkla strukturen kan generaliseras mer. En ren struktur kan karakteriseras av steg som definieras av oberoende och identiskt fördelade slumpvariabler .

På grafer

En slumpmässig promenad av längden k på en möjligen oändlig graf G med roten 0 är en stokastisk process med slumpmässiga variabler sådana att , och detta är en vertex likformigt slumpmässigt vald bland grannar . Då är tal sannolikheten att en slumpmässig promenad av längden k börjar på v och slutar på w . I synnerhet, om G är en graf med rötter på 0 , är sannolikheten att den stegvisa slumpmässiga vandringen återgår till 0 . ${\displaystyle X_{1},X_{2},\dots ,X_{k))$ $X_{1}=0$ ${X_{i+1))$ $X_{i}$ $p_{v,w,k}(G)$ $p_{0,0,2k}$ $2k$

I analogi med det tidigare beskrivna avsnittet (ökade dimensioner), anta att nu är vår stad inte längre ett perfekt kvadratiskt rutnät. När vår person når en viss korsning väljer han med lika stor sannolikhet mellan olika tillgängliga vägar. Således, om det finns sju utgångar vid korsningen, kommer en person att gå till var och en med en sannolikhet på en sjundedel. Därmed får vi en slumpmässig promenad på grafen. Kommer vår man att ta sig till sitt hem? Det visar sig att, under ganska goda förhållanden, svaret förblir ja, [45] men, beroende på grafen, för nästa fråga ('Kommer två personer att mötas?') kanske svaret "oändligt ofta" inte längre är ett nästan viss händelse. [46]

Ett exempel där en person nästan säkert kommer att nå huset är när längden på alla block ligger i intervallet från a till b (där a och b är två ändliga positiva tal). Viktigt: vi antar inte att grafen är plan , det vill säga tunnlar och broar kan finnas i staden. Ett sätt att bevisa detta resultat är genom att ansluta till elektriska nätverk . Ta en stadskarta och placera ett 1 ohm motstånd på varje block. Låt oss nu mäta "motståndet mellan punkt och oändlighet". Med andra ord, låt oss välja något nummer R och ta alla punkter i det elektriska nätverket med ett avstånd mellan dem och vår punkt större än R, och koppla ihop dem. Vi får ett ändligt elektriskt nätverk där vi kan mäta resistansen mellan vår punkt och andra punkter i nätverket. Låt R tendera mot oändligheten. Den resulterande gränsen kallas motståndet mellan punkt och oändlighet .

Det visar sig att följande gissningar är sanna (ett elementärt bevis finns i Doyle och Snells bok):

Sats : En graf är transient om och endast om motståndet mellan punkt och oändlighet är ändligt. Dessutom är valet av en punkt oviktigt om grafen är kopplad.

Med andra ord, i ett transient system behöver man bara övervinna ändligt motstånd för att nå oändligheten från vilken punkt som helst. I ett återkommande system är motståndet mellan valfri punkt och oändlighet oändligt.

En slumpmässig promenad på en graf är ett specialfall av en Markov-kedja . Till skillnad från en allmän Markov-kedja har en slumpmässig gång på en graf en egenskap som kallas tidssymmetri eller reversibilitet . Grovt sett betyder denna egenskap, även kallad principen för detaljerad jämvikt , att sannolikheterna för att korsa en given väg i den ena eller andra riktningen har ett mycket enkelt förhållande mellan dem (om grafen är regelbunden , då är de lika). Denna egenskap har viktiga konsekvenser.

Sedan 1980-talet har det gjorts mycket forskning för att relatera grafegenskaper till slumpmässiga promenader. Utöver det elektriska nätverket som beskrivits ovan finns det också kopplingar till isoperimetriska ojämlikheter, funktionella ojämlikheter som Sobolev- och Poincaré- ojämlikheterna och till egenskaper hos lösningar till Laplace-ekvationen . Mycket av denna forskning har fokuserat på Cayley-graferna för ändligt genererade grupper. I många fall överförs dessa diskreta resultat till eller härleds från grenrör och Lie-grupper .

På tal om slumpmässiga grafer , särskilt om Erdős-Rényi-modellen , har analytiska resultat erhållits för vissa egenskaper hos slumpmässiga vandrare. De inkluderar fördelningen av rullatorns första [47] och sista [48] träffar (eng. träfftid) där den första träffen är första gången rullatorn först kliver på en tidigare besökt plats, och den sista sammanfaller med fallet när vandraren inte har någon annanstans att ta vägen, förutom den tidigare besökta platsen.

En bra referens för en slumpmässig promenad på en graf är den här onlineboken. För studiet av grupper är Wöss böcker lämpliga. Om själva övergångskärnan är slumpmässig (baserat på miljön ), kallas den slumpmässiga promenaden en "slumpmässig promenad i en slumpmässig miljö". När slumpgångslagen inkluderar slumpmässighet kallas lagen annealed (eng. annealed ); å andra sidan, om den anses som fast, kallas lagen tempererad (eng. quenched ). $p(x,y)$ $\omega$ $\omega$ $\omega$

Vi kan välja alla möjliga kanter på grafen med samma sannolikhet som det lokala osäkerhetsmaximum (entropi). Vi kan också göra detta globalt - i en maximal entropy random walk (eng. maximum entropy random walk, MERW ) är det nödvändigt att alla banor är lika sannolika eller, med andra ord, för vilka två hörn som helst, varje väg av en given längd är lika troligt. [49] En sådan promenad har mycket starkare lokaliserande egenskaper.

Självinteragerande slumpmässiga promenader

Det finns en separat typ av slumpmässig vandring där varje steg beror på det föregående på något komplext sätt. De är svårare att lösa analytiskt än vanliga random walks; dock kan beteendet hos alla slumpmässiga rollatormodeller erhållas med hjälp av datorer. Till exempel:

Självundvikande vandring. [femtio]

En självundvikande promenad med längd n är en slumpmässig bana med längd n steg, som börjar vid utgångspunkten, som bara passerar genom angränsande punkter i och aldrig passerar genom samma punkt två gånger. I det tvådimensionella fallet är en sådan väg vanligtvis mycket kort [51] , medan den i den förhöjda dimensionen växer utan gräns. Denna modell används ofta inom polymerfysik (sedan 1960-talet). ${\displaystyle \mathbb {Z} ^{d))$ ${\displaystyle \mathbb {Z} ^{d))$

Slumpmässig promenad med cykelradering. [52] [53]
Förstärkt random walk. [54]
Forskningsprocess.
Multi-agent random walk. [55]

Långtidskorrelerade promenader

Långtidskorrelerade tidsserier finns i många biologiska, klimatologiska och ekonomiska system:

Hjärtslagsinspelning [56]
Icke-kodande DNA-sekvenser [57]
Tidsserier för aktievolatilitet [58]
Temperaturrekord runt om i världen [59]

Korrelerande slumpmässiga promenader

Slumpmässiga promenader där rörelseriktningen vid en tidpunkt korrelerar med rörelseriktningen vid nästa tidpunkt. Används för att simulera djurs rörelse. [60] [61]

Se även

Anteckningar

↑ Wirth, E.; Szabó, G.; Czinkóczky, A. Mät landskapets mångfald med logiska scoutagenter // ISPRS – International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences : tidskrift. - 2016. - 8 juni ( vol. XLI-B2 ). - S. 491-495 . - doi : 10.5194/isprs-archives-xli-b2-491-2016 . - .
↑ Wirth E. (2015). Pi från agentgränsövergångar av NetLogo-paket . Wolfram biblioteksarkiv
↑ Pearson, K. Problemet med den slumpmässiga promenaden // Nature . - 1905. - Vol. 72 , nr. 1865 . — S. 294 . - doi : 10.1038/072294b0 . — .
↑ Pal, Révész (1990) Slumpmässig promenad i slumpmässiga och icke-slumpmässiga miljöer , World Scientific
↑ Kohls, Moritz; Hernandez, Tanja. Förväntad täckning av Random Walk Mobility Algorithm (engelska) : journal. - 2016. - . - arXiv : 1611.02861 .
↑ Random Walk-1-Dimensional - från Wolfram MathWorld . Mathworld.wolfram.com (26 april 2000). Hämtad: 2 november 2016. (obestämd)
↑ Edward A. Colding et al, Random walk models in biology, Journal of the Royal Society Interface, 2008
↑ Kotani, M. och Sunada, T. Spectral geometri of crystal gitter. — Samtida. Matematik. - 2003. - T. 338. - S. 271-305. — (Samtida matematik). — ISBN 9780821833834 . - doi : 10.1090/conm/338/06077 .
↑ Kotani, M. och Sunada, T. Stor avvikelse och tangentkonen vid oändligheten av ett kristallgitter , Math . Z. : journal. - 2006. - Vol. 254 , nr. 4 . - P. 837-870 . - doi : 10.1007/s00209-006-0951-9 .
↑ Polias slumpmässiga gångkonstanter . Mathworld.wolfram.com. Hämtad: 2 november 2016. (obestämd)
↑ Durrett, Rick. Sannolikhet: Teori och exempel . - Cambridge University Press , 2010. - S. 191 . — ISBN 9781139491136 .
↑ Polya, George. Sannolikhet ; kombinatorier; Undervisning och lärande i matematik (engelska) . — Cambridge, Mass.: MIT Press , 1984. — S. 582–585 . — ISBN 0-262-16097-8 .
↑ Erdős, P.; Taylor, SJ Some intersection properties of random walk paths // Acta Mathematica Academiae Scientiarum Hungaricae : journal . - 1960. - Vol. 11 , nr. 3-4 . - S. 231-248 . — ISSN 0001-5954 . - doi : 10.1007/BF02020942 .
↑ MacKenzie, D. MATHEMATICS: Att ta måttet på den vildaste dansen på jorden // Science: journal. - 2000. - Vol. 290 , nr. 5498 . - P. 1883-1884 . doi : 10.1126 / science.290.5498.1883 . — PMID 17742050 .
↑ Kapitel 2 DIFFUSION Arkiverad 9 februari 2015 på Wayback Machine . dartmouth.edu.
↑ Diffusionsekvation för den slumpmässiga promenaden Arkiverad 21 april 2015 på Wayback Machine . physics.uakron.edu.
↑ D. Ben-Avraham och S. Havlin, Diffusion and Reactions in Fractals and Disordered Systems Arkiverad 4 oktober 2011 på Wayback Machine , Cambridge University Press, 2000.
↑ Weiss, George H.; Rubin, Robert J. Random Walks: Theory and Selected Applications // Framsteg inom kemisk fysik. - 1982. - T. 52. - S. 363-505. — ISBN 9780470142769 . - doi : 10.1002/9780470142769.ch5 .
↑ Blumen, A.; Klafter, J.; Zumofen, G. Modeller för reaktionsdynamik i glasögon // Optisk spektroskopi av glasögon. - 1986. - T. 1. - S. 199-265. - (Fysik och kemi av material med lågdimensionella strukturer). - ISBN 978-94-010-8566-3 . - doi : 10.1007/978-94-009-4650-7_5 .
↑ Alexander, S.; Orbach, R. Densitet av tillstånd 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 fraktala strukturer och perkolationskluster (engelska) // Journal de Physique Lettres : journal. - 1983. - Vol. 44 , nr. 1 . - S. 13-22 . - doi : 10.1051/jphyslet:0198300440101300 .
↑ Smoluchowski, MV Versuch einer mathematischen Theorie der Koagulationskinetik kolloider Lösungen (tyska) // Z. Phys. Chem. : affär. - 1917. - S. 129-168 . , Rice, SA Diffusionsbegränsade reaktioner . - Elsevier , 1985. - V. 25. - (Comprehensive Chemical Kinetics). — ISBN 978-0-444-42354-2 .
↑ Skellam, JG Random Dispersal in Theoretical Populations // Biometrika : journal. - 1951. - Vol. 38 , nr. 1/2 . - S. 196-218 . - doi : 10.2307/2332328 . — PMID 14848123 . — .
↑ Skellam, JG Studier i statistisk ekologi: I. Spatial Pattern (engelska) // Biometrika : journal. - 1952. - Vol. 39 , nr. 3/4 . - s. 346-362 . - doi : 10.2307/2334030 . — .
↑ Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H. Eugene; Weiss, George H. Territorium täckt av N-diffunderande partiklar // Nature . - 1992. - Vol. 355 , nr. 6359 . - s. 423-426 . - doi : 10.1038/355423a0 . - . , Larralde, Hernan; Trunfio, Paul; Havlin, Shlomo; Stanley, H.; Weiss, George. Antal distinkta platser som besökts av N slumpmässiga vandrare // Fysisk granskning A : journal . - 1992. - Vol. 45 , nr. 10 . - P. 7128-7138 . - doi : 10.1103/PhysRevA.45.7128 . - . — PMID 9906785 . ; för insikter angående problemet med N random walkers, se Shlesinger, Michael F. New paths for random walkers // Nature . - 1992. - Vol. 355 , nr. 6359 . - s. 396-397 . - doi : 10.1038/355396a0 . — . och färgkonstverket som illustrerar artikeln.
↑ Berger, T. Informationshastigheter för Wienerprocesser // IEEE Transactions on Information Theory : journal. - 1970. - Vol. 16 , nr. 2 . - S. 134-139 . - doi : 10.1109/TIT.1970.1054423 .
↑ Risken H. (1984) Fokker–Plancks ekvation . Springer, Berlin.
↑ De Gennes PG (1979) Skalande begrepp i polymerfysik . Cornell University Press, Ithaca och London.
↑ Van Kampen NG (1992) Stokastiska processer i fysik och kemi , reviderad och förstorad upplaga. Norra Holland, Amsterdam.
↑ Weiss, George H.Aspekter och tillämpningar av Random Walk . - North-Holland Publishing Co., Amsterdam, 1994. - (Slumpmässiga material och processer). - ISBN 978-0-444-81606-1 .
↑ Doi M. och Edwards SF (1986) Theory of Polymer Dynamics . Clarendon Press, Oxford
↑ Goel NW och Richter-Dyn N. (1974) Stokastiska modeller i biologi . Academic Press, New York.
↑ Redner S. (2001) En vägledning till den första passageprocessen . Cambridge University Press, Cambridge, Storbritannien.
↑ Cox D. R. (1962) Förnyelseteori . Methuen, London.
↑ Jones , RAL Mjuk kondenserad materia . — Reprint.. — Oxford [ua]: Oxford University Press , 2004. — S. 77–78 . — ISBN 978-0-19-850589-1 .
↑ Bar-Yossef, Ziv; Gurevich, Maxim. Slumpmässigt urval från en sökmotors index // 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. - Vol. 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 integrerad modell av fixerande ögonrörelser och mikrosackader (engelska) // Proceedings of the National Academy of Sciences of the United States of America : journal. - 2011. - Vol. 108 , nr. 39 . - P. E765-70 . - doi : 10.1073/pnas.1102730108 . - . — PMID 21873243 .
↑ Nosofsky, R.M.; Palmeri, TJ En exemplarbaserad slumpmässig vandringsmodell för snabb klassificering // Psychological Review : journal. - 1997. - Vol. 104 , nr. 2 . - S. 266-300 . - doi : 10.1037/0033-295x.104.2.266 . — PMID 9127583 . Arkiverad från originalet den 10 december 2004.
↑ Codling, E. A; Plank, M.J; Benhamou, S. Random walk models in biology // Journal of the Royal Society Interface : journal. - 2008. - 6 augusti ( vol. 5 , nr 25 ). - s. 813-834 . - doi : 10.1098/rsif.2008.0014 . — PMID 18426776 .
↑ Gupta, Pankaj et al. WTF: The who-to-follow-systemet på Twitter , Proceedings of the 22nd international conference on World Wide Web
↑ Karpenko A.P. Moderna sökmotoroptimeringsalgoritmer. Algoritmer inspirerade av naturen. M.: MSTUs förlag im. N. E. Bauman, 2014. 446 sid.
↑ En stokastisk algoritm för höghastighetskapacitansextraktion i integrerade kretsar // Microelectronics Reliability. — 1993-07. - T. 33 , nej. 9 . - S. 1420-1421 . — ISSN 0026-2714 . - doi : 10.1016/0026-2714(93)90150-w .
↑ Det är intressant att notera att mötet mellan två oberoende slumpmässiga vandrare i en allmän graf inte alltid reducerar till problemet med att en enda slumpmässig vandring återvänder till sin startpunkt.
↑ Krishnapur, Manjunath; Peres, Yuval. Återkommande grafer där två oberoende slumpmässiga promenader kolliderar ändligt ofta // Elektronisk kommunikation i sannolikhet : journal. - 2004. - Vol. 9 . - S. 72-81 . — ISSN 1083-589X . - doi : 10.1214/ECP.v9-1111 . - . — arXiv : math/0406487 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Fördelningen av första träfftider för randomwalks på Erdős–Rényi-nätverk // Journal of Physics A: Mathematical and Theoretical : journal. - 2017. - Vol. 50 , nej. 11 . — S. 115001 . - doi : 10.1088/1751-8121/aa5af3 . — . - arXiv : 1606.01560 .
↑ Tishby, Ido; Biham, Ofer; Katzav, Eytan. Fördelningen av väglängder för självundvikande promenader på Erdős–Rényi-nätverk // Journal of Physics A: Mathematical and Theoretical : journal. - 2016. - Vol. 49 , nr. 28 . — S. 285002 . - doi : 10.1088/1751-8113/49/28/285002 . - . - arXiv : 1603.06613 .
↑ Burda, Z.; Duda, J.; Lycka till, JM; Waclaw, B. Localization of the Maximal Entropy Random Walk // Physical Review Letters : journal . - 2009. - Vol. 102 , nr. 16 . - P. 160602 . - doi : 10.1103/PhysRevLett.102.160602 . - . - arXiv : 0810.4113 . — PMID 19518691 .
↑ Madras, Neal och Slade, Gordon (1996) The Self-Avoiding Walk , Birkhäuser Boston. ISBN 0-8176-3891-1 .
↑ Hemmer, S.; Hemmer, PC En genomsnittlig självundvikande slumpmässig promenad på det kvadratiska gittret varar 71 steg // Journal of Chemical Physics : journal. - 1984. - Vol. 81 , nr. 1 . - s. 584-585 . - doi : 10.1063/1.447349 . - .
↑ Lawler, Gregory (1996). Korsning av slumpmässiga promenader , Birkhäuser Boston. ISBN 0-8176-3892-X .
↑ Lawler, Gregory Conformally Invariant Processes in the Plane , book.ps.
↑ Pemantle, Robin. En kartläggning av slumpmässiga processer med förstärkning // Sannolikhetsundersökningar : journal. - 2007. - Vol. 4 . - S. 1-79 . - doi : 10.1214/07-PS094 . — arXiv : math/0610076 .
↑ Alamgir, M och von Luxburg, U (2010). "Multi-agent random walks for local clustering on graphs" , IEEE 10th International Conference on Data Mining (ICDM) , s. 18-27.
↑ Peng, C.-K.; Mietus, J; Hausdorff, JM; Havlin, S; Stanley, H.E.; Goldberger, A.L. Antikorrelationer med lång räckvidd och icke-gaussiskt beteende av hjärtslag // Phys . Varv. Lett. : journal. - 1993. - Vol. 70 , nej. 9 . - P. 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. Långdistanskorrelationer i nukleotidsekvenser // Nature . - 1992. - Vol. 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 ekonomiska tidsserier // Physica A : journal. - 1997. - Vol. 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. Indikation på en universell beständighetslag som styr atmosfärisk variabilitet // Phys . Varv. Lett. : journal. - 1998. - Vol. 81 , nr. 3 . — S. 729 . - doi : 10.1103/PhysRevLett.81.729 . — .
↑ Bovet, Pierre; Benhamou, Simon. Rumslig analys av djurs rörelser med hjälp av en korrelerad slumpmässig vandringsmodell // Journal of Theoretical Biology : journal. - 1988. - Vol. 131 , nr. 4 . - s. 419-433 . - doi : 10.1016/S0022-5193(88)80038-9 .
↑ Kareiva, PM; Shigesada, N. Analysera insektsrörelser som en korrelerad slumpmässig promenad (engelska) // Oecologia : journal. - 1983. - Vol. 56 , nr. 2-3 . - S. 234-238 . - doi : 10.1007/BF00379695 . — . — PMID 28310199 .

Litteratur

Aldous, David; Fyll, James Allen. Vändbara Markov-kedjor och slumpmässiga promenader på grafer . – 2002.
Ben-Avraham D.; Havlin S. , Diffusion and Reactions in Fractals and Disordered Systems Arkiverad 4 oktober 2011 på Wayback Machine , Cambridge University Press, 2000.
Doyle, Peter G.; Snell, J. Laurie. Random Walks och elektriska nätverk. - Mathematical Association of America , 1984. - Vol 22. - (Carus Mathematical Monographs). - ISBN 978-0-88385-024-4 .
Feller, William (1968), En introduktion till sannolikhetsteori och dess tillämpningar (volym 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" Arkiverad 4 mars 2016 på Wayback Machine , Mathematische Annalen , 84(1-2):149-160, mars 1921.
Révész, Pal (2013), Random Walk in Random and Non-random Environments (tredje upplagan) , World Scientific Pub Co. ISBN 978-981-4447-50-8
Sunada, ToshikazuTopologisk kristallografi: med sikte på diskret geometrisk analys . - Springer, 2012. - Vol. 6. - (Enkäter och handledningar i tillämpad matematisk vetenskap). — ISBN 978-4-431-54177-6 .
Weiss G. Aspects and Applications of the Random Walk , North-Holland, 1994.
Woess, Wolfgang (2000), Random Walks on Infinite Graphs and Groups , Cambridge tracts in mathematics 138, Cambridge University Press. ISBN 0-521-55292-3

Länkar

Polyas Random Walk Constants
Slumpmässig vandring i Java-applet Arkiverad 31 augusti 2007 på Wayback Machine
Quantum random walk
Gaussisk slumpmässig gångskalkylator
Elektronkonduktansmodeller som använder maximal entropi Random Walks Wolfram-demonstrationsprojekt

Ordböcker och uppslagsverk	Stor dansk Stor ryss Britannica (online)
I bibliografiska kataloger	BNF : 119358404 J9U : 987007563128805171 LCCN : sh85111357 NDL : 00571555