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. ^[1] ^[2] ^[3] 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, ^[1] ^[4] ^[5] ^[6] 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. ^[7]

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 . ^[7] ^[8] ^[9]

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:

\Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\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

\Pr(X_{1}=x_{1},\ldots ,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. ^[10] ^[11] 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. ^[11]

Shtigjet, në formulimin integral të shtegut të mekanikës kuantike, janë zinxhirë Markov. ^[12]

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. ^[13]
Biologjia e sistemeve, për shembull me modelimin e infeksionit viral të qelizave të vetme. ^[14]
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 ^[15] ).

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. ^[16] ^[17] Ë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 . ^[18]

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

^ ^a ^b Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. fq. 1–235. ISBN 978-1-119-38755-8. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!) Gabim referencash: Invalid <ref> tag; name ":0" defined multiple times with different content
^ "Markov chain | Definition of Markov chain in US English by Oxford Dictionaries". Oxford Dictionaries. Arkivuar nga origjinali më 15 dhjetor 2017. Marrë më 2017-12-14. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Definition at Brilliant.org "Brilliant Math and Science Wiki". Retrieved on 12 May 2019
^ Samuel Karlin; Howard E. Taylor (2 dhjetor 2012). A First Course in Stochastic Processes. Academic Press. fq. 47. ISBN 978-0-08-057041-9. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Bruce Hajek (12 mars 2015). Random Processes for Engineers. Cambridge University Press. ISBN 978-1-316-24124-0. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ G. Latouche; V. Ramaswami (1 janar 1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM. fq. 4–. ISBN 978-0-89871-425-8. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ ^a ^b Sean Meyn; Richard L. Tweedie (2 prill 2009). Markov Chains and Stochastic Stability. Cambridge University Press. fq. 3. ISBN 978-0-521-73182-9. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!) Gabim referencash: Invalid <ref> tag; name "MeynTweedie2009page3" defined multiple times with different content
^ Reuven Y. Rubinstein; Dirk P. Kroese (20 shtator 2011). Simulation and the Monte Carlo Method. John Wiley & Sons. fq. 225. ISBN 978-1-118-21052-9. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Dani Gamerman; Hedibert F. Lopes (10 maj 2006). Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, Second Edition. CRC Press. ISBN 978-1-58488-587-0. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Fitzpatrick, Richard. "Thermodynamics and Statistical Mechanics" (PDF). Arkivuar (PDF) nga origjinali më 2016-11-30. Marrë më 2017-06-02. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ ^a ^b van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (2016-03-11). "A simple introduction to Markov Chain Monte–Carlo sampling". Psychonomic Bulletin & Review. 25 (1): 143–154. doi:10.3758/s13423-016-1015-8. ISSN 1069-9384. PMC 5862921. PMID 26968853. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Ryder, Lewis H. (1985). Quantum field theory. Cambridge [Cambridgeshire]: Cambridge University Press. fq. 160. ISBN 978-0521338592. OCLC 10533049. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ George, Dileep; Hawkins, Jeff (2009). Friston, Karl J. (red.). "Towards a Mathematical Theory of Cortical Micro-circuits". PLOS Comput Biol. 5 (10): e1000532. Bibcode:2009PLSCB...5E0532G. doi:10.1371/journal.pcbi.1000532. PMC 2749218. PMID 19816557. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)Mirëmbajtja CS1: DOI i lirë i pashënjuar (lidhja)
^ Gupta, Ankur; Rawlings, James B. (prill 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268. doi:10.1002/aic.14409. PMC 4946376. PMID 27429455. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Pratas, D; Silva, R; Pinho, A; Ferreira, P (18 maj 2015). "An alignment-free method to find and visualise rearrangements between pairs of DNA sequences". Scientific Reports. 5: 10203. Bibcode:2015NatSR...510203P. doi:10.1038/srep10203. PMC 4434998. PMID 25984837. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Gupta, Brij; Agrawal, Dharma P.; Yamaguchi, Shingo (16 maj 2016). Handbook of Research on Modern Cryptographic Solutions for Computer and Cyber Security. IGI Global. fq. 448–. ISBN 978-1-5225-0106-0. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Langville, Amy N.; Meyer, Carl D. (2006). "A Reordering for the PageRank Problem" (PDF). SIAM Journal on Scientific Computing. 27 (6): 2112–2113. Bibcode:2006SJSC...27.2112L. CiteSeerX 10.1.1.58.8652. doi:10.1137/040607551. ISSN 1064-8275. Arkivuar (PDF) nga origjinali më 2017-09-21. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ Brennan, Michael; Xiab, Yihong. "Stock Price Volatility and the Equity Premium" (PDF). Department of Finance, the Anderson School of Management, UCLA. Arkivuar nga origjinali (PDF) më 2008-12-28. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
^ "A Markov Chain Example in Credit Risk Modelling Columbia University lectures" (PDF). Columbia University. Arkivuar nga origjinali (PDF) më 24 mars 2016. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[:0-1] Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. fq. 1–235. ISBN 978-1-119-38755-8. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!) Gabim referencash: Invalid <ref> tag; name ":0" defined multiple times with different content

[2] "Markov chain | Definition of Markov chain in US English by Oxford Dictionaries". Oxford Dictionaries. Arkivuar nga origjinali më 15 dhjetor 2017. Marrë më 2017-12-14. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[3] Definition at Brilliant.org "Brilliant Math and Science Wiki". Retrieved on 12 May 2019

[KarlinTaylor2012page47-4] Samuel Karlin; Howard E. Taylor (2 dhjetor 2012). A First Course in Stochastic Processes. Academic Press. fq. 47. ISBN 978-0-08-057041-9. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[Hajek2015-5] Bruce Hajek (12 mars 2015). Random Processes for Engineers. Cambridge University Press. ISBN 978-1-316-24124-0. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[LatoucheRamaswami1999-6] G. Latouche; V. Ramaswami (1 janar 1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM. fq. 4–. ISBN 978-0-89871-425-8. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[MeynTweedie2009page3-7] Sean Meyn; Richard L. Tweedie (2 prill 2009). Markov Chains and Stochastic Stability. Cambridge University Press. fq. 3. ISBN 978-0-521-73182-9. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!) Gabim referencash: Invalid <ref> tag; name "MeynTweedie2009page3" defined multiple times with different content

[RubinsteinKroese2011page225-8] Reuven Y. Rubinstein; Dirk P. Kroese (20 shtator 2011). Simulation and the Monte Carlo Method. John Wiley & Sons. fq. 225. ISBN 978-1-118-21052-9. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[GamermanLopes2006-9] Dani Gamerman; Hedibert F. Lopes (10 maj 2006). Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, Second Edition. CRC Press. ISBN 978-1-58488-587-0. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[10] Fitzpatrick, Richard. "Thermodynamics and Statistical Mechanics" (PDF). Arkivuar (PDF) nga origjinali më 2016-11-30. Marrë më 2017-06-02. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[auto1-11] van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (2016-03-11). "A simple introduction to Markov Chain Monte–Carlo sampling". Psychonomic Bulletin & Review. 25 (1): 143–154. doi:10.3758/s13423-016-1015-8. ISSN 1069-9384. PMC 5862921. PMID 26968853. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[12] Ryder, Lewis H. (1985). Quantum field theory. Cambridge [Cambridgeshire]: Cambridge University Press. fq. 160. ISBN 978-0521338592. OCLC 10533049. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[13] George, Dileep; Hawkins, Jeff (2009). Friston, Karl J. (red.). "Towards a Mathematical Theory of Cortical Micro-circuits". PLOS Comput Biol. 5 (10): e1000532. Bibcode:2009PLSCB...5E0532G. doi:10.1371/journal.pcbi.1000532. PMC 2749218. PMID 19816557. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)Mirëmbajtja CS1: DOI i lirë i pashënjuar (lidhja)

[14] Gupta, Ankur; Rawlings, James B. (prill 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268. doi:10.1002/aic.14409. PMC 4946376. PMID 27429455. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[rearrang-15] Pratas, D; Silva, R; Pinho, A; Ferreira, P (18 maj 2015). "An alignment-free method to find and visualise rearrangements between pairs of DNA sequences". Scientific Reports. 5: 10203. Bibcode:2015NatSR...510203P. doi:10.1038/srep10203. PMC 4434998. PMID 25984837. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[BrijP.2016-16] Gupta, Brij; Agrawal, Dharma P.; Yamaguchi, Shingo (16 maj 2016). Handbook of Research on Modern Cryptographic Solutions for Computer and Cyber Security. IGI Global. fq. 448–. ISBN 978-1-5225-0106-0. Arkivuar nga origjinali më 23 mars 2017. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[LangvilleMeyer2006-17] Langville, Amy N.; Meyer, Carl D. (2006). "A Reordering for the PageRank Problem" (PDF). SIAM Journal on Scientific Computing. 27 (6): 2112–2113. Bibcode:2006SJSC...27.2112L. CiteSeerX 10.1.1.58.8652. doi:10.1137/040607551. ISSN 1064-8275. Arkivuar (PDF) nga origjinali më 2017-09-21. {{cite journal}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[18] Brennan, Michael; Xiab, Yihong. "Stock Price Volatility and the Equity Premium" (PDF). Department of Finance, the Anderson School of Management, UCLA. Arkivuar nga origjinali (PDF) më 2008-12-28. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[19] "A Markov Chain Example in Credit Risk Modelling Columbia University lectures" (PDF). Columbia University. Arkivuar nga origjinali (PDF) më 24 mars 2016. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]