În matematică , economie și fizică teoretică , o plimbare aleatorie este un model matematic al unui sistem având o dinamică discretă compusă dintr-o succesiune de pași aleatori , sau făcute „la întâmplare”. De asemenea, se folosesc frecvent expresii random walk , random walk sau random walk în engleză. În plus, acești pași aleatorii sunt complet decorelați unul de celălalt; această ultimă proprietate fundamentală este numită caracterul Markovian al procesului, numit după matematicianul Markov . În mod intuitiv înseamnă că în fiecare moment, viitorul sistemului depinde de starea sa prezentă, dar nu de trecutul său, chiar și de cel mai apropiat. Cu alte cuvinte, sistemul „pierde memoria” pe măsură ce evoluează în timp. Din acest motiv, o plimbare aleatorie este uneori denumită și „plimbare beată”.
Această modelare matematică face posibilă explicarea anumitor fenomene naturale, cel mai faimos exemplu dintre acestea fiind mișcarea browniană , care corespunde, de exemplu, mișcărilor aparent aleatorii ale particulelor prezente în fluidul intern al unui bob de polen.
În matematică sau informatică, studiem adesea plimbări aleatorii pe rețele obișnuite sau pe grafice mai complexe. Aceasta este, de exemplu, metoda utilizată de motorul de căutare Google pentru a naviga, identifica și clasifica paginile rețelei de internet .
Din punct de vedere tehnic, mersul aleatoriu este domeniul teoriei probabilității . O plimbare aleatorie este într-adevăr un proces stocastic de tipul lanțului Markov . Este împărțit în unități elementare numite trepte , a căror lungime poate fi ea însăși constantă, aleatorie sau fixată de rețea sau de graficul pe care călătorim. Prin urmare, la fiecare pas, există o serie de posibilități de a selecta aleatoriu direcția și dimensiunea pasului. Această gamă de posibilități poate fi discretă (alegerea dintre un număr finit de valori) sau continuă .
Ideea mersului aleatoriu a fost introdusă (fără numele) în 1905 de biostatisticianul Karl Pearson pentru a explica migrațiile unei populații de țânțari într-o pădure. Pearson pune următoarea întrebare:
„Un bărbat începe de la punctul O și călătorește 1 yard (0,914 m ) în linie dreaptă; se întoarce de orice unghi și merge din nou pe curți drept. Repetă acest proces de n ori. Cer probabilitatea ca după n dintre aceste călătorii să se afle la o distanță între r și r + dr de punctul său de plecare. "
Răspunsul la această întrebare este oferit o săptămână mai târziu de Lord Rayleigh în următorul număr al revistei Nature : când n este suficient de mare, această probabilitate este:
.Dacă Rayleigh oferă răspunsul atât de repede, este pentru că el însuși a studiat o problemă înrudită în 1880: comportamentul unei suprapuneri de unde acustice cu aceeași amplitudine, dar cu faze aleatorii. Pearson îl întâlnește pe Rayleigh10 august :
„Ar fi trebuit să știu, dar lecturile mele din ultimii ani s-au mutat în alte domenii de interes și nu te-ai aștepta să găsești primul pas într-o problemă biometrică într-o disertație despre acustic. "
Pearson continuă apoi:
„Lecția soluției lordului Rayleigh este că într-o țară deschisă, cel mai probabil loc pentru a găsi un bețiv încă capabil să stea în picioare este undeva în vecinătatea punctului său de plecare. "
Termenul „mers aleatoriu” nu a fost introdus decât în jurul anilor 1919-1921 de matematicianul maghiar George Pólya , care a folosit cuvântul german „ Irrfahrt ”.
Cel mai simplu model de mers aleatoriu este mersul aleatoriu discret unidimensional pe rețeaua periodică ℤ. Pentru a forma un exemplu concret, ne putem imagina o persoană (sau „particulă”) pe o scară, care întoarce o monedă pentru a decide dacă următorul pas va fi în sus sau în jos. La fiecare pas, există doar două posibilități: în acest exemplu, un pas înainte sau un pas înapoi. Singurul parametru liber al problemei este probabilitatea ca particula să sară înainte (în loc să sară înapoi).
Dacă numim această probabilitate cu numărul real p astfel încât: 0 < p <1 , atunci q = 1 - p reprezintă probabilitatea ca particula să sară înapoi .
Cel mai simplu caz, care corespunde de exemplu mișcării browniene, constă în formularea ipotezei izotropiei spațiale . Direcțiile „înainte / înapoi” ale spațiului fizic fiind echivalente a priori , stabilim echipabilitatea :
Este remarcabil faptul că legile evidențiate în acest caz se extind la probleme mult mai complexe de mers aleatoriu.
Fiecare dintre fotografiile la întâmplare pentru a alege mișcarea constituie un test Bernoulli cu rezultate la fel de probabile : aici probabilitatea de ascensiune sau coborâre este 1/2.
Figura alăturată arată un eșantion de trei simulări numerice independente de mers aleatoriu pentru o particulă: am trasat pozițiile succesive x ( t ) ale particulei la momentele t = 1, 2, ..., începând de la condiția inițială x ( 0) = 0 .
După n pași în total, de câte ori am tras „cozi” urmează distribuția binomială B ( n , 1/2) , astfel încât probabilitatea este:
unde este numărul combinațiilor de k elemente luate din n .
Putem determina poziția după n iterații, luând valoarea 0 pentru început, adăugând 1 pentru fiecare pas înainte (cozi), scăzând 1 pentru fiecare pas înapoi (față). Deci , poziția este dată de: . În comparație cu legea binomială clasică, este, prin urmare, suficient să deplasați rezultatele cu n ⁄ 2 și să înmulțiți cu 2, astfel:
Concret, dacă repetăm experiența cu un număr mare de participanți și dacă le permitem să evolueze în timpul unui număr suficient de mare de pași (de ordinul n = 100, de exemplu), ne așteptăm ca norul pozițiilor finale să fie aproximativ centrat pe mersul inițial. Acest lucru se poate face cantitativ: plasându-ne în regimul asimptotic n >> 1 , demonstrăm folosind formula lui Stirling că legea binomială se comportă asimptotic ca o distribuție gaussiană . În special, se obține o ordine de mărime a răspândirii norului participanților: de exemplu, aproximativ 95% dintre participanți sunt așteptați să rămână la 20 de pași sau mai puțin față de poziția inițială (20 = 2 √ 100 ).
ExempleGaleria de mai jos conține patru exemplare de plimbări aleatorii izotrope pe rețeaua after după 1000 de pași de la origine. Liniile punctate indică respectiv valorile maxime și minime ale poziției atinse (după 1000 de pași).
Conform formulei de mai sus, probabilitatea de a reveni la origine după 2 n pași merită (este desigur zero după un număr impar de pași).
Echivalentul obținut prin formula Stirling arată că această probabilitate tinde încet spre 0 ceea ce înseamnă intuitiv că cu cât timpul este mai lung, cu atât suntem mai puțin probabil să fim la punctul de plecare. Cu toate acestea, vom vedea că orice plimbare revine cel puțin o dată la origine, știind totuși că media timpilor primei întoarceri la origine este infinită.
Probabilitatea de trecere la origineNe întrebăm care este probabilitatea de a ne fi întors cel puțin o dată la origine în timpul unei călătorii de lungime 2n ; este remarcabil faptul că evenimentul opus are, de asemenea, o probabilitate și, prin urmare, tinde spre 1 atunci când n tinde spre infinit: o mers aleator izotrop pe linie revine aproape sigur cel puțin o dată la punctul său de plecare (de aceea y repetă o infinitate de ori ), iar acest lucru se aplică chiar și oricărui punct prin care trece. Vom vedea mai târziu că acest lucru rămâne adevărat în dimensiunea 2, dar devine fals în dimensiunea superioară.
Demonstrarea formulei anterioare:
Din motive de simetrie, numărul de pași aleatori de lungime care nu trec este dublu față de numărul celor care rămân .
Problema noastră este să numărăm pașii care merg de la la în linii și să fim, în afară , strict la dreapta .
Primul segment al unei astfel de pas necesar merge la , doar contoriza numărul de trasee care merg pe la fotografii ocolesc .
În general, numărul de căi care merg pe la accidente vasculare cerebrale este (calea este determinată în întregime de către mișcarea spre dreapta (sau mișcarea spre stânga)) pentru a alege din totalul deplasărilor. Așadar, numărul total de pași care merg de la până merită
Partea mai dificila este de a determina numărul de pași în cu fotografii care trec prin 0. Acest lucru se face folosind principiul de reflecție ( a se vedea articolul pe problema alegerilor ).
Pentru un astfel de pas, putem înlocui bijectiv partea dintre start și prima revenire prin simetrică față de : acest număr este, prin urmare, același cu cel al pașilor care merg de la la în mișcări, adică
Prin urmare, merită numărul de pași care merg de la până la lungime fără a parcurge axa . Rețineți că acest rezultat este echivalent cu cel al teoremei scrutinului .
Deducem numărul de pași evitând : ; oferirea de sume telescopice , ceea ce trebuia demonstrat.
O altă interpretare a aceluiași rezultat: numărul de cuvinte binare de lungime ale căror toate cuvintele secundare începând din stânga (resp. În dreapta) prezintă strict mai mult de 1 decât de 0 (resp. Invers) merită (nu a confunda cu cuvintele lui Dyck ).
Un calcul similar arată că, în cazul ciudat, este valabilă și probabilitatea de a reveni la origine în timpul unei plimbări în lungime (a se vedea secvența A063886 a OEIS și secvența A307768 a OEIS ).
Ora primei reveniri la origineFolosind rezultatele de mai sus, probabilitatea poate fi obținută ca mersul pe jos înapoi la origine pentru prima dată : . Deducem că așteptarea timpului primei reveniri la origine este infinită, deoarece .
Demonstrarea formulei anterioare:
Un pas care revine la origine la momentul respectiv trece în mod necesar cu 1 sau cu -1 în momentul anterior și, întotdeauna prin simetrie, sunt la fel de mulți pași care ajung la 1 ca la -1; numărul de pași care revin la origine pentru prima dată la un moment dat merită, prin urmare, de două ori numărul de pași de lungime care se termină în 1 și rămân> 0; putem reface un raționament de tipul anterior sau putem aplica direct formula buletinului de vot cu , de unde , ceea ce ne-am dorit.
Rețineți că este dublul numărului de ordine catalane .
Considerăm o mers aleatoriu pe rețeaua plană ℤ 2 . Există patru mișcări posibile aici la fiecare site: înainte, înapoi, dreapta, stânga. Figura alăturată arată un eșantion de trei simulări numerice independente ale mersurilor aleatorii pentru o particulă: am trasat cele trei traiectorii obținute.
Pentru plimbări lungi, distribuția poziției finale a mersului se comportă asimptotic ca o distribuție gaussiană . Această convergență este ilustrată mai jos: trasăm distribuțiile probabilităților de prezență în rețea după 10 pași, apoi după 60 de pași:
ExemplareGaleria de mai jos conține patru exemplare de plimbări aleatorii izotrope pe rețeaua ℤ 2 după 10.000 de pași de la origine.
Considerăm o plimbare aleatorie pe rețeaua cubică ℤ 3 . Există șase mișcări posibile aici la fiecare site: înainte, înapoi, dreapta, stânga, sus, jos.
Figura alăturată arată un eșantion de trei simulări numerice independente ale mersurilor aleatorii pentru o particulă: am trasat cele trei traiectorii obținute.
ExemplareGaleria de mai jos conține patru exemplare de plimbări aleatorii izotrope pe rețeaua ℤ 3 după 10.000 de pași de la origine.
Considerăm mersul aleator pe planul defined 2 definit prin următorul proces:
Fiecare direcție a saltului este complet independentă de direcția saltului anterior.
Figura alăturată arată un eșantion de trei simulări numerice independente ale mersurilor aleatorii pentru o particulă: am trasat cele trei traiectorii obținute.
ExemplareGaleria de mai jos conține patru exemplare de pași izotropi aleatori pe planul ℝ 2 după 10.000 de pași de la origine.
Luați în considerare o plimbare aleatorie izotropă pe rețeaua ℤ d cu d dimensiuni spațiale. Putem alege întotdeauna să luăm punctul de plecare al acestei plimbări ca origine O a sistemului de coordonate carteziene. Problema de recurență constă apoi în întreabă dacă putem găsi cel puțin un finit pozitiv instantaneu t pentru care particula trece prin originea O din nou .
Se va spune că mersul aleatoriu este recurent dacă și numai dacă probabilitatea ca particula să revină la originea O pentru un anumit moment t finit ulterior este egală cu una.
Această proprietate a recurenței depinde puternic de dimensiunea spațiului; putem demonstra într-adevăr că (Pólya - 1921):
Unii oameni glumesc uneori că această teoremă stă la baza proverbului: „Toate drumurile duc la Roma” . Cititorul va observa că dacă cineva include căi „cosmice”, atunci proverbul este greșit.
Probabilitatea de a reveni la origine în dimensiune mai mare sau egală cu treiDe fapt, știm cum să calculăm probabilitatea ca mersul, pornind inițial de la origine, să revină la origine și aceasta pentru toate dimensiunile d > 2 . Această probabilitate p ( d ) admite următoarea expresie:
unde u ( d ) este o integrală dimensională d :
, care poate fi exprimat folosind funcția Bessel de primul fel : .Numărul reprezintă numărul mediu de reveniri la origine înainte de a merge la infinit (vezi legea geometrică ).
De fapt, cazul special d = 3 fusese deja obținut anterior de Watson, Mc Crea și Whipple și Domb. O expresie analitică a integralului a fost obținută abia în 1977 de Glasser și Zucker:
unde Γ este funcția gamma . Expresiile analitice ale lui u ( d ) nu sunt cunoscute în dimensiunea d mai mare sau egală cu 4.
Obținem următoarele valori numerice:
Considerăm că un grup presupus aici a fi multiplicativ, fără ca acest lucru să fie esențial pentru definirea unei plimbări aleatorii pe un grup. Ne oferim o serie de variabile aleatoare independente cu aceeași lege (legea numită aici de exemplu), variabile aleatoare toate cu valori în . De asemenea, ne oferim o variabilă aleatorie cu valori în , a oricărei legi și independentă de . Atunci pozăm, pentru
Secvența este atunci un lanț Markov și se numește mers aleator pe G , de trepte . Această calificare se aplică , de asemenea , la orice secvență aleatoare de aceeași distribuție ca și X . Alternativ, acceptăm ca mers aleatoriu o secvență definită de relația de recurență:
Pentru a distinge cele două tipuri de lanțuri Markov astfel definite, uneori vorbim de mers aleatoriu drept și mers aleatoriu stâng . Termenul general al matricei de tranziție a acestui lanț Markov este definit, pentru , de
în funcție de mersul aleatoriu este dreapta sau stânga. Putem verifica cu ușurință acest lucru
deoarece și sunt bijections de G în G . Astfel, o măsurătoare uniform peste o măsurătoare staționară .
Exemplu:plimbările aleatorii menționate mai sus sunt plimbări aleatorii pe grupele aditive ℤ d și ℝ 2 .
Utilizată pe scară largă în modelarea seriilor temporale continue, se poate scrie o plimbare aleatorie:
Acesta este un caz special al unui proces autoregresiv (adică „regresat pe sine”) cu ρ = 1 . Valoarea parametrului ρ este foarte importantă deoarece modifică fundamental proprietatea seriei:
Recursiv, o plimbare aleatorie este pur și simplu suma zgomotului alb. Îl scriem: