Slučajna šetnja

Slučajna šetnja (slučajni hod) je matematička formalizacija puta koji se sastoji od niza slučajnih koraka. Na primer, putanja praćenja molekula kao što putuje u tečnost ili gas, za pretragu puta sakupljanjem životinje, cena jedne promenljive akcije i finansijski status kockara mogu se modelirati kao slučajne šetnje, iako to ne može biti istinski slučajno u stvarnosti. Termin slučajnog hoda je prvi put uvedeo Karl Pearson 1905. Slučajne šetnje su korišćene u mnogim oblastima: ekologija, ekonomija, psihologija, informatika, fizika, hemija, i biologija. Slučajne šetnje objašnjavaju uočena ponašanja mnogih procesa u ovim oblastima, i na taj način služe kao temeljni model za snimljene stokestik aktivnosti.

Primer osam slučajnih šetnji u jednoj dimenziji sa početkom u 0. Parcela pokazuje trenutnu poziciju na liniji (vertikalne ose) u odnosu na vremenske intervale (horizontalna osa).

Različiti tipovi slučajnih šetnji su od interesa. Često se pretpostavlja da su Markovljevi lanci ili Markovljevi procesi, ali i druge, mnogo komplikovanije šetnje su takođe od interesa. Neke slobodne šetnje su na grafikonima, druge na linijama, u avionu, u višim dimenzijama, ili čak zaobljenim površinama, dok su neke slučajne šetnje u grupama. Slobodne šetnje takođe variraju u odnosu na vremenski parametar. Često je šetnja u diskretnom vremenu, a potiče iz prirodnih brojeva, kao u k_0, k_1, X_2, \ dots. Međutim, neke šetnje prave svoje korake u slučajnim razmacima, a u tom slučaju položaj X_t je definisana za beskonačno vreme t \ ge 0. Određeni slučajevi ili granice slučajnih šetnji uključuju Levi let. Slučajne šetnje su vezane za modele difuzije i predstavljaju osnovnu temu diskusija Markovog rada. Nekoliko svojstava slučajnih šetnji, uključujući i rasprostiranje distribucije, prvi prolaza vremena i susret stopa, su intenzivno proučavani.

Rešetke slučajne šetnje

Popularni model slučajne šetnje je slučajna šetnja na regularnoj rešetki, gde na svakom koraku lokacija skače na drugo mesto, prema nekim verovatnoćama raspodele. U principu slučajne šetnje, lokacija može da skoči samo sa susednih mesta rešetke, formirajući put rešetke. U jednostavnoj simetričnoj slučajnoj šetnji na lokalnom nivou konačne rešetke, verovatnoća za lokaciju skokovima na svaki njegovi najbliži sused je ista. Najbolji primer je proučavanje slučajne šetnje na d-dimenzionalni celim rešetkama (ponekad se naziva hipercubic rešetke) \ mathbb Z ^ um.

Jedno dimenzijalna slobodna šetnja

Osnovni primer slučajne šetnje je slučajna šetnja na ceo broj linije, \ mathbb Z, koji počinje u 0 i na svakom koraku kreće +1 ili -1 sa istom verovatnoćom.

Ova šetnja može se ilustrovati na sledeći način. Marker je postavljen na nulu na broj linije i kovanica je prevrnuta. Ako padne na glavu, marker se pomera jednu jedinicu sa desne strane. Ako padne na repove, marker se pomera jednu jedinicu sa leve strane. Nakon pet bacanja, marker može sada biti na 1, -1, 3, -3, 5 ili -5. Sa pet bacanja, tri glave i dva repa, u bilo kom redosledu će sleteti na 1. Postoji 10 načina za sletanje na 1 (okretanjem tri glave i dva repa), 10 načina sletanja na -1 (okretanjem tri repa i dve glave), 5 načini sletanja na 3 (okretanjem četiri glave i jedan rep), 5 načine sletanja na -3 (okretanjem četiri repa i jedna glava), 1 put sletanju na 5 (okretanjem pet glava), i 1 način sletanju na -5 (okretanjem pet repa). Pogledajte sliku ispod za ilustraciju mogućih ishoda od 5 okreta.

Svi mogući ishodi slučajnih šetnji nakon 5 bacanja novčića

Slučajna šetnja u dve dimenzije (animirana vezrija)

Slučajna šetnja u dve dimenzije sa 25 hiljada koraka (animirana verzija)

Slučajna šetnja je dvodimenzionalna sa dva miliona manjih koraka. Ova slika je napravljena na takav način da tačke koje su češće obojene su tamnije. U granicama, za veoma male korake, dobija se Braunovo kretanje.

Da bismo formalno definisali ovu šetnju, uzimamo nezavisne slučajne promenljive $Z_{1},Z_{2},\dots$, gde je svaka promenljiva 1 ili -1, sa verovatnoćom za obe vrednosti 50% i postavimo $S_{0}=0\,\!$ i $S_{n}=\sum _{j=1}^{n}Z_{j}.$ Serija $\{S_{n}\}\,\!$ se zove jednostavno slučajna šetnja $\mathbb {Z}$. Ova serija (zbir sekvenci od −1s do 1s) daje udaljenost šetnje, ako je svaki deo šetnje dužina jednog. Očekivano $E(S_{n})\,\!$ od $S_{n}\,\!$ je nula. To jest, srednja vrednost svih bačenih novčića približava se nuli kako se broj bacanja povećava. Ovo sledi od konačnih dodataka imovine očekivanja:

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

Slična računica, koristeći nezavisnost slučajnih promenljivih i činjenica da $E(Z_{n}^{2})=1$, pokazuje da:

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

To nagoveštava da $E(|S_{n}|)\,\!$, očekivani prevod rastojanja nakon n koraka, treba da bude reda${\sqrt {n}}$. Na primer,

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

Ovaj rezultat pokazuje da je difuzija neefikasna za mešanje zbog načina na koji se kvadratni koren ponaša za veliko $N$.

Koliko puta će slučajna šetnja da pređe graničnu liniju ukoliko je dozvoljeno da nastavi šetnju zauvek? Jednostavna slučajna šetnja po \ mathbb Z će preći svaku tačku neograničen broj puta. Ovaj rezultat ima mnogo imena: Nivo prelaz fenomen, ponavljanje ili propast kockar je. Razlog za prezime glasi: kockar sa ograničenom količinom novca će na kraju izgubiti kada igraju fer utakmicu protiv jedne banke sa beskonačnim količinom novca. Novac kockara će obavljati slučajnu šetnju, a to će dostići nulu u nekom trenutku, i igra će biti gotova.

Ako su a i b pozitivni celi brojevi, tada je očekivani broj koraka do jednodimenzionalnog principa slučajne šetnje sa početkom u prvim  udarcima  b ili -a je AB. Verovatnoća je da će ova šetnja pogoditi B pre nego što -a je A / (A + B), što se može izvesti iz činjenice da jednostavna slučajna šetnja predstavlja lažne uzde.

Neki od navedenih rezultati može biti izveden iz svojstava Paskalovog trougla. Broj različitih slojeva n korake gde svaki korak je +1 ili -1 je 2n. Iz proste slučajne šetnje, svaka od ovih šetnji je podjednako verovatna. Da bi Sn  bio jednak sa brojem k potrebno je i dovoljno da broj +1 u šetnji premašuje one -1 do k. Broj šetnji koje zadovoljavaju $S_{n}=k$ je jednak broju načina izbora (n - k) / 2 sa n koje je broj dozvoljenih poteza, označen$n \choose (n-k)/2$. Da ovo ima značenje, potrebno je da su n i k parni brojevi. Dakle, verovatnoća da $S_{n}=k$ je jednako . Što predstavlja unose Paskalovog trougla u smislu faktorijala i korišćenja Stirling formule, mogu se postići dobre procene za ove verovatnoće za velike vrednosti n.

Ako je prostor ograničen na \ mathbb Z + za kratkotrajno, broj načina na koji će slučajna šetnja da slete na svaki broj ima pet bacanja i može da se prikaže kao {0,5,0,4,0,1}.

Ovaj odnos sa Paskalovim trouglom je dokazan za male vrednosti n. Ako kreće od nule, jedina mogućnost će biti da ostane na nuli. Međutim, u jednom opet, postoji jedna šansa od sletanja na -1 ili jedno moguće spuštanje na 1. U dva navrata, marker na 1 da pređe na 2 ili nazad na nulu. Marker na -1, da pređe na -2 ili nazad na nulu. Dakle, postoji jedna šansa od sletanja na -2, dve šanse za sletanje na nulu, a jedno moguće sletanje na 2.

$P[S_{0}=k]$ $2P[S_{1}=k]$ $2^{2}P[S_{2}=k]$ $2^{3}P[S_{3}=k]$ $2^{4}P[S_{4}=k]$ $2^{5}P[S_{5}=k]$

k	−5	−4	−3	−2	−1	0	1	2	3	4	5
1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1

Teorema centralne granice i zakon ponavljanja logaritma opisuju važne aspekte ponašanja principa slučajne šetnje \mathbb Z. Konkretno, prethodno se podrazumeva da n raste, pristup verovatnoće (proporcionalna broju u svakom redu)  sa normalnom raspodelom.

Kao direktna generalizacija, mogu se uzeti u obzir slučajne šetnje na kristalnoj letvici (Infinite iznosa Abelevi pokriva grafikone preko konačnih grafova). Zapravo je moguće uspostaviti centralnu graničnu teoremu i teoremu velikih devijacija u ovom okruženju.

Kao Markov lanac

Jednodimenzionalna slučajna šetnja može se posmatrati kao Markov lanac čije stanje prostora je dato po obliku celih $i=0,\pm 1,\pm 2,\dots .$ Za neke brojeve p zadovoljava se$\,0<p<1$, verovatnoća prelaza (verovatnoća Pi j prelaska iz stanja da se navede j) i daju:

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

Više dimenzije

Tri slučajne šetnje u tri dimenzije

Zamislite sada pijanica koji slučajno šeta u idealizovanom gradu. Grad je efektivno beskonačan i raspoređen u kvadratnu mrežu, i na svakom preseku pijanac bira jednu od četiri moguća puta (uključujući i onaj iz kojeg je došao), sa jednakom verovatnoćom. Formalno, ovo je slučajna šetnja određena svim tačakama u ravni sa celim koordinatama.

Da li će se pijanac ikada vratiti svojoj kući iz bara? To je 2-dimenzionalni ekvivalent problema nivoa prelaza koji je ranije opisan. Ispostavilo se da je skoro sigurno da će u 2-dimenzionalnoj slučajnoj šetnji, ali i sa 3 dimenzije ili više, verovatnoća povratka u proseku smanjuje kako se broj dimenzija povećava. U 3 dimenzije, verovatnoća se smanjuje za otprilike 34%.

Putanja slučajne šetnje je zbir lokacija koje su posećene, koje su zanemarene dok sšetnjom ne stignemo na mesto. U jednoj dimenziji, putanja su jednostavno sve tačke između minimalne visine šetnje koja je postignuta i maksimalno (oba su, u proseku, po nalogu √ n). U višim dimenzijama skup ima zanimljive geometrijske karakteristike. U stvari, jedan dobija diskretni fraktal, to je skup koji pokazuje stohastičko samo-sličnost na velikim skalama, ali se u malom obimu može posmatrati "jaggedness" tako da proizilazi iz mreže na kojoj se vrši šetnja. Dve Lavlerove knjige navedene u daljem tekstu su dobar izvor za ovu temu.

Odnos prema Vinerovom procesu

Glavni članak: Vinerov proces

Simulacija Vinerovog procesa u dve dimenzije

Vinerov proces je matematička formulacija Braunovog kretanja, slučajnog kretanja tela u tečnostima veće specifične gustine od njega samog.

Vinerov proces je povezan sa slučajnom šetnjom. Stohastički proces

$W_{n}(t)={\frac {1}{\sqrt {n}}}\sum \limits _{1\leq k\leq \lfloor nt\rfloor }\xi _{k},$

za svako $\xi _{1},\xi _{2},\ldots$, gde su to nezavisne i identični raspoređene slučajne promenljive sa očekivanom vrednošću 0 i varijansom 1, za $n\to \infty$, $W_{n}$ teži Vinerovom proceesu. Konvergencija je data Centralnom graničnom teoremom. Vinerov proces u proizvoljnoj dimenziji je limes slučajne šetnje u istoj dimenziji.

Slučajna šetnja se može posmatrati kao diskretan fraktal, odnosno funkcija celobrojnih dimenzija 1, 2, ... Vinerov proces je pravi fraktal Hausdorfove dimenzije 2.

Vinerov proces šetnje je invarijantan na rotacije za proizvoljni ugao, dok je slučajna šetnja invarijantna samo na rotacije pod pravim uglom, jer je definisana na celobrojnoj rešetki koja sama ne poseduje invarijantnost na ostale rotacije.

Gausova slučajna šetnja

Slučajni šetnja sa brojem koraka koji varira prema normalnoj podeli se koristi kao model za realne podatke vremenskih serija kao što su finansijska tržišta. Crna-Scholes formula za cenu je opcija modeliranja, na primer, koristi Gausovu slučajnu šetnju kao osnovnu pretpostavku

Ovde, veličina koraka je inverzna kumulativnoj normalnoj raspodeli $\Phi ^{-1}(z,\mu ,\sigma )$ gde 0 ≤ z ≤ 1je ravnomerno raspoređeni slučajni broj, a μ i σ su srednje i standardne devijacije normalne distribucije.

Ako je μ  različit od nule, slučajna šetnja će varirati oko linearnog trenda. Obrnuto, ako je početna vrednost slučajne šetnje, očekivana vrednost nakon n koraka će biti vs + nμ.

Za poseban slučaj gde je μ jednaka nuli, nakon n koraka, raspodelom udaljenost je N (0, nσ2), gde je N ()  oznaka za normalnu raspodelu, n je broj koraka, i σ je inverzna kumulativna normalna distribucija kao što je dato gore.

Dokazati: Gausova slučajna šetnja može da se posmatrati kao zbir niza nezavisnih i identično distribuiranih slučajnih promenljivih, Xi iz obrnute kumulativne normalne distribucije sa srednjom jednakom nuli i X  obrnute kumulativne normalne distribucije:

Z = $\sum _{i=0}^{n}{X_{i}}$,

ali imamo distribuciju za sumu od dve nezavisno normalno distribuirane slučajne promenljive, Z = X + Y, daje

N(μ_X + μ_Y, σ²_X + σ²_Y) (vidi ovde).

U našem slučaju, μ_X = μ_Y = 0 i σ²_X = σ²_Y = σ² donosi

N(0, 2σ²)

Po indukciji, za n koraka imamo

Z ~ N(0, nσ²).

Za korake distribuirane prema bilo kojoj distribuciji sa nulom na sredini i konačne varijanse (ne nužno samo normalne distribucije), koren srednje kvadratne udaljenost posle n koraka je

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

Ali za Gausovu slučajnu šetnju, ovo je samo standardna devijacija distribucije prevoda udaljenosti nakon n koraka. Dakle, ako je μ jednaka nuli, a od korena znači kvadratna (RMS) prevod udaljenosti je jedna standardna devijacija, postoji 68,27% verovatnoće da će efektivna udaljenost nakon n koraka pasti između± σ${\sqrt {n}}$. Isto tako, postoji 50% verovatnoće da će  udaljenost nakon n koraka pasti između± 0.6745σ${\sqrt {n}}$.

Anomalna difuzija

U poremećenim sistemima kao što su porozna medija i fraktali $\sigma ^{2}$ ne može biti proporcionalna $t$ ali može $t^{2/d_{w}}$. Eksponent $d_{w}$se zove eksponent anomalije difuzije  i može biti veći ili manji od 2.Anomalous difuzija se takođe može izraziti kao σ_r² ~ Dt^α gde α je parametar anomalnije.

Broj različitih lokacija

Broj različitih lokacija koje je posetio jedan slučajni šetač $S(t)$ je intenzivno proučavan za kvadratnu i kubnu letvicu i za fraktale. Ova količina je korisna za analizu problema hvatanja i kinetičkih reakcija. Takođe je u vezi sa vibracionom gustinom stanja, difuzijom reakcije procesa i širenja populacije u ekologiji. Generalizacija ovog problema na broj različitih lokacija posetilo je $N$ slučajnih šetača, $S_{N}(t)$, nedavno je studirano za D-dimenzionalne euklidske rešetke. Broj različitih lokacija posećenih od N šetača u vezi su sa brojem različitih sajtova koje posećuje svaki šetač.

Aplikacije

Antonija Gormleia Kvantna Oblačnost skulptura u Londonu dizajniran od strane računarom pomoću algoritma slučajne šetnje.

Slede neke aplikacije slučajne šetnje:

• U finansijskoj ekonomiji,"hipoteza slučajna šetnja" se koristi za modeliranje cena akcija i drugih faktora. Empirijska istraživanja pronašla su neka odstupanja od ovog teorijskog modela, posebno u kratkom roku i dugoročnim korelacijama. Pogledajte cene akcija.
• U populacione genetike, slobodna šetnja opisuje statističke osobine genetičkog drifta
• U fizici, slučajne šetnje se koriste kao pojednostavljeni modeli fizičkog Brovnovog kretanja i difuzije, kao što su slučajno kretanje molekula u tečnosti i gasova. Videti na primer difuzione ograničene agregacije. Takođe u fizici, slučajne šetnje i neke od interakciji šetnje igraju ulogu u kvantnoj teoriji polja.
• U matematičkoj ekologiji, slučajne šetnje se koriste da opišu pojedine pokrete životinja, za empirijske procese podrške za biodiffusion, i povremeno za modeliranje dinamike stanovništva.
• U fizici polimera, slučajna šetnja opisuje idealan lanac. To je najjednostavniji model proučavanja polimera.
• U ostalim oblastima matematike, slučajna šetnja se koristi za izračunavanje rešenja Laplasove jednačine, da proceni harmoničnu meru, i za različite konstrukcije u analizi i kombinatorici.
• U informatici, slučajne šetnje se koriste za procenu veličine Veba. U Vorld Vide Veb konferencije 2006. godine, bar-Iossef i dr. objavili su svoje nalaze i algoritme za iste.
• U slici segmentacije, slučajne šetnje se koriste za utvrđivanje nalepnice (tj "objekat" ili "pozadina") da se drže svakog piksela. Ovaj algoritam se tipično naziva algoritam segmentacije slučajne šetnje.

U svim ovim slučajevima, slučajna šetnja je često zamenjena za Braunovo kretanje.

• U istraživanju mozga, slučajne šetnje i ojačane slučajne šetnje se koriste za modeliranje kaskade neurona koje pucaju u mozgu.
• U viziji nauke, očni zanošenje teži da se ponaša kao slučajna šetnja. Prema nekim autorima, fikational pokreti oka u celini su takođe dobro opisali slučajnu šetnju.
• U psihologiji, slučajne šetnje objašnjavaju precizno odnos između vremena potrebnog da se donese odluka i verovatnoće da će određena odluka da bude doneta.
• Slučajne šetnje mogu se koristiti za uzorkovanje iz državnog prostora koji je nepoznat ili veoma velik, na primer, da izabere slučajno stranu sa interneta, ili za istraživanje uslova rada, slučajni radnik u datoj zemlji.

Kada se ovaj poslednji pristup  koristi u kompjuterskoj nauci poznat je kao umetanje ili MCMC za kratko. Često, uzorkovanje od nekog komplikovanog državnog prostora takođe omogućava da dobijete verovatnoće procene veličine prostora ekipe. Procena stalno velike matrice nule i jedinice je bio prvi veliki problem za rešiti korišćenjem ovog pristupa.

• Slučajne šetnje se takođe koriste za uzorkovanje masivnih onlajn grafikona kao što su oni na onlajn društvenim mrežama.
• U bežičnom umrežavanju, slučajna šetnja se koristi za modeliranje kretanja čvora.
• Pokretne bakterije koje se angažuju u slučajnoj šetnji.
• Slučajne šetnje se koriste za modeliranje kockanja.
• U fizici, slučajne šetnje su u osnovi metod procene Fermi.
• Na vebu, sajt Tvitter koristi slučajne šetnje da predloži koga da pratiši

Varijante slučajne šetnje

Veliki broj vrsta stohastičkih procesa su smatrani da su slični čistim slučajnim šetnjama, ali gde je dozvoljeno da jednostavna struktura bude uopštena. Čista struktura može biti okarakterisana koracima koji definišu nezavisne i identično raspodeljene slučajne promenljive.

Slučajna šetnja na grafikonima

Slučajni hoda dužine k beskonačno mogućeg grafika G sa korenom 0 je stohastički proces sa slučajnim promenljivama$X_{1},X_{2},\dots ,X_{k}$ tako da$X_{1}=0$ i ${X_{i+1}}$ je najviša tačka izabrana ravnomerno nasumično iz suseda $X_{i}$.

Onda za broj $p_{v,w,k}(G)$ je verovatnoća da se slučajna šetnja od dužine k početkom u v završava u V. Konkretno, ako je G grafikon sa korenom 0, $p_{0,0,2k}$onda je verovatnoća da $2k$-korak slobodne šetnje vraća na 0.

Pretpostavimo sada da naš grad više nije savršen kvadrat mreže. Kada naš pijanica dostigne određenu raskrsnicu on bira između različitih puteva sa jednakom verovatnoćom. Stoga, ako čvor ima sedam izlaza pijanac će ići na svaki od njih sa verovatnoćom jedne sedmine. Ovo je slučajna šetnja na grafikonu. Hoće li naš pijanica doći do svoje kuće? Ispostavilo se da pod veoma blagim uslovima, odgovor je uvek da. Na primer, ako su dužine svih blokova između A i B (gde su a i b bilo koja dva konačno pozitivna broja), onda će pijanac, gotovo sigurno, doći do svoje kuće. Obratite pažnju da ne pretpostavljamo da je grafikon ravni, odnosno grad može da sadrži tunele i mostove. Jedan od načina da se dokaže ovaj rezultat jeste korišćenje veze sa električnim mrežama. Uzmite mapu grada i postavite jedno oma otpornik na svakom bloku. Sada meri "otpor između tačke i beskonačnosti". Drugim rečima, izaberite neki broj R i preduzeti sve tačke u električnu mrežu sa udaljenosti veće od R iz naše tačke i poslati ih zajedno. Ovo je sada konačno električna mreža i možemo meriti otpor od naše tačke do žičanih tačaka. Uzmite R do beskonačnosti. Granica se zove otpor između tačke i beskonačnosti. Ispostavilo se da je sledeće tačno (elementarni dokaz može se naći u knjizi Doile i Snell):

Teorema: grafik je prolazan ako i samo ako je otpor između tačke i beskonačnosti konačan. Nije važno ako je tačka izabrana ako je povezan grafik.

Drugim rečima, u prolaznom sistemu, jedan samo treba da prevaziđe konačan otpor da se stigne do beskonačnosti iz bilo koje tačke. U povratnom sistemu, otpor od bilo koje tačke u beskonačnosti je beskonačan.

Ova karakterizacija recidiva i prolaznosti je veoma korisna, a posebno nam omogućava da analiziramo slučaj grada sastavljen u ravni sa ograničenom razdaljinom.

Slučajna šetnja na grafu je veoma poseban slučaj Markovog lanca. Za razliku od opšteg Markovog lanca, slučajna šetnja na grafikonu ima imovinu koja se zove vreme simetrija ili ponavljanje. Grubo govoreći, ovaj hotel, koji se naziva princip detaljnog balansa, znači da će verovatnoća preći dati put u jednom pravcu ili u drugom i imamo veoma jednostavnu vezu između njih (ako je graf redovno, oni su samo jednaki). Ova nekretnina ima značajne posledice.

Od 1980-ih, mnogo istraživanja je izvršeno u cilju povezivanja svojstva grafikona do slučajne šetnje. Pored električne mrežne konekcije gore opisane, postoje značajne veze sa isoperimetričnim nejednakostima, funkcionalne nejednakosti kao što su Sobolev i Poenkare nejednakosti i svojstva rešenja Laplasove jednačine. Značajan deo ovog istraživanja bio je fokusiran na Caileiem grafovima konačno ostvarenih grupa. Na primer, dokaz Dave Baier i Persi Diaconis da 7 kundacima Shuffles dovoljno da se meša špil karata i na snazi je rezultat o slučajnoj šetnji na grupi SN, a dokaz koristi strukturu grupe u suštinskom načinu. U mnogim slučajevima ovi diskretni rezultati prenose na, ili su dobijeni od mnogostrukosti i grupa.

Dobra referenca za slučajnu šetnju na grafikonima je online knjiga Aldous i napunite. Za grupe vidi knjigu Voess.

Ako tranzicija kernela$p(x,y)$je sama slučajna (na osnovu životne \ omega) onda se slučajna šetnja zove "slučajna šetnja po slučajnom okruženju". Kada zakon slučajne šetnje uključuje slučajnosti \ omega, zakon se zove annealed zakon; S druge strane, ako \ omega se smatra fiksnim, zakon se naziva gasi zakon. Pogledajte knjigu Hughes ili predavanje  Zeitouni.

Možemo da razmišljamo o izboru svake moguće prednost sa istom verovatnoćom kao maksimalnom lokalnom nesigurnošću (entropija) . Mi takođe možemo to uraditi na globalnom nivou - u maksimalnoj entropiji slučajne šetnje (MERV) želimo da svi putevi budu podjednako verovatni, ili drugim rečima: za svaka dva vertekes, svaki put date dužine je podjednako verovatan. Ova slučajna šetnja ima mnogo jače osobine lokalizacije.

Polu-interagujuća slučajna šetnja

Postoji veliki broj zanimljivih modela slučajnih putanja u kojoj svaki korak zavisi od prošlosti u komplikovanom načinu. Svi su složeniji za analitičko rešavanje od uobičajenog slučajnog koraka; dalje, ponašanje bilo kog modela slučajne šetnje je dobiti pomoću računara. Primeri uključuju:

• Polu-izbegavajuća šetnja (Madras i Slade 1996)).

Polu-izbegavajuća šetnja dužine n o z ^ d je slučajna p N-korak koji počinje u poreklu, čini prelaze samo između susednih lokacija u z ^ d, nikada ne posećuje sajt, i ravnomerno je izabran među svim tim putevima. U dve dimenzije, do usled samo-hvatanje, tipična samo-izbegavajuća šetnja je vrlo kratka, dok u višu dimenziju raste iznad svih granica. Ovaj model se često koristi u fizici polimera (od 1960)

• Izbrisana petlja slučajne šetnje (Gregory Lawler).
• Ojačana slučajna šetnja (Robin Pemantle 2007).
• Proces istraživanja.
• Multiagent slučajne šetnje.

Duge koleracijske šetnje

Duge korelacijske vremenske serije se mogu naći u mnogim biološkim, klimatskih i ekonomskih sistemima..

• Heartbeat records
• Non-coding DNA sequences
• Volatility time series of stocks
• Temperature records around the globe

Vidi još

• Braunovo kretanje

Literatura

• Stein, Rolf Alfred (1972). Tibetan Civilization. Stanford University Press. ISBN 978-0-8047-0901-9. 
• Aldous, David; Fill, Jim, Reversible Markov Chains and Random Walks on Graphs, https://web.archive.org/web/20040921020230/http://stat-www.berkeley.edu/users/aldous/RWG/book.html
• Ben-Avraham D.; Havlin S., Diffusion and Reactions in Fractals and Disordered Systems Arhivirano na sajtu Wayback Machine (4. oktobar 2011), Cambridge University Press, 2000.
• Doyle, Peter G.; Snell, J. Laurie (1984). Random Walks and Electric Networks. Carus Mathematical Monographs 22. Mathematical Association of America. arXiv:math.PR/0001057. ISBN 978-0-88385-024-4.  MR 920811
• Feller, William (1968). An Introduction to Probability Theory and its Applications. I. ISBN 978-0-471-25708-0. 
• Hughes, Barry D. (1996). Random Walks and Random Environments. Oxford University Press. ISBN 978-0-19-853789-2. 
• Mackenzie, Dana, "Taking the Measure of the Wildest Dance on Earth", Science, Vol. 290, 8 December 2000.
• Norris, James (1998). Markov Chains. Cambridge University Press. ISBN 978-0-521-63396-3. 
• Pólya G.(1921), "Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Strassennetz", Mathematische Annalen, 84(1-2):149–160, March 1921.
• Révész, Pal (2013). Random Walk in Random and Non-random Environments (3rd izd.). World Scientific Pub Co. ISBN 978-981-4447-50-8. 
• Weiss G. Aspects and Applications of the Random Walk, North-Holland, 1994.
• Toshikazu Sunada (2012), Topological Crystallography --With a View Towards Discrete Geometric Analysis--, Surveys and Tutorials in the Applied Mathematical Sciences, Vol. 6, Springer

Spoljašnje veze

• Pólya's Random Walk Constants
• Random walk in Java Applet
• Quantum random walk