Vikipedio:Projekto matematiko/Markova ĉeno

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al
Markova ĉeno
(eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En matematiko, (diskreta-tempo) Markova ĉeno, nomis post _Andrey_ Markova, estas diskreta-tempa stokastiko kun la Markova propraĵo. En tia procezo, la antaŭaj ŝtatoj estas netaŭga por aŭguranta la sinsekvaj ŝtatoj, donita scio de la aktuala (ŝtato, stato, stati).

Estas ankaŭ kontinu-tempaj markovaj ĉenoj.

Markova ĉeno estas vico X₁, X₂, X₃, ... de hazarda variablo. La limigo de ĉi tiuj (variabloj, variablas), kio estas, la aro de ilia ebla (valoroj, valoras), estas (nomita, vokis) la (ŝtato, stato, stati) spaco, la valoro de X_n estante la (ŝtato, stato, stati) de la procezo je tempo n. Se la kondiĉa probabla distribuo de X_n+1 sur pasintaj ŝtatoj estas funkcio de X_n sola, tiam:

$\Pr(X_{n+1}=x|X_0, X_1, X_2, \ldots, X_n) = \Pr(X_{n+1}=x|X_n), \,$

kie x estas iu (ŝtato, stato, stati) de la procezo. La idento pli supre identigas la Markova propraĵo.

Simpla vojo al _visualise_ specifa tipo de Markova ĉeno estas tra finia stata maŝino. Se vi estas je (ŝtato, stato, stati) y je tempo n, tiam la probablo (tiu, ke, kiu) vi estos movi sur al (ŝtato, stato, stati) x je tempo n + 1 ne dependi sur n, kaj nur dependas sur la aktuala (ŝtato, stato, stati) y (tiu, ke, kiu) vi estas en. De ĉi tie je ĉiumomente n, a finia Markova ĉeno povas esti karakterizita per matrico de (probabloj, probablas) kies x, y ero estas donita per $\Pr(X_{n+1}=x|X_n=y) \,$ kaj estas sendependa de la tempa indekso n. Ĉi tiuj (specoj, specas) de diskretaj finiaj Markovaj ĉenoj povas ankaŭ esti priskribita per orientita grafeo, kie la randoj estas (etikedita, markita) per la (probabloj, probablas) de iranta de unu (ŝtato, stato, stati) al la alia (ŝtato, stato, stati) (tiu, ke, kiu) estas sur ĉu fino de la direktita rando.

_Andrey_ Markova produktis la unuaj rezultoj (1906) por ĉi tiuj procezoj. Ĝeneraligo al kalkuleble malfinio (ŝtato, stato, stati) (spacoj, kosmoj, spacetoj) estis donita per Kolmogorova (1936). Markovaj ĉenoj estas rilatanta al Moviĝo de Brown kaj la _ergodic_ hipotezo, du temoj en fiziko kiu estis grava en la frua (jaroj, jaras) de la dudeka jarcento, sed Markova (aperas, ŝajnas, aspektas) al havi ĉasita ĉi tiu el matematika motivado, nome la vastigaĵo de la leĝo de grandaj nombroj al dependa (eventoj, eventas).

Enhavo

1 Propraĵoj de Markovaj ĉenoj
2 Markovaj ĉenoj en diskreta (ŝtato, stato, stati) (spacoj, kosmoj, spacetoj)
3 Sciencaj aplikoj
4 Markova (parodii, travestii) (naskantoj, naskantas, generiloj, generas)
5 Vidu ankaŭ jenon:
6 Referencoj
7 Ekstera (ligoj, ligas)

[redaktu] Propraĵoj de Markovaj ĉenoj

Markova ĉeno estas karakterizita per la kondiĉa distribuo

$\Pr(X_{n+1}=x| X_n)\,$

kiu estas (nomita, vokis) la traira probablo de la procezo. Ĉi tiu estas iam (nomita, vokis) la "unu-(ŝtupo, paŝi)" traira probablo. La probablo de trairo en du, tri, aŭ pli (ŝtupoj, ŝtupas, paŝas) estas derivita de la unu-(ŝtupo, paŝi) traira probablo kaj la Markova propraĵo:

$\Pr(X_{n+2}=x|X_n) = \int \Pr(X_{n+2}=x,X_{n+1}=y|X_n)\,dy = \int \Pr(X_{n+2}=x|X_{n+1}=y) \, \Pr(X_{n+1}=y|X_n) \, dy$

Ankaŭ,

$\Pr(X_{n+3}=x|X_n) = \int \int \Pr(X_{n+3}=x|X_{n+2}=y)\, \Pr(X_{n+2}=y|X_{n+1}=z) \, \Pr(X_{n+1}=z|X_n) \, dz \, dy$

Ĉi tiuj (formuloj, formulas) ĝeneraligi al ajna estonto (tempoj, tempas) n + k per multiplikante la trairo (probabloj, probablas) kaj integralanta k − 1 (tempoj, tempas).

La bagatela distribuo _Pr_(X_n = x) estas la distribuo super ŝtatoj je tempo n. La komenca distribuo estas _Pr_(X₀ = x). La evoluismo de la procezo tra unufoje (ŝtupo, paŝi) estas priskribita per

$\Pr(X_{n+1}=x) = \int P(X_{n+1}=x|X_n=y)\,P(X_n=y)\,dy$

Ĉi tiu estas versio de la Frobenius-a-_Perron_ ekvacio. Tie (majo, povas) ekzisti unu aŭ pli (ŝtato, stato, stati) distribuoj π tia (tiu, ke, kiu)

$\pi(x) = \int \Pr(X=x|Y=y)\,\pi(y)\,dy$

kie Y estas (justa, ĵus) oportuna nomo por la (variablo, varianta) de integralado. Tia distribuo π estas (nomita, vokis) oficejaĵara distribuo aŭ neŝanĝiĝema-(ŝtato, stato, stati) distribuo, aŭ iam Gibbsa stato. Oficejaĵara distribuo estas propra funkcio de la kondiĉa distribua funkcio, asociita kun la ajgeno 1.

Ĉu estas oficejaĵara distribuo, kaj ĉu ĝi estas unika se ĝi faras ekzisti, estas difinita per certaj propraĵoj de la procezo. Nereduktebla (meznombroj, meznombras, signifas) (tiu, ke, kiu) ĉiu (ŝtato, stato, stati) estas alirebla de ĉiu alia (ŝtato, stato, stati). Procezo estas perioda se tie ekzistas almenaŭ unu (ŝtato, stato, stati) al kiu la procezo estos daŭre redoni kun (fiksis, neŝanĝebligita) tempo (periodo, punkto) (pli granda ol unu). Neperioda (meznombroj, meznombras, signifas) (tiu, ke, kiu) estas ne tia (ŝtato, stato, stati). Pozitiva _recurrent_ (meznombroj, meznombras, signifas) (tiu, ke, kiu) la atendis redoni tempo estas finia por ĉiu (ŝtato, stato, stati). Iam la (termoj, kondiĉoj, terminoj, termas, terminas) nemalmuntebla, necikla, kaj persista estas uzitaj kiel sinonimoj por "nereduktebla", "neperioda", kaj "_recurrent_", respektive. Kiam la (ŝtato, stato, stati) spaco de Markova ĉeno estas ne nereduktebla, ĝi (majo, povas) esti dispartigita enen aro de (nereduktebla) komunikantaj klasoj, ĉiu kies (majo, povas) esti (klasifikita, klasigita) kiel pli supre. La problemo de klasifiko estas grava unu en la matematika studi de Markovaj ĉenoj kaj rilatantaj stokastikoj.

Se la Markova ĉeno estas pozitiva _recurrent_, tie ekzistas oficejaĵara distribuo. Se ĝi estas pozitiva _recurrent_ kaj nereduktebla, tie ekzistas unika oficejaĵara distribuo, kaj plue la procezo konstruis per prenante la oficejaĵara distribuo kiel la komenca distribuo estas _ergodic_. Tiam la averaĝa de funkcio f super specimenoj de la Markova ĉeno estas egala al la averaĝa kun respekto al la oficejaĵara distribuo,

$\lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}^{n-1} f(X_k) = \int f(x)\,\pi(x)\,dx$

En aparta, ĉi tiu tenas por f egala al la identa funkcio. Tial la averaĝa de specimeno (valoroj, valoras) super tempo estas egala al la (atendata valoro, atendita valoro) de la oficejaĵara distribuo.

Plue, la ekvivalento de averaĝoj ankaŭ tenas se f estas la nadla funkcio sur iu subaro A de la (ŝtato, stato, stati) spaco.

$\lim_{n\rightarrow\infty}\; \frac{1}{n} \; \sum_{k=0}^{n-1} \chi_A(X_k) = \int_A \pi(x)\,dx = \mu_{\pi}(A)$

kie μ_π estas la mezuri konkludita per π. Ĉi tiu (konstruas, faras) ĝi ebla al aproksimi la oficejaĵara distribuo per _histogram_ aŭ alia denseco taksi de vico de specimenoj.

[redaktu] Markovaj ĉenoj en diskreta (ŝtato, stato, stati) (spacoj, kosmoj, spacetoj)

Se la (ŝtato, stato, stati) spaco estas finia, la traira probablodistribuo povas esti (prezentita, prezentis) kiel matrico, (nomita, vokis) la traira matrico, kun la (mi, j)'(th, -a) ero egala al

$P_{ij} = \Pr(X_{n+1}=j\mid X_n=i) \,$

Por diskreta (ŝtato, stato, stati) spaco, la (integraladoj, integraladas) en la k-(ŝtupo, paŝi) traira probablo estas (sumadoj, sumadas), kaj povas esti komputita kiel la k'(th, -a) povo de la traira matrico. Tio estas, se P estas la unu-(ŝtupo, paŝi) traira matrico, tiam P^k estas la traira matrico por la k-(ŝtupo, paŝi) trairo.

La oficejaĵara distribuo estas vektoro kiu (verigas, kontentigas) la ekvacio

$\pi^{T}\mathbf{P} = \pi^{T},$

kie $π T$ estas la transponi de $π$ . En alia (vortoj, vortas), la oficejaĵara distribuo $π$ estas (maldekstre, restita) ajgenvektoro de la traira matrico, asociita kun la ajgeno 1.

Sekve de tio, neniu la ekzisto nek la unikeco de oficejaĵara distribuo estas garantiita por ĝenerala traira matrico P. Tamen, se la traira matrico P estas nereduktebla kaj neperioda, tiam tie ekzistas unika oficejaĵara distribuo $π$ . Aldone, P^k konverĝas _elementwise_ al rango-unu matrico en kiu ĉiu (linio, vico) estas la (transponi de la) oficejaĵara distribuo $π T$ , tio estas

$\lim_{k\rightarrow\infty}\mathbf{P}^k=\mathbf{1}\pi^T,$

kie $\mathbf{1}$ estas la kolumna vektoro kun ĉiuj elementoj egala al 1. Ĉi tiu estas komencita per la _Perron_-Teoremo de Frobenius.

Ĉi tiu (meznombroj, meznombras, signifas) (tiu, ke, kiu) se ni simuli aŭ observi hazarda marŝo kun traira matrico P, tiam la longtempa probablo de ekzisto de la _walker_ en donita (ŝtato, stato, stati) estas sendependa de kie la ĉeno estis startita, kaj estas diktita per la oficejaĵara distribuo. La hazarda marŝo "forgesas" la pasinta. Unuvorte, Markovaj ĉenoj estas la "venonta aĵo" post senmemoraj procezoj (kio estas, vico de sendependa idente distribuis hazarda variablo).

Traira matrico kiu estas pozitiva (tio estas, ĉiu ero de la matrico estas pozitiva) estas nereduktebla kaj neperioda. Matrico estas stokasta matrico se kaj nur se ĝi estas la matrico de trairo (probabloj, probablas) de iu Markova ĉeno.

La speciala okazo de la traira probablo estante sendependa de la pasinta estas sciata kiel la Skemo de Bernoulli. Skemo de Bernoulli kun nur du eblaj ŝtatoj estas sciata kiel Procezo de Bernoulli.

[redaktu] Sciencaj aplikoj

_Markovian_ sistemoj aperi (mult)amplekse en fiziko, aparte statistika mekaniko, ĉiam (probabloj, probablas) estas uzitaj al prezenti nekonato aŭ _unmodelled_ (detaloj, detalas) de la sistemo, se ĝi povas esti alprenita (tiu, ke, kiu) la dinamiko estas tempo-invarianto, kaj (tiu, ke, kiu) ne taŭga historio (bezoni, bezono, necesa) esti konsiderata kiu estas ne jam inkluzivis en la (ŝtato, stato, stati) priskribo.

Markovaj ĉenoj povas ankaŭ kutimi modelaj diversaj procezoj en viciga teorio kaj statistiko. _Claude_ Shannon-a's fama 1948 papero A matematika teorio de komunikado, kiu je sola (ŝtupo, paŝi) kreita la kampo de informa teorio, malfermas per prezentanta la koncepto de entropio tra Markova modelanta de la Angla lingvo. Tia _idealised_ (modeloj, modelas) povas (enkapti, kapto) multaj de la statistikaj regulecoj de sistemoj. (Ebena, Para, Eĉ) sen priskribanta la plena strukturo de la sistemo perfekte, tia signali (modeloj, modelas) povas fari ebla tre efika datuma kunpremo tra entropiaj kodantaj teknikoj kiel aritmetika kodigo. Ili ankaŭ permesi efika (ŝtato, stato, stati) proksumumo kaj rekonado de ŝablonoj. La mondaj poŝtelefonaj sistemoj dependi sur la _Viterbi_ algoritmo por eraro-korektado, dum Latentaj Markovaj modeloj (kie la Markova trairo (probabloj, probablas) estas (komence, fonte) nekonato kaj devas ankaŭ esti taksita de la datumoj) estas (mult)amplekse uzita en parolado (ekkono, rekonado) kaj ankaŭ en biokomputiko, ekzemple por kodanta regiono/gena antaŭdiro.

La _PageRank_ de _webpage_ kiel uzita per Google estas difinita per Markova ĉeno. Ĝi estas la probablo al esti je paĝo mi en la oficejaĵara distribuo sur jena Markova ĉeno sur ĉiuj (sciata) _webpages_. Se N estas la nombro de sciata _webpages_, kaj paĝo mi havas k_mi (ligoj, ligas) tiam ĝi havas traira probablo (1-q)/k_mi + q/N por ĉiuj paĝoj (tiu, ke, kiu) estas (ĉenerita, ligita, bindita) al kaj q/N por ĉiuj paĝoj (tiu, ke, kiu) estas ne (ĉenerita, ligita, bindita) al. La parametro q estas prenita al cirkuli 0.15.

Markovaj ĉenaj manieroj havi ankaŭ iĝi tre grava por generante (vicoj, vicas) de hazardaj nombroj al precize reflekti tre komplika deziris probablodistribuoj - procezo (nomita, vokis) Markova ĉeno Monte-a _Carlo_ aŭ _MCMC_ por mallonga. En ĵusa (jaroj, jaras) ĉi tiu havas _revolutionised_ la _practicability_ de Konkludo de Bayes manieroj.

Markovaj ĉenoj ankaŭ havi multaj aplikoj en biologia modelanta, aparte loĝantaraj procezoj, kiu estas utila en modelantaj procezoj (tiu, ke, kiu) estas (almenaŭ) analoga al biologia (loĝantaroj, loĝantaras).

Ĵusa apliko de Markovaj ĉenoj estas en terstatistiko. Tio estas, Markovaj ĉenoj estas uzitaj en du al tri dimensia stokasto (simuladoj, simuladas) de diskreta (variabloj, variablas) kondiĉa sur observis datumoj. Tia apliko estas (nomita, vokis) "Markova ĉena terstatistiko", simila kun _kriging_ terstatistiko. La Markova ĉena terstatistika maniero estas ankoraŭ en evoluo.

Markovaj ĉenoj povas kutimi modelo multaj (ludoj, ludas) de ŝanco. La porinfana (ludoj, ludas) _Chutes_ kaj (Eskaloj, Eskalas, Ŝtupetaroj, Ŝtupetaras) kaj Bombona Lando, ekzemple, estas (prezentita, prezentis) akurate per Markovaj ĉenoj. Je ĉiu turni, la ludanto startas en donita (ŝtato, stato, stati) (sur donita kvadrato) kaj de tie havas (fiksita, neŝanĝebligita) _odds_ de movanta al certaj aliaj ŝtatoj ((kvadratoj, placoj, kvadratigas)).

[redaktu] Markova (parodii, travestii) (naskantoj, naskantas, generiloj, generas)

Markovaj procezoj povas ankaŭ kutimi generi malprofunde "(reala, reela)-(aspektanta, rigardanta)" teksta donita specimena dokumento: ili estas uzitaj en diversaj (pecoj, pecas) de rekrea "(parodii, travestii) generilo" programaro (vidi _dissociated_ premi, _Jeff_ _Harrison_, Marko V _Shaney_ aŭ [1]). Markovaj ĉenoj havi ankaŭ estas uzita en muzika komponaĵo.

[redaktu] Vidu ankaŭ jenon:

Latenta Markova modelo
(Ekzemploj, Ekzemplas) de Markovaj ĉenoj
Markova procezo
Markova decida procezo
Skipo de finia tipo
Marko V _Shaney_
Fazo-tipa distribuo

[redaktu] Referencoj

A.A. Markova. "_Rasprostranenie_ _zakona_ _bol_'_shih_ (ĉizilo, ĉizi) na _velichiny_, _zavisyaschie_ (drogo, kuracilo, narkotaĵo) _ot_ _druga_". _Izvestiya_ _Fiziko_-_matematicheskogo_ _obschestva_ _pri_ _Kazanskom_ _universitete_, 2-_ya_ _seriya_, _tom_ 15, _pp_ 135-156, 1906.

A.A. Markova. "Vastigaĵo de la limigo (teoremoj, teoremas) de teorio de probabloj al (sumo, sumi) de (variabloj, variablas) koneksa en ĉeno". represita en Apendico B de: R. _Howard_. Dinamikaj Probablecaj Sistemoj, volumeno 1: Markovaj Ĉenoj. Johano _Wiley_ kaj (Filoj, Fas), 1971.

(Leono (Zodiako), Leono) _Breiman_. Probablo. Originala redakcio (publikigita, publikigis) per Addison-a-_Wesley_, 1968; represis per Socio por Industria kaj Aplikis Matematiko, 1992. ISBN 0-89871-296-3. (Vidi Ĉapitro 7.)