Véletlenszerű séta

A matematikában , a közgazdaságtanban és az elméleti fizikában a véletlenszerű séta egy olyan rendszer matematikai modellje , amelynek diszkrét dinamikája véletlenszerű lépésekből áll , vagy "véletlenszerűen" készült. Szintén gyakran használják a random walk , random walk vagy random walk kifejezéseket angolul. Ezek a véletlenszerű lépések ráadásul teljesen dekorreláltak egymástól; ez utóbbi az alapvető tulajdonságot nevezzük a Markov-jellegű a folyamat, melynek névadója a matematikus Markov . Ez intuitív módon azt jelenti, hogy a rendszer jövője minden pillanatban a jelenlegi állapotától függ, de nem a múltjától, még a legközelebb sem. Más szavakkal, a rendszer "elveszíti az emlékezetét", ahogy az idővel fejlődik. Emiatt a véletlenszerű sétát néha „részeg sétának” is nevezik.

Ez a matematikai modellezés lehetővé teszi bizonyos természeti jelenségek számbavételét, amelyek leghíresebb példája a Brown-mozgás , amely megfelel például a pollenszem belső folyadékában jelenlévő részecskék látszólag véletlenszerű mozgásának.

Matematikában vagy informatikában gyakran véletlenszerű sétákat tanulmányozunk rendszeres hálózatokon vagy összetettebb grafikonokon . Például ezt a módszert használja a Google keresőmotorja az internetes hálózat oldalainak böngészésére, azonosítására és osztályozására .

Technikailag a véletlenszerű séta a valószínűségelmélet területe . A véletlenszerű séta valóban sztochasztikus folyamat a Markov-lánc típusú . Ez lebontva elemi egységek úgynevezett lépéseket , amelyek hossza önmagában is állandó, véletlenszerű vagy fix a hálózat vagy a grafikon, amelyen utazunk. Ezért minden lépésnél számos lehetőségünk van arra, hogy véletlenszerűen kiválasszuk a lépés irányát és méretét. Ez a lehetőségek tartománya lehet diszkrét (választás véges számú érték közül) vagy folyamatos .

Történelmi

A véletlenszerű séta ötletét (név nélkül) 1905-ben vezette be Karl Pearson biostatisztikus, hogy figyelembe vegye a szúnyogok populációjának vándorlását egy erdőben. Pearson a következő kérdést teszi fel:

„Egy ember az O pontról indul és 1 yardot (0,914  m ) halad egyenes vonalban; bármilyen szögből megfordul, és ismét egyenesen sétál az udvarokon. N -szer megismétli ezt a folyamatot . Annak a valószínűségét kérem, hogy ezen utak n után az r és r + dr közötti távolságra legyen a kiindulási ponttól. "

Erre a kérdésre egy héttel később Lord Rayleigh ad választ a Nature folyóirat következő számában  : amikor n elég nagy, akkor ez a valószínűség:

dP(r) ∼ 2neml2exp⁡(-r2neml2)rdr{\ displaystyle \ mathrm {d} P (r) \ \ sim \ {\ frac {2} {nl ^ {2}}} \, \ exp \ left (- {\ dfrac {r ^ {2}} {nl ^ {2}}} \ jobbra) \, r \, \ mathrm {d} r}

Ha Rayleigh ilyen gyorsan megadja a választ, az azért van, mert 1880-ban ő maga tanulmányozta egy kapcsolódó problémát: az azonos amplitúdójú, de véletlenszerű fázisú akusztikus hullámok egymásra helyezésének viselkedését. Pearson tovább találkozik Rayleigh-velAugusztus 10 :

- Tudnom kellett volna, de az utóbbi évek olvasmánya más érdeklődési területekre helyezkedett át, és nem számíthat arra, hogy az akusztikáról szóló disszertációban megtalálja az első lépést egy biometrikus probléma kapcsán. "

Pearson ezután folytatja:

- Lord Rayleigh megoldásának tanulsága az, hogy egy nyílt országban valahol a kiindulási pont közelében található a legvalószínűbb hely, ahol még mindig talpon tud állni egy részeg. "

A "véletlenszerű séta" kifejezést csak 1919-1921 körül vezette be George Pólya magyar matematikus , aki a német " Irrfahrt  " szót használta  .

Egydimenziós diszkrét véletlenszerű séta

Meghatározás

A legegyszerűbb véletlen bolyongás modell az egy- dimenziós diszkrét véletlen séta a periódusos rács ℤ. Konkrét példaként képzelhetünk el egy lépcsőn egy olyan személyt (vagy „részecskét”), aki egy érmét megfordít, hogy eldöntse, a következő lépés felfelé vagy lefelé halad-e. Minden lépésnél csak két lehetőség van: ebben a példában egy előre lépés vagy egy visszalépés. A probléma egyetlen szabad paramétere annak valószínűsége, hogy a részecske előreugrik (nem pedig visszaugrik).

Ha ezt a valószínűséget p valós számmal nevezzük meg, így: 0 < p <1 , akkor q = 1 - p azt a valószínűséget jelenti, hogy a részecske vissza fog ugrani .

A legegyszerűbb eset, amely megfelel például a Brown-mozgásnak, a térbeli izotropia hipotézisének felállítását jelenti . A fizikai tér "előre / hátra" irányai eleve egyenértékűek, beállítjuk az egyenértékűséget  :

o=q=12{\ displaystyle p = q = {\ frac {1} {2}}}

Figyelemre méltó, hogy az ebben az esetben kiemelt törvények sokkal összetettebb véletlenszerű járási problémákra is kiterjednek.

Izotróp véletlenszerű séta

A véletlenszerű lövések mindegyike a mozgás kiválasztásához Bernoulli-tesztet jelent , ugyanolyan valószínű eredménnyel  : itt az emelkedés vagy az ereszkedés valószínűsége 1/2.

A szemközti ábra egy részecske véletlenszerű sétáinak három független numerikus szimulációját mutatja: a részecske egymás utáni x ( t ) helyzetét t = 1, 2, ... időpontban ábrázoltuk , kezdve az x ( 0) = 0 .

Összesen n lépés után a „farok” rajzolásának száma követi a B binomiális eloszlást ( n , 1/2) , így a valószínűsége: NEMnem{\ displaystyle N_ {n}}

P(NEMnem=k) = 12nem (nemk){\ displaystyle P (N_ {n} = k) \ = \ {\ frac {1} {2 ^ {n}}} \ {n \ select k}}

ahol a száma kombinációk a k elemek vett n . (nemk){\ displaystyle {n \ select k}}

Meghatározhatjuk a n iteráció utáni helyzetet úgy, hogy a kezdethez 0 értéket veszünk, minden egyes előre lépéshez (farok) hozzáadunk 1-et, és minden egyes visszalépéshez (arc) kivonunk 1-et. Tehát a helyzet adja meg: . A klasszikus binomiális törvényhez képest ezért elegendő az eredményeket n ⁄ 2-vel eltolni és 2- gyel megszorozni, így: xnem{\ displaystyle X_ {n}}xnem{\ displaystyle X_ {n}}xnem=NEMnem-(nem-NEMnem)=2NEMnem-nem{\ displaystyle X_ {n} = N_ {n} - (n-N_ {n}) = 2N_ {n} -n}

• P(xnem=k)=12nem(nemnem+k2){\ displaystyle P (X_ {n} = k) = {1 \ felett {2 ^ {n}}} {\ binom {n} {\ frac {n + k} {2}}}}ha n és k azonos paritással bír, akkor = 0 különben;
• a remény semmis;
• a szórás n és a szórás √ n  ;
• még mindig fennáll Bienaymé-Tchebychev egyenlőtlenség  ;
• és a nagy számok törvénye .

Konkrétan, ha megismételjük a tapasztalatokat nagy számú résztvevővel, és ha hagyjuk, hogy kellően sok lépésben fejlődjenek ( például n = 100 nagyságrendűek ), akkor azt várjuk, hogy a végső pozíciók felhője nagyjából a kezdeti séta. Ez kvantitatívvá tehető: az aszimptotikus n >> 1 rezsimbe helyezéssel Stirling képletével bemutatjuk, hogy a binomiális törvény aszimptotikusan viselkedik, mint egy Gauss-eloszlás . Különösen nagyságrendet kapunk a résztvevők felhőjének elterjedéséről: például azt várjuk, hogy a résztvevők körülbelül 95% -a 20 lépésnél vagy kevesebbnél maradt a kezdeti pozíciótól (20 = 2 √ 100 ).

Az alábbi galéria az izotróp véletlenszerű séták négy mintáját tartalmazza a ℤ rácson, az eredettől 1000 lépés után. A pontozott vonalak jelzik az elért pozíció maximális és minimális értékét (1000 lépés után).

Visszatérés a származási problémához

A fenti képlet szerint annak a valószínűsége, hogy 2 n lépés után visszatérünk az origóhoz (páratlan számú lépés után természetesen nulla). onem=P(x2nem=0)=122nem(2nemnem){\ displaystyle p_ {n} = P (X_ {2n} = 0) = {1 \ felett {2 ^ {2n}}} {\ binom {2n} {n}}}

A Stirling-képlettel kapott egyenérték azt mutatja, hogy ez a valószínűség lassan a 0 felé hajlik, ami intuitívan azt jelenti, hogy minél hosszabb az idő, annál kevésbé valószínű, hogy a kiindulási ponton vagyunk. Látni fogjuk azonban, hogy minden séta legalább egyszer visszatér az eredethez, miközben tudjuk, hogy az első visszatérés időpontjának átlaga végtelen. onem∼1πnem{\ displaystyle p_ {n} \ sim {1 \ over {\ sqrt {\ pi n}}}}

Az eredetre való átjutás valószínűsége

Megkérdezzük magunktól, hogy mekkora annak a valószínűsége , hogy legalább 2n hosszú út során legalább egyszer visszatértünk az origóhoz  ; figyelemre méltó, hogy az ellenkező eseménynek is van valószínűsége, és ezért az 1 felé tart, amikor n a végtelen felé hajlik: az izotróp véletlenszerű séta a vonalon szinte biztosan legalább egyszer visszatér a kiindulópontjához (ezért valójában y végtelen számú alkalommal), és ez még minden olyan pontra vonatkozik, amelyen keresztülhalad. Később látni fogjuk, hogy ez továbbra is igaz marad a 2. dimenzióban, de hamisabbá válik a magasabb dimenzióban. qnem{\ displaystyle q_ {n}}{xk≠0,1⩽k⩽2nem}{\ displaystyle \ {X_ {k} \ neq 0.1 \ leqslant k \ leqslant 2n \}}onem=122nem(2nemnem){\ displaystyle p_ {n} = {1 \ felett {2 ^ {2n}}} {\ binom {2n} {n}}}qnem=1-onem{\ displaystyle q_ {n} = 1-p_ {n}}

Az előző képlet bemutatása:

A szimmetria érdekében a véletlen hosszúságú lépések száma, amelyek nem haladnak át , megduplázzák a megmaradók számát . 2nem{\ displaystyle 2n}0{\ displaystyle 0}>0{\ displaystyle> 0}

A probléma az, hogy számít a lépéseket haladva a az agyvérzés és a lét, kivéve , szigorúan a jogot . 0{\ displaystyle 0}2k{\ displaystyle 2k}2nem{\ displaystyle 2n}0{\ displaystyle 0}0{\ displaystyle 0}

Az első szakasz egy ilyen lépés feltétlenül fog a csak számolja meg a pályák, amik a az lövések megkerülve . 0{\ displaystyle 0}1{\ displaystyle 1}1{\ displaystyle 1} 2k{\ displaystyle \ 2k}2nem-1{\ displaystyle 2n-1}0{\ displaystyle 0}

Általában útvonalak számának hogy menjen be a ütések (az út teljesen határozza meg a mozgást a jobb (vagy mozgás balra)) közül lehet választani a teljes elmozdulások. Tehát már a lépcsőfokok számát, amik a az is megérinál nél{\ displaystyle a}b{\ displaystyle b}m{\ displaystyle m}(mm+b-nál nél2)={\ displaystyle \ left ({\ begin {tömb} {c} m \\ {\ frac {m + ba} {2}} \ vég {tömb}} \ jobb) =} (mm-b+nál nél2){\ displaystyle \ left ({\ begin {tömb} {c} m \\ {\ frac {m-b + a} {2}} \ vég {tömb}} \ jobb)}m+b-nál nél2{\ displaystyle {\ frac {m + ba} {2}}}m-b+nál nél2{\ displaystyle {\ frac {m-b + a} {2}}}m{\ displaystyle m}1{\ displaystyle 1}2k{\ displaystyle 2k}(2nem-1nem+k-1).{\ displaystyle \ left ({\ begin {tömb} {c} 2n-1 \\ n + k-1 \ vége {tömb}} \ jobb).}

A trükkös rész az, hogy meghatározza a lépések számát a a felvételek átmenni 0. Ezt az elvet a reflexió (lásd a cikket a választási kérdés ). 1{\ displaystyle 1}2k{\ displaystyle 2k}2nem-1{\ displaystyle 2n-1}

Egy ilyen lépés, akkor bijectively cserélje ki a részét a start és az első visszatérés által szimmetrikus : ez a szám tehát ugyanaz, mint a lépések haladva a az mozog, azaz0{\ displaystyle 0}0{\ displaystyle 0}0{\ displaystyle 0}-1{\ displaystyle -1}2k{\ displaystyle 2k}2nem-1{\ displaystyle 2n-1}(2nem-1nem+k).{\ displaystyle \ left ({\ begin {tömb} {c} 2n-1 \\ n + k \ vége {tömb}} \ jobb).}

A lépések száma haladva a hosszú , anélkül, hogy a tengely ezért érdemes . Ne feledje, hogy ez az eredmény megegyezik a szavazási tételével . 0{\ displaystyle 0}2k{\ displaystyle 2k}2nem{\ displaystyle 2n}(2nem-1nem+k-1)-(2nem-1nem+k){\ displaystyle \ left ({\ begin {tömb} {c} 2n-1 \\ n + k-1 \ end {tömb}} \ jobb) - \ bal ({\ begin {tömb} {c} 2n-1 \\ n + k \ end {tömb}} \ jobb)}

Mi levezetni száma elkerülve lépéseket  :  ; teleszkópos összegadás , amit be kellett mutatni. 0{\ displaystyle 0}22nem(1-qnem)=2∑nemk=1((2nem-1nem+k-1)-(2nem-1nem+k)){\ displaystyle 2 ^ {2n} (1-q_ {n}) = 2 {\ alulhalmaz {k = 1} {\ overset {n} {\ sum}}} \ bal (\ bal ({\ begin {tömb} {c} 2n-1 \\ n + k-1 \ end {tömb}} \ jobbra) - \ balra ({\ begin {tömb} {c} 2n-1 \\ n + k \ vége {tömb}} \ jó jó)}22nem(1-qnem)=2(2nem-1nem)=(2nemnem){\ displaystyle 2 ^ {2n} (1-q_ {n}) = 2 \ bal ({\ begin {tömb} {c} 2n-1 \\ n \ end {tömb}} \ jobb) = \ bal ({ \ begin {tömb} {c} 2n \\ n \ vége {tömb}} \ jobbra}}

Ugyanennek az eredménynek egy másik értelmezése: A bináris szavak száma, amelyeknek az összes balra (ill. Jobbra) kezdődő részszava szigorúan több mint 1, mint 0 (ill. Fordítva), érdemes (nem összekeverni Dyck szavaival ). 2nem{\ displaystyle 2n}(2nemnem){\ displaystyle \ left ({\ begin {tömb} {c} 2n \\ n \ vége {tömb}} \ jobb)}

Hasonló számítás azt mutatja, hogy páratlan esetben az eredethez való visszatérés valószínűsége is hosszú séta során érvényes (lásd az OEIS A063886 és az OEIS A307768 sorrendjét ). 2nem+1{\ displaystyle 2n + 1}1-onem{\ displaystyle 1-p_ {n}}

Az első visszatérés ideje a származáshoz

A fenti eredmények alapján a valószínűsége lehet beszerezni a séta vissza eredetét először  : . Arra a következtetésre jutunk, hogy az első visszatérés időpontjának várakozása végtelen azóta . r2nem{\ displaystyle r_ {2n}}2nem{\ displaystyle 2n}r2nem=onem2nem-1{\ displaystyle r_ {2n} = {p_ {n} \ felett {2n-1}}}∑∞nem=12nemr2nem{\ displaystyle {\ underset {n = 1} {\ overset {\ infty} {\ sum}}}} {2nr_ {2n}}2nemr2nem∼1πnem{\ displaystyle 2nr_ {2n} \ sim {1 \ over {\ sqrt {\ pi n}}}}

Az előző képlet bemutatása:

Egy lépés, amely visszatér az eredetre abban az időben, szükségszerűen 1-gyel vagy -1-gyel halad az előző időpontban, és mindig szimmetria alapján annyi lépés érkezik 1-re, mint -1-re; az eredethez először egyszer visszatérő lépések száma ezért kétszer annyi, mint az 1-re végződő és> 0-nál hátralévő hosszúságú lépések száma ; átdolgozhatjuk az előző típusú érvelést, vagy közvetlenül alkalmazhatjuk a szavazólap képletét azzal , honnan , mit akartunk. 2nem{\ displaystyle 2n}2nem{\ displaystyle 2n}2nem-1{\ displaystyle 2n-1} 22nemr2nem=2o-qo+q(o+qo){\ displaystyle 2 ^ {2n} r_ {2n} = 2 {{pq} \ felett {p + q}} \ balra ({\ begin {tömb} {c} p + q \\ p \ vég {tömb}} \ jobb)}o+q=2nem-1,o-q=1{\ displaystyle p + q = 2n-1, pq = 1}22nemr2nem=212nem-1(2nem-1nem)=12nem-1(2nemnem){\ displaystyle 2 ^ {2n} r_ {2n} = 2 {{1} \ felett {2n-1}} \ balra ({\ begin {tömb} {c} 2n-1 \\ n \ vége {tömb}} \ right) = {{1} \ felett {2n-1}} \ balra ({\ begin {tömb} {c} 2n \\ n \ vége {tömb}} \ jobbra)}

Vegye figyelembe, hogy ez duplája a katalán rendelések számának . 12nem-1(2nemnem)=2nem(2(nem-1)nem-1){\ displaystyle {{1} \ felett {2n-1}} \ balra ({\ begin {tömb} {c} 2n \\ n \ vége {tömb}} \ jobbra) = {{2} \ át {n} } \ balra ({\ begin {tömb} {c} 2 (n-1) \\ n-1 \ vége {tömb}} \ jobbra)}nem-1{\ displaystyle n-1}

Izotróp véletlenszerű séta x- dimenziós rácson

Két dimenzió

Véletlenszerű sétát tekintünk a repülőhálózatra ℤ 2 . Négy lehetséges mozgás van itt minden helyszínen: előre, hátra, jobbra, balra. A szemközti ábra egy részecske véletlenszerű sétáinak három egymástól független numerikus szimulációját mutatja: ábrázoltuk a kapott három pályát.

Hosszú séták esetén a végső sétáló pozíció eloszlása aszimptotikusan viselkedik, mint egy Gauss-eloszlás . Ezt a konvergenciát az alábbiakban szemléltetjük: 10, majd 60 lépés után ábrázoljuk a jelenlét valószínűségének eloszlását a hálózaton:

Példányok

Az alábbi galéria négy izotróp véletlenszerű sétát tartalmaz a ℤ 2 rácson , 10 000 lépés után az origótól.

Három dimenzió

Véletlenszerű sétát fontolgatunk a köbös rácson ℤ 3 . Hat lehetséges mozdulat van itt minden helyszínen: előre, hátra, jobbra, balra, felfelé, lefelé.

A szemközti ábra egy részecske véletlenszerű sétáinak három független numerikus szimulációját mutatja: ábrázoltuk a kapott három pályát.

Példányok

Az alábbi galéria négy izotróp véletlenszerű sétát tartalmaz a ℤ 3 rácson , 10 000 lépés után az eredettől .

Kétdimenziós vetületek

Izotróp véletlenszerű séta x dimenziós kontinuumon

Két dimenzió

Figyelembe vesszük a véletlen járást a ℝ 2 síkon, amelyet a következő folyamat határoz meg:

• a részecske kezdetben az origóban van: x (0) = 0 , y (0) = 0, és másodpercenként egymást követő ugrásokkal mozog a síkon.

• minden ugrásnál a részecske egységnyi hosszúsággal halad előre abba az irányba, amelyet a tengelyhez ( Ox ) meghatározott α poláris szög jellemez . Például: –π ≤ α <+ π .

• Ez a poláros szög α egy véletlenszerű változó , azzal jellemezve, hogy egy valószínűségi sűrűség f ( α ) . A folyamat izotróp, ha az összes irány egyenértékű , ami megfelel az egységes sűrűség választásának  :

f(α) = 12π11[-π,π[(α){\ displaystyle f (\ alpha) \ = \ {\ frac {1} {2 \ pi}} 1 \! \! 1 _ {[- \ pi, \ pi [} (\ alfa)}

Minden ugrási irány teljesen független az előző ugrás irányától.

A szemközti ábra egy részecske véletlenszerű sétáinak három független numerikus szimulációját mutatja: ábrázoltuk a kapott három pályát.

Példányok

Az alábbi galéria négy izotróp véletlen lépés mintát tartalmaz a random 2 síkon az eredettől számított 10 000 lépés után.

A tér megismétlődése és dimenziója

Ismétlődés

Tekintsünk egy izotróp véletlen bolyongás rácson ℤ d a d térbeli dimenzióban. Mindig választhatjuk, hogy ennek a sétának a kiindulópontját vesszük, mint a derékszögű koordinátarendszer O kezdőpontját . A megismétlődés kérdése ekkor abból áll, hogy megkérdezzük-e legalább egy véges pozitív t pillanatot , amelyre a részecske ismét áthalad az O origón .

A véletlenszerű járás akkor és csak akkor ismétlődőnek mondható, ha annak a valószínűsége, hogy a részecske egy bizonyos véges későbbi t pillanatban visszatér az O kezdőpontra , egyenlő eggyel.

Pólya tétele (1921)

Ez a megismétlődési tulajdonság erősen függ a tér dimenziójától; bizonyítani tudjuk, hogy (Pólya - 1921):

• A d = 1, és d = 2, az izotróp véletlen séta visszatérő.
• a d = 3 és azon túl, az izotróp véletlenszerű séta nem ismétlődő; akkor azt mondjuk, hogy átmeneti (a jó „Franglais” kifejezésnél egyes szerzők néha az angol tranziens szót használják ).

Vannak, akik néha viccelődnek, hogy ez a tétel a közmondás alapja: "Minden út Rómába vezet" . Az olvasó megjegyzi, hogy ha valaki "kozmikus" utakat tartalmaz, akkor a közmondás téves.

Az eredethez való visszatérés valószínűsége háromnál nagyobb vagy egyenlő dimenzióban

Valójában tudjuk, hogyan kell kiszámítani annak valószínűségét, hogy a gyalogos, kezdetben az origóból kiindulva, visszatér az origóra, és ez az összes d > 2 dimenzió esetében . Ez a p ( d ) valószínűség a következő kifejezést ismeri el:

o(d) = 1 - 1u(d){\ displaystyle p (d) \ = \ 1 \ - \ {\ frac {1} {u (d)}}}

ahol u ( d ) egy d- dimenziós integrál :

u(d) = d(2π)d ∫-ππ...∫-ππdx1...dxdd - kötözősaláta⁡x1 - ... - kötözősaláta⁡xd{\ displaystyle u (d) \ = \ {\ frac {d} {(2 \ pi) ^ {d}}} \ \ int _ {- \ pi} ^ {\ pi} \ dots \ int _ {- \ pi} ^ {\ pi} {\ frac {\ mathrm {d} x_ {1} \ dots \ mathrm {d} x_ {d}} {d \ - \ \ cos x_ {1} \ - \ \ dots \ - \ \ cos x_ {d}}}}, amely az első típusú Bessel-függvény segítségével fejezhető ki  : u(d)=∫0∞(én0(t/d))de-tdt{\ displaystyle u (d) = \ int _ {0} ^ {\ infty} (I_ {0} (t / d)) ^ {d} e ^ {- t} dt}.

A szám az eredethez való visszatérések átlagos számát jelenti a végtelenbe lépés előtt (lásd a geometriai törvényt ). u(d)=11-o(d){\ displaystyle u (d) = {\ frac {1} {1-p (d)}}}

A d = 3 speciális esetet korábban már megszerezte Watson, Mc Crea és Whipple, valamint Domb. Az integrál analitikai kifejezését csak 1977-ben érte el Glasser és Zucker:

u(3) = 6.32π3Γ(124.)Γ(5.24.)Γ(724.)Γ(11.24.) {\ displaystyle u (3) \ = \ {\ frac {\ sqrt {6}} {32 \, \ pi ^ {3}}} \, \ Gamma \ left ({\ frac {1} {24}} \ jobbra) \, \ Gamma \ balra ({\ frac {5} {24}} \ jobbra) \, \ Gamma \ balra ({\ frac {7} {24}} \ jobbra) \, \ Gamma \ balra ({ \ frac {11} {24}} \ jobbra) \}

ahol Γ a gamma függvény . Az u ( d ) analitikai kifejezése nem ismert a d dimenzióban, amely nagyobb vagy egyenlő 4-vel.

A következő számértékeket kapjuk:

• u(3)≈1,516386059{\ displaystyle u (3) \ kb. 1,516386059}Követve A086231 A OEIS-ben , a következő A086230 az OEIS-ben  ;o(3)≈0,3405373296{\ displaystyle p (3) \ kb 0,3405373296}
• u(4)≈1,239467122{\ displaystyle u (4) \ kb 1,239467122}Követve A242812 A OEIS-ben , a következő A086232 az OEIS-ben  ;o(4)≈0,1932016732{\ displaystyle p (4) \ kb. 0,1932016732}
• u(5.)≈1,156308125{\ displaystyle u (5) \ kb 1,156308125}Követve A242813 A OEIS-ben , a következő A086233 az OEIS-ben  ;o(5.)≈0,1351786098{\ displaystyle p (5) \ kb 0.1351786098}
• u(6.)≈1,116963373{\ displaystyle u (6) \ kb. 1116963373}Követve A242814 A OEIS-ben , a következő A086234 az OEIS-ben  ;o(6.)≈0,1047154954{\ displaystyle p (6) \ kb 0,1047154954}
• u(7)≈1,093906316{\ displaystyle u (7) \ kb 1,093906316}Követve A242815 A OEIS-ben , a következő A086235 az OEIS-ben  ;o(7)≈0,0858449341{\ displaystyle p (7) \ kb. 0,0858449341}
• u(8.)≈1,078647012{\ displaystyle u (8) \ kb. 1,078647012}Követve A242816 A OEIS-ben , a következő A086236 az OEIS-ben .o(8.)≈0,0729126500{\ displaystyle p (8) \ kb. 0,0729126500}

Véletlenszerű séta egy csoporton

Az itt feltételezett csoportot multiplikatívnak tekintjük , anélkül, hogy ez elengedhetetlen lenne egy csoporton végzett véletlenszerű séta meghatározásához. Adunk magunknak egy sor független, véletlenszerű változót ugyanazzal a törvénnyel ( például itt nevezett törvényt ), véletlenszerű változókat, amelyeknek értéke van . Adunk magunknak egy véletlen változót, amelynek értékei bármilyen törvényt tartalmaznak, és ettől függetlenek . Ezután pózolunk, a(G,∘){\ displaystyle (G, \ circ)}Y=def(Ynem)nem∈NEM∗{\ displaystyle Y {\ stackrel {\ text {def}} {=}} (Y_ {n}) _ {n \ in \ mathbb {N} ^ {*}}}v{\ displaystyle \ nu}(G,∘){\ displaystyle (G, \ circ)}x0{\ displaystyle X_ {0}}(G,∘){\ displaystyle (G, \ circ)}Y=(Ynem)nem⩾0{\ displaystyle Y = (Y_ {n}) _ {n \ geqslant 0}}nem∈NEM∗{\ displaystyle n \ in \ mathbb {N} ^ {*}}

xnem=defxnem-1∘Ynem.{\ displaystyle X_ {n} {\ stackrel {\ text {def}} {=}} X_ {n-1} \ circ Y_ {n}.}

A szekvencia ezután egy Markov-lánc , és az úgynevezett egy véletlen séta a G , a lépések . Ez a minősítés vonatkozik az X-vel azonos eloszlású véletlenszerű szekvenciákra is . Alternatív megoldásként véletlenszerű sétaként elfogadjuk az ismétlődési reláció által meghatározott szekvenciát: x=def(xnem)nem∈NEM{\ displaystyle X {\ stackrel {\ text {def}} {=}} (X_ {n}) _ {n \ in \ mathbb {N}}} v{\ displaystyle \ nu}Z=def(Znem)nem∈NEM{\ displaystyle Z {\ stackrel {\ text {def}} {=}} (Z_ {n}) _ {n \ in \ mathbb {N}}}

xnem=defYnem∘xnem-1.{\ displaystyle X_ {n} {\ stackrel {\ text {def}} {=}} Y_ {n} \ circ X_ {n-1}.}

Megkülönböztetni a kétféle Markov-láncok így meghatározott, néha beszélünk jobb véletlen bolyongás és bal véletlen séta . Az általános kifejezés az átmenet mátrix e Markov-lánc van meghatározva, a , a og,h{\ displaystyle p_ {g, h}}(g,h)∈G2{\ displaystyle (g, h) \ itt: G ^ {2}}

og,h=defv(g-1∘h)vagyjóog,h=defv(h∘g-1),{\ displaystyle p_ {g, h} {\ stackrel {\ text {def}} {=}} \ nu (g ^ {- 1} \ circ h) \ quad {\ textrm {vagy}} \, \, { \ textrm {good}} \ quad p_ {g, h} {\ stackrel {\ text {def}} {=}} \ nu (h \ circ g ^ {- 1}),}

attól függően, hogy a véletlenszerű séta jobb vagy bal. Ezt könnyen ellenőrizhetjük

∑g∈Gog,h=∑g∈Gv(g-1∘h)=∑g∈Gv(g-1)=∑g∈Gv(g)=1,{\ displaystyle \ sum _ {g \ in G} p_ {g, h} = \ sum _ {g \ in G} \ nu (g ^ {- 1} \ circ h) = \ sum _ {g \ in G } \ nu (g ^ {- 1}) = \ sum _ {g \ a G} -ben \ nu (g) ​​= 1,}

mivel és van bijekciókat a G a G . Ily módon egy egységes mérési fölött egy helyhez kötött mérési . g↦g∘h{\ displaystyle g \ mapsto g \ circ h \,}g↦g-1{\ displaystyle g \ mapsto g ^ {- 1}}G{\ displaystyle G}

Példa:

a fent említett véletlenszerű séták véletlenszerű séták a ℤ d és ℝ 2 additív csoportokon .

Véletlenszerű séta egy grafikonon

Folyamatos véletlenszerű séta

A folyamatos idősorok modellezésében széles körben alkalmazott véletlenszerű séta írható:

xt=xt-1+εtfehér zajjal εt ∼NEM(0,1){\ displaystyle X_ {t} = X_ {t-1} + \ varepsilon _ {t} \ qquad {\ mbox {fehér zajjal}} \ \ varepsilon _ {t} \ \ sim {\ mathcal {N}} ( 0,1)}

Ez egy autoregresszív folyamat (azaz „önmagában visszafejlődött”) speciális esete, ahol ρ = 1 . A ρ paraméter értéke nagyon fontos, mert alapvetően megváltoztatja a sorozat tulajdonságát:

xt=ρxt-1+εt{\ displaystyle X_ {t} = \ rho X_ {t-1} + \ varepsilon _ {t}}{|ρ|<1A folyamat helyhez kötött|ρ|=1Véletlenszerű séta: a folyamat ezért nem stacioner|ρ|>1A folyamat robbanásszerű{\ displaystyle {\ begin {cases} | \ rho | <1 & {\ text {A folyamat stacionárius}} \\ | \ rho | = 1 & {\ text {Véletlen séta: a folyamat ezért nem stacionárius}} \\ | \ rho |> 1 & {\ text {A folyamat robbanásveszélyes}} \ end {esetben}}}

Rekurzív módon a véletlenszerű séta egyszerűen a fehér zaj összege. Írjuk:

xt=x0+∑én=1tεén{\ displaystyle X_ {t} = X_ {0} + \ sum _ {i = 1} ^ {t} \ varepsilon _ {i}}

Véletlenszerű séta Riemann-fajtán

Megjegyzések és hivatkozások

1. Karl Pearson, Nature , 1905. július 27., DOI : 10.1038 / 072294b0 .
2. Ezt a valószínűségi sűrűséget azóta Rayleigh törvényének hívják .
3. Karl Pearson, Természet , 1905. augusztus 10.
4. Ha van, akkor általában végtelen sok lesz belőlük. A véges idők közül a legkisebbet az első visszatérésnek nevezzük . Lásd pl. Stroock 2005 , kb. 1.
5. Lásd pl. Stroock 2005 , kb. 1.
6. (in) Yakov G. Sinai, Valószínűségszámítás - egy bevezető kurzus , Springer-Verlag, 1992 ( ISBN  3-540-53348-6 ) , p. 71.
7. (in) Jonathan Novak, "  Pólya-tétel véletlen séta  " , American Mathematical Monthly , vol.  121, N o  8,2014, P.  711-716.
8. (De) Georg Pólya, „Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz”, Mathematische Annalen , vol. 83, 1921), p.  149-160 .
9. (in) EW Montroll, "  Véletlenszerű séta többdimenziós terekben, különösen egy periodikus rács  " , Journal of the SIAM , vol.  4,1956, P.  241-260.
10. (in) GN Watson, "  Három hármas integrál  " , Quarterly Journal of Mathematics , vol.  2, n o  10,1939, P.  266-276.
11. (in) WH McCrea és FJW Whipple, "  Véletlen utak két és három dimenzióban  " , Proceedings of the Royal Society of Edinburgh , vol.  60,1940, P.  281-298.
12. (in) C. Domb, "a  többszörös visszatérés a véletlenszerű járás problémájában van  " , Proceedings of the Cambridge Philosophical Society , vol.  50,1954, P.  586-591.
13. (in) ML Glasser és IJ Zucker, "  Extended Watson integrálok a köbös rácsokhoz  " , PNAS , vol.  74,1977, P.  1800-1801.
14. (in) Eric W. Weisstein , "  Polya véletlenszerű járási konstansai  " a MathWorld- on .
15. (in) Steven R. Finch, Matematikai konstansok , Cambridge University Press ,2003, 602  p. ( ISBN  978-0-521-81805-6 , online olvasás ) , p.  322.

Lásd is

Bibliográfia

Szakkönyvek

• (en) Joseph Rudnick és George Gaspari, A véletlenszerű séta elemei: Bevezetés haladó hallgatóknak és kutatóknak , Cambridge University Press ,2004, 346  p. ( ISBN  0-521-82891-0 )
• en) Frank Spitzer, a Random Walk alapelvei , Princeton University Press ,1964( online olvasás )Újranyomta Springer (1970) ( ISBN  0-387-90139-6 )  ; 2 e kiadású gyűjtemény Diplomás szövegek a matematikából 34 (2001) ( ISBN  0-387-95154-7 )
• (en) Daniel W. Stroock , Bevezetés a Markov-folyamatokba , Springer, koll.  "Matematikai diplomás szövegek",2005, 178  p. ( ISBN  978-3-540-23451-7 , online olvasás )
• (en) William Feller , Bevezetés a valószínűségelméletbe és alkalmazásaiba, 1. kötet , John Wiley & Sons , gyűjt.  "Wiley sorozat a valószínűségben és a statisztikában",1968, 528  p. ( ISBN  978-0-471-25708-0 )

Klasszikus elemek

• (en) Mark Kac, Random Walk and Theory of Brownian Motion , American Mathematical Monthly 54 (7) (1947), 369-391. (en) Szöveg [PDF] formátumban Ez a cikk egyike a következőknek: Selected Papers on Noise & Stochastic Processes , Charles Proteus Steinmetz & Nelson Wax (szerk.), Dover Publishing, Inc. (1954). Újra megjelent a Phoenix gyűjteményben (2003), ASIN 0486495353.
• (en) Subramaniam Chandrashekhar, Stochastic Problems in Physics & Astronomy , Review of Modern Physics 15 (1943), 1–89. Ez a cikk egyike a hatnak: Selected Papers on Noise & Stochastic Processes , Charles Proteus Steinmetz & Nelson Wax (szerk.), Dover Publishing, Inc. (1954). Újra megjelent a Phoenix gyűjteményben (2003), ASIN 0486495353.

Virtuális könyvtár

• (en) Martin Z. Bazant, Random Walks and Diffusion  ; Alkalmazott matematika tanfolyam az MIT-n , fizikai és pénzügyi alkalmazásokkal.
  • (en) Előadási jegyzetek 2003 .
  • (en) Tanfolyamjegyzetek 2001 .

Véletlenszerű séta Riemann-fajtán

• (en) Mark A. Pinsky, Izotróp transzportfolyamat egy Riemann-féle elosztón , Transaction of the American Mathematical Society 218 (1976), 353-360.
• (en) Nicolas Th. Varopoulos, Brown-mozgás és véletlenszerű séták sokaságokon [PDF] , Annales de Institut Fourier 34 (2) (1984), 243-269.

Kapcsolódó cikkek

• Markov lánc
• Sztochasztikus folyamat
• Brown-mozgalom
• Az Ehrenfest Urns modellje
• Rayleigh törvénye
• Adaptív viselkedés
• Önkerülő út

Külső linkek

• Életnagyságú véletlenszerű gyaloglás, egy városban
• (en) Véletlenszerű séta fejezet az American Mathematical Society bevezető valószínűségi könyvében [PDF]