Procesul Markov

În matematică , un proces Markov este un proces stochastic cu proprietatea Markov . Într-un astfel de proces, predicția viitorului din prezent nu este făcută mai precisă de informațiile despre trecut. Procesele Markov poartă numele inventatorului lor, Andrei Markov .

Un proces Markov în timp discret este o secvență de variabile aleatorii . Setul valorilor lor posibile se numește spațiu de stare , valoarea fiind starea procesului în momentul respectiv Conform autorilor, termenul „ lanț Markov ” desemnează procesele Markov în timp discret sau numai procesele Markov în timp discret Procesul Markov în timp discret și spațiu de stare discret, adică procese Markov în timp discret al căror spațiu de stare este finit sau numărabil . $\ scriptstyle \ X_ {1},$ $\ scriptstyle \ X_ {2},$ $\ scriptstyle \ X_ {3}, \ \ dots$ $\ scriptstyle \ X_ {n} \$ $\ scriptstyle \ n.$

Dacă legea condițională a cunoașterii timpului trecut, adică cunoașterea este o funcție a singurului, atunci: $\ scriptstyle \ X _ {{n + 1}} \$ $\ scriptstyle \ \ left (X_ {k} \ right) _ {{0 \ leq k \ leq n}} \$ $\ scriptstyle \ X_ {n} \$

P (X _ {{n + 1}} = x \ mid X_ {0}, X_ {1}, X_ {2}, \ ldots, X_ {n}) = P (X _ {{n + 1}} = x \ mid X_ {n}). \,

unde este orice stare a procesului. Identitatea de mai sus identifică probabilitatea markoviană . $X$

Andrei Markov a publicat primele rezultate ale acestor procese în 1906 .

O generalizare a unui spațiu infinit numărabil de stat a fost dat de Kolmogorov în 1936 .

Procesele Markov sunt legate de mișcarea browniană și ipoteza ergodică , două teme ale fizicii statistice care au fost foarte importante la începutul XX - lea secol.

Tipuri de procese Markov

Spațiu discret de stare

Când variabilele aleatorii succesive sunt variabile discrete echipate cu o funcție de probabilitate, vorbim despre un lanț Markov .

Deși lanțurile Markov se aplică fenomenelor al căror aspect temporal nu are în general niciun interes, se pot asocia valorile succesive cu instantele . Proprietatea markoviană conform căreia probabilitatea unei stări a sistemului depinde doar de starea sa anterioară printr-o probabilitate condițională numită probabilitate de tranziție este exprimată prin: $x_i \,$ $t_ {i} \,$

P (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}; x _ {{n-2}}, t _ {{n-2} }; ...; x_ {1}, t_ {1}; x_ {0}, t_ {0}) = P (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}) \ quad t_ {n}> t _ {{n-1}}> ...> t_ {1}> t_ {0} \,

Un lanț Markov este definit în întregime de probabilitatea de ordinul întâi și probabilitatea de tranziție. De exemplu, obținem probabilitatea de ordinul doi prin: $P (x, t) \,$

P (x_ {1}, t_ {1}; x_ {2}, t_ {2}) = P (x_ {1}, t_ {1}) P (x_ {2}, t_ {2} | x_ {1 }, t_ {1}) \ quad t_ {2}> t_ {1} \,

Prin urmare, este definit și de probabilitatea de ordinul doi. În cele din urmă, poate fi definit de starea inițială și probabilitatea de tranziție.

Spațiu continuu de stare

Lanțurile Markov găsesc aplicații în cele mai diverse domenii, dar procesele luate în considerare în probleme dinamice, în special în vibrații, se referă în general la variabile aleatoare continue.

În aceste condiții, probabilitatea de a obține o valoare dată este în general zero și probabilitățile de apariție trebuie înlocuite cu densități de probabilitate în formula proprietății markoviene:

p (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}; x _ {{n-2}}, t _ {{n-2} }; ...; x_ {1}, t_ {1}; x_ {0}, t_ {0}) = p (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}) \ quad t_ {n}> t _ {{n-1}}> ...> t_ {1}> t_ {0} \,

Timp discret și timp continuu

Considerațiile de mai sus rămân valabile dacă intervalele de timp devin infinit de mici. Această remarcă este deosebit de interesantă în cazul unei ecuații diferențiale . Dacă este de ordinul întâi, setarea diferenței finite relevă un mecanism markovian. Pentru ordinele superioare și sistemele diferențiale, descompunerea în ecuații de ordinul întâi duce la un sistem markovian cu mai multe dimensiuni.

Proprietățile proceselor Markov în timp discret

Un proces Markov se caracterizează prin distribuția condiționată:

P (X _ {{n + 1}} \ mid X_ {n}) \,

care se mai numește și probabilitatea de tranziție a unei etape de proces. Probabilitatea de tranziție pentru doi , trei sau mai mulți pași este dedusă din probabilitatea de tranziție a unui pas și din proprietatea Markov:

P (X _ {{n + 2}} \ mid X_ {n}) = \ int P (X _ {{n + 2}}, X _ {{n + 1}} \ mid X_ {n}) \ , {\ mathrm d} X _ {{n + 1}} = \ int P (X _ {{n + 2}} \ mid X _ {{n + 1}}) \, P (X _ {{n + 1}} \ mid X_ {n}) \, {\ mathrm d} X _ {{n + 1}}

De asemenea,

P (X _ {{n + 3}} \ mid X_ {n}) = \ int P (X _ {{n + 3}} \ mid X _ {{n + 2}}) \ int P (X _ {{n + 2}} \ mid X _ {{n + 1}}) \, P (X _ {{n + 1}} \ mid X_ {n}) \, {\ mathrm d} X _ {{ n + 1}} \, {\ mathrm d} X _ {{n + 2}}

Aceste formule sunt generalizate într-un viitor arbitrar îndepărtat prin multiplicarea probabilităților de tranziție și integrarea timpilor. $n + k$ $k-1$

Legea distribuției marginale este legea distribuției statelor în timp . Distribuția inițială este . Evoluția procesului după un pas este descrisă de: $P (X_ {n})$ $nu$ $P (X_ {0})$

P (X _ {{n + 1}}) = \ int P (X _ {{n + 1}} \ mid X_ {n}) \, P (X_ {n}) \, {\ mathrm d} X_ {n}

Aceasta este o versiune a ecuației Frobenius-Perron . Pot exista una sau mai multe distribuții de stat, cum ar fi: $\ pi$

\ pi (X) = \ int P (X \ mid Y) \, \ pi (Y) \, {\ mathrm d} Y

unde este un nume arbitrar pentru variabila de integrare. O astfel de distribuție se numește distribuție staționară . O distribuție staționară este o funcție proprie a legii distribuției condiționate, asociată cu valoarea proprie 1. $Da$ $\ pi$

În cazul lanțurilor Markov de spațiu discret, anumite proprietăți ale procesului determină dacă există sau nu o distribuție staționară și dacă este unică sau nu.

un lanț Markov este ireductibil dacă orice stat este accesibil din orice alt stat.
o stare este recurentă pozitivă dacă așteptarea timpului primei reveniri la această stare, pornind de la această stare, este finită.

Când spațiul de stare al unui lanț Markov nu este ireductibil, acesta poate fi partiționat într-un set de clase comunicante ireductibile. Problema clasificării este importantă în studiul matematic al lanțurilor Markov și al proceselor stochastice .

Dacă un lanț Markov are cel puțin o stare recurentă pozitivă, atunci există o distribuție staționară.

Dacă un lanț Markov este recurent pozitiv și ireductibil, atunci:

există o singură distribuție staționară;
iar procesul construit luând distribuția staționară ca distribuție inițială este ergodic .

Deci, media unei funcții peste instanțele lanțului Markov este egală cu media sa în funcție de distribuția sa staționară: $f$

\ lim _ {{n \ rightarrow \ infty}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k} ) = \ int f (X) \, \ pi (X) \, {\ mathrm d} X

Acest lucru este valabil mai ales atunci când funcția de identitate este. $f$

Media valorii instanțelor este, prin urmare, pe termen lung, egală cu așteptările distribuției staționare.

Mai mult, această echivalență asupra mijloacelor se aplică și dacă este funcția indicator a unui subset al spațiului de stare: $f$ $LA$

\ lim _ {{n \ rightarrow \ infty}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k}) = \ int _ {A} \ pi (X) \, {\ mathrm d} X = \ mu _ {{\ pi}} (A)

unde este măsura indusă de . $\ mu _ {{\ pi}}$ $\ pi$

Acest lucru permite distribuția staționară să fie aproximată printr-o histogramă a unei anumite secvențe.

Dacă spațiul de stare este finit , atunci distribuția probabilității poate fi reprezentată printr-o matrice stocastică numită matrice de tranziție , al cărei al treilea element este: $(i, j)$

P (X _ {{n + 1}} = j \ mid X_ {n} = i) \,

Aplicații

Sistemele markoviene sunt foarte prezente în fizică, în special în fizica statistică . Acestea intervin în special prin ecuația Fokker-Planck . Mai general, ipoteza markoviană este adesea invocată atunci când probabilitățile sunt folosite pentru a modela starea unui sistem, presupunând totuși că starea viitoare a sistemului poate fi dedusă din trecut cu o istorie destul de scăzută.
Celebrul articol din 1948 al lui Claude Shannon , O teorie matematică a comunicării , care fundamentează teoria informației , începe prin introducerea conceptului de entropie dintr-o modelare Markov a limbii engleze . Arată astfel gradul de predictibilitate al limbii engleze, prevăzut cu un model simplu de ordine 1. Deși simple, astfel de modele permit să se reprezinte bine proprietățile statistice ale sistemelor și să se facă predicții eficiente fără a descrie complet structura. .
În compresie , modelarea Markoviană permite realizarea unor tehnici de codificare a entropiei foarte eficiente, cum ar fi codarea aritmetică . Mulți algoritmi de recunoaștere a modelelor sau inteligență artificială, cum ar fi algoritmul Viterbi , utilizat în marea majoritate a sistemelor de telefonie mobilă pentru corectarea erorilor, presupun un proces Markovian de bază.
Indicele de popularitate al unei pagini web ( PageRank ) așa cum este utilizat de Google este definit de un lanț Markov. Este definit de probabilitatea de a fi în această pagină din orice stare a lanțului Markov care reprezintă Web-ul. Dacă este numărul de pagini web cunoscute și o pagină are legături, atunci probabilitatea sa de a trece la o pagină legată (spre care indică) este și pentru toate celelalte (pagini fără legătură). Rețineți că avem . Parametrul este de aproximativ 0,15. $NU$ $eu$ $k_ {i}$ $p_ {i} ^ {l} = {\ tfrac {1-q} {k_ {i}}} + {\ tfrac qN}$ $p_ {i} ^ {{nl}} = {\ tfrac qN}$ $k_ {i} p_ {i} ^ {l} + (N-k_ {i}) p_ {i} ^ {{nl}} = 1$ $q$
Lanțurile Markov sunt un instrument fundamental pentru modelarea proceselor în teoria cozii și statistici .
Lanturi Markov sunt frecvent utilizate în fiabilitate pentru calculele de fiabilitate și disponibilitate a sistemelor tehnice , în special pentru modelarea tip de defect de secvențe de evenimente, reparații, modificări de configurație.
Lanțurile Markov sunt folosite și în bioinformatică pentru a modela relațiile dintre simbolurile succesive ale aceleiași secvențe (de exemplu, a nucleotidelor ), depășind modelul polinomial. Modelele ascunse Markov au, de asemenea, diverse utilizări, cum ar fi segmentarea (definirea limitelor regionale în cadrul secvențelor de gene sau proteine cu proprietăți chimice diferite), alinierea multiplă , predicția funcției sau descoperirea genelor (modelele ascunse Markov sunt mai „flexibile” decât definiții stricte ale codonului de tip start + codoni multipli + codoni stop și sunt, prin urmare, mai potrivite pentru eucariote (datorită prezenței intronilor în genomul acestora) sau pentru descoperirea pseudo-genelor).

Vezi și tu

Articole similare

Bibliografie

Étienne Pardoux: Procese și aplicații Markov - Algoritmi, rețele, genom și finanțe . Dunod, 2007
Pierre Désesquelles: Procese Markov în biologie, sociologie, geologie, chimie, fizică și aplicații industriale . Elipsele, 2016.

linkuri externe

(ro) [PDF] Charles M. Grinstead și J. Laurie Snell, cap. „ Lanțurile Markov ”, în Introducere în probabilitate , AMS
(ro) Markov Chain Minunat
Exerciții corectate ( sfaturi ale Universității din Nisa Sophia Antipolis )