Zinxhirët e Markovit

Një diagram që përfaqëson një proces Markovi me dy gjendje. Numrat janë probabiliteti i kalimit nga një gjendje në një gjendje tjetër.

Një zinxhir Markovi ose proces Markovi është një model stokastik që përshkruan një seri ngjarjesh të mundshme në të cilat probabiliteti i secilës ngjarje varet vetëm nga gjendja e arritur në ngjarjen e mëparshme. Joformalisht, kjo mund të mendohet si, "Ajo që do të ndodhë më pas varet vetëm nga gjendja tani ." Një seri e pafundme e numërueshme, në të cilën zinxhiri ndryshon gjendjen në hapa kohorë diskrete, jep një zinxhir Markovi në kohë diskrete (ZMKD). Një proces me kohë të vazhdueshme quhet zinxhir Markovi me kohë të vazhdueshme (ZMKV). Është emëruar pas matematikanit rus Andrey Markov .

Zinxhirët e Markovit kanë shumë zbatime si modele statistikore të proceseve të botës reale, të tilla si studimi i sistemeve të kontrollit të drejtimit në automjetet motorike, radhët ose rreshtat e klientëve që mbërrijnë në një aeroport, kurset e këmbimit valutor dhe dinamikat e popullsisë së kafshëve.

Proceset Markov janë baza për metodat e përgjithshme të simulimit stokastik të njohura si zinxhirët Markov Monte Carlo, të cilat përdoren për simulimin e kampionimit nga shpërndarjet e ndërlikuara të probabilitetit dhe kanë gjetur zbatim në statistikat e Bejesit, termodinamikë, mekanikë statistikore, fizikë, kimi, ekonomi, financë, përpunimin e sinjalit, teorinë e informacionit dhe përpunimin e të folurit .

Përkufizimi formal

Zinxhirët e Markovit në kohë diskrete

Një zinxhir Markovi në kohë diskrete është një seri e ndryshoreve të rastit X ₁, X ₂, X ₃, ... me vetinë Markov, domethënë që probabiliteti për të kaluar në gjendjen tjetër varet vetëm nga gjendja e tanishme dhe jo nga gjendja e mëparshme pohon se:

$\mathrm{Pr}(X_{n+1}=x\mid X_1=x_1,X_2=x_2,\dots ,X_n=x_n)=\mathrm{Pr}(X_{n+1}=x\mid X_n=x_n),$ nëse të dy probabilitetet me kusht janë të përcaktuara mirë, pra nëse $\mathrm{Pr}(X_1=x_1,\dots ,X_n=x_n)>0.$

Vlerat e mundshme të X _i formojnë një bashkësi të numërueshme S të quajtur hapësira e gjendjes së zinxhirit.

Zinxhiri Markov në kohë të vazhduar

Një zinxhir Markovi me kohë të vazhdueshme ( X _t ) _t ≥ 0 përcaktohet nga një hapësirë gjendjeje e fundme ose e numërueshme S, një matricë e shpejtësisë së kalimit Q me dimensione të barabarta me atë të hapësirës së gjendjes dhe shpërndarjen fillestare të probabilitetit të përcaktuar në hapësirën e gjendjes. Për i ≠ j, elementët q _ij janë jonegativë dhe përshkruajnë shpejtësinë e kalimit të procesit nga gjendja i në gjendjen j . Elementet q _ii zgjidhen të tillë që çdo rresht i matricës së shkallës së kalimit e ka shumën zero, ndërsa shumat e rreshtave të një matrice të kalimit të probabilitetit në një zinxhir (diskret) Markov janë të gjitha të barabarta me një.

Aplikacionet

Hulumtimet kanë raportuar aplikimin dhe dobinë e zinxhirëve Markov në një gamë të gjerë temash si fizika, kimia, biologjia, mjekësia, muzika, teoria e lojërave dhe sportet.

Fizika

Sistemet Markoviane shfaqen gjerësisht në termodinamikë dhe mekanikë statistikore, sa herë që përdoren probabilitete për të përfaqësuar detaje të panjohura ose të pamodeluara të sistemit, nëse mund të supozohet se dinamika është e pandryshueshme në kohë dhe se nuk duhet të merret parasysh historia përkatëse e cila nuk është përfshirë tashmë në përshkrimin e gjëndjes. Për shembull, një gjendje termodinamike funksionon nën një shpërndarje probabiliteti që është e vështirë ose e shtrenjtë për t'u marrë. Prandaj, metoda e zinxhirëve të Markovit Monte Carlo mund të përdoret për të nxjerrë zgjedhje rastësisht nga një kuti e zezë për të përafruar shpërndarjen e probabilitetit të atributeve mbi një sërë objektesh.

Shtigjet, në formulimin integral të shtegut të mekanikës kuantike, janë zinxhirë Markov.

Biologjia

Zinxhirët Markov përdoren në fusha të ndryshme të biologjisë. Shembuj të dukshëm janë:

• Filogjenetika dhe bioinformatika, ku shumica e modeleve të evolucionit të ADN-së përdorin zinxhirë Markov në kohë të vazhdueshme për të përshkruar nukleotidin e pranishëm në një vend të caktuar në gjenom .
• Dinamika e popullsisë, ku zinxhirët Markov janë në veçanti një mjet qendror në studimin teorik të modeleve të matricës së popullsisë .
• Neurobiologjia, ku zinxhirët Markov janë përdorur, p.sh., për të simuluar neokorteksin e gjitarëve.
• Biologjia e sistemeve, për shembull me modelimin e infeksionit viral të qelizave të vetme.
• Modelet e ndarjes për shpërthimin e sëmundjes dhe modelimin e epidemisë.

Njohja e të folurit

Modelet e fshehura Markov janë baza për shumicën e sistemeve moderne të njohjes automatike të të folurit .

Teoria e informacionit

Zinxhirët Markov përdoren gjatë përpunimit të informacionit. Punimi i famshëm i Claude Shannon i vitit 1948 Një Teori Matematike e Komunikimit, i cili në një hap të vetëm krijoi fushën e teorisë së informacionit, hapet duke prezantuar konceptin e entropisë përmes modelimit Markov të gjuhës angleze. Modele të tilla të idealizuara mund të kapin shumë nga rregullsitë statistikore të sistemeve. Edhe pa e përshkruar strukturën e plotë të sistemit në mënyrë të përsosur, modele të tilla sinjalesh mund të bëjnë të mundur ngjeshjen shumë efektive të të dhënave përmes teknikave të kodimit të entropisë, siç është kodimi aritmetik . Ato gjithashtu lejojnë vlerësimin efektiv të gjendjes dhe njohjen e modelit . Zinxhirët Markov luajnë gjithashtu një rol të rëndësishëm në të mësuarit përforcues .

Zinxhirët Markov janë gjithashtu baza për modelet e fshehura Markov, të cilat janë një mjet i rëndësishëm në fusha të tilla të ndryshme si rrjetet telefonike (të cilat përdorin algoritmin Viterbi për korrigjimin e gabimeve), njohja e të folurit dhe bioinformatika (si për shembull në zbulimin e rirregullimeve ).

Zbatimet në internet

Një diagram gjendjesh që përfaqëson algoritmin PageRank me një probabilitet kalimtar prej M, ose $\frac{\alpha }{k_i}+\frac{1-\alpha }{N}$ .

PageRank e fnjë faqe interneti siç përdoret nga Google përcaktohet nga një zinxhir Markovi. Është probabiliteti për të qenë në një faqe $i$ në shpërndarjen stacionare të zinxhirit pasues të Markovit në të gjitha faqet e internetit (të njohura). Nëse $N$ është numri i uebfaqeve të njohura dhe një faqe $i$ ka $k_i$ lidhet me të, atëherë ka probabilitet kalimi $\frac{\alpha }{k_i}+\frac{1-\alpha }{N}$ për të gjitha faqet që janë të lidhura me dhe $\frac{1-\alpha }{N}$ për të gjitha faqet që nuk janë të lidhura me. Parametri $\alpha$ merret rreth 0.15.

Modelet Markov janë përdorur gjithashtu për të analizuar sjelljen e përdoruesve të navigimit në ueb.

Ekonomia dhe financa

Makroekonomia dinamike përdor shumë zinxhirët Markov. Një shembull është përdorimi i zinxhirëve Markov për të modeluar në mënyrë ekzogjene çmimet e kapitalit (aksioneve) në një mjedis ekuilibri të përgjithshëm .

Agjencitë e vlerësimit të kredisë prodhojnë tabela vjetore të probabiliteteve të kalimit për obligacionet me vlerësime të ndryshme krediti.