Cadena de Màrkov

Un diagrama que representa un procés de Markov de dos estats, amb els estats etiquetats com a E i A. Cada número representa la probabilitat que el procés de Màrkov canviï d'un estat a un altre, amb la direcció indicada per la fletxa. Per exemple, si el procés de Màrkov està en l'estat A, aleshores la probabilitat que canviï l'estat E és 0.4, mentre que la probabilitat que romangui en l'estat A és 0.6.

Una cadena de Màrkov , que rep el seu nom del matemàtic rus Andrei Màrkov (1856-1922), és una sèrie d'esdeveniments, en la qual la probabilitat que passi un esdeveniment depèn de l'esdeveniment immediat anterior. En efecte, les cadenes d'aquest tipus tenen memòria. "Recorden" l'últim esdeveniment i això condiciona les possibilitats dels esdeveniments futurs. Aquesta dependència de l'esdeveniment anterior distingeix a les cadenes de Màrkov de les sèries d'esdeveniments independents, com tirar una moneda a l'aire o un dau.

Aquest tipus de procés, introduït per Màrkov en un article publicat a 1907, presenta una forma de dependència simple, però molt útil en molts models, entre les variables aleatòries que formen un procés estocàstic. En els negocis, les cadenes de Màrkov s'han utilitzat per analitzar els patrons de compra dels deutors morosos, per planificar les necessitats de personal i per analitzar el reemplaçament d'equip.

Les seves aplicacions són diverses, com ara en els models estadístics de procesos del món real, com ara l'estudi dels sistemes de control de creuer en vehicles amb motor, les cues de clients que arriben en un aeroport, les taxes de canvi de les monedes i les dinàmiques poblacionals dels animals.

Els processos de Markov són la base dels mètodes generals de simulació estocàstica coneguts com cadena de Markov Monte Carlo, que s'utilitzen per simular mostres que provenen de distribucions probabilístiques complexes, i se n'han trobat aplicacions en l'estadística bayesiana, la termodinàmica, la mecànica estadística, la física, la química, l'economia, les finances, el processament de senyals, la teoria de la informació i la intel·ligència artificial.

S'utilitza l'adjectiu markovià (en anglès, Markovian) per notar que alguna cosa està relacionada amb el procés de Markov.

Definició formal

En les matemàtiques, es defineix com un procés estocàstic discret que compleix amb la propietat de Màrkov, és a dir, si es coneix la història del sistema fins a la seva moment actual, el seu estat present resumeix tota la informació rellevant per descriure en probabilitat el seu estat futur.

Una cadena de Màrkov és una seqüència X ₁ , X ₂ , X ₃ , ... de variables aleatòries. El rang d'aquestes variables, és anomenat espai estat, el valor de X _n és l'estat del procés en el temps n . Si la distribució de probabilitat condicional de X _{n +1} en estats passats és una funció de X _n per si sola, aleshores:

$P(X_{n+1}=x_{n+1}|x_{n}=x_{n},X_{n-1}=x_{n-1},\ldots ,x_{2}=x_{2},x_{1}=x_{1})=P(X_{n+1}=x_{n+1}|x_{n}=x_{n}).\,$

On x _i és l'estat del procés en l'instant i . La identitat mostrada és la propietat de Màrkov.

Notació útil

Cadenes homogènies i no homogènies

• Una cadena de Markov es diu homogènia si la probabilitat d'anar de l'estat i a l'estat j en un pas no depèn del temps en què es troba la cadena, és a dir:

$P(x_{n}=j|X_{n-1}=i)=P(x_{1}=j|x_{0}=i)\,$ per a tot ni per a qualsevol i, j.

Si per alguna parella d'estats i per algun temps n la propietat abans esmentada no es compleix direm que la cadena de Màrkov és no homogènia.

Probabilitats de transició i matriu de transició

• La probabilitat d'anar de l'estat i a l'estat j a n unitats de temps és

$p_{ij}^{(n)}=\Pr(x_{n}=j\mid x_{0}=i)\,$,

en la probabilitat de transició en un pas s'omet el superíndex de manera que queda

$p_{ij}=\Pr(x_{1}=j\mid x_{0}=i).\,$

Les probabilitats de transició solen venir donades mitjançant números reals. Si aquestes probabilitats no es coneixen de manera precisa, cal estimar-les d'alguna manera amb la incertesa que implica qualsevol procediment d'estimació. Així, per exemple, es poden estimar mitjançant intervals modals o per números borrosos.

• Un fet important és que les probabilitats de transició en n passos satisfan l'equació de Chapman-Kolmogórov, és a dir, per a qualsevol k tal que 0 < k < n es compleix que

$p_{ij}^{(n)}=\sum _{r\in E}p_{ir}^{(k)}p_{rj}^{(nk)}$

on E denota l'espai d'estats.

• Quan la cadena de Màrkov és homogènia, moltes de les seves propietats útils es poden obtenir a través de la seva matriu de transició, definida entrada a entrada com $A_{i,j}=p_{ij}$

és a dir, l'entrada i, j correspon a la probabilitat d'anar de l'estat iaj en un pas.

De la mateixa manera es pot obtenir la matriu de transició en n passos com:

$A_{i,j}^{(n)}=P_{ij}^{(n)}$, on $P_{ij}^{(n)}=P(x_{n}=j|x_{0}=i)$.

Vector de probabilitat invariant

• Es defineix la distribució inicial $\pi (x)=P(x_{0}=x)\,$.

• Direm que un vector de probabilitat (finit o infinit numerable) és invariant per a una cadena de Màrkov si

$\nu P=\nu \,$

on P denota la matriu de transició de la cadena de Markov. Al vector de probabilitat invariant s'anomena distribució estacionària o distribució d'equilibri .

Classes de comunicació

• Per dos estats i , j en l'espai d'estats E , direm que d' i s'accedeix a j (i es denotarà $i\rightarrow j$) si

$p_{ij}^{(n)}>0\,$ per algun n ,

si $i\rightarrow j$ i $j\rightarrow i$ llavors direm que i comunica amb j i es denotarà i ↔ j.

La propietat "↔" és una relació d'equivalència. Aquesta relació indueix una partició de l'espai d'estats. A aquestes classes d'equivalència les anomenarem classes de comunicació .

Donat un estat x , denotarem a la seva classe de comunicació com C (x) .

• Direm que un subconjunt C de l'espai d'estats (al qual denotarem E ) és tancat si cap estat de E -C pot ser accedit des d'un estat de C, és a dir, si $p_{x,y}^{(m)}=0$ per a tot x ∈ C, per a tot i ∈ E -C i per a tot natural m> 0.

Temps d'entrada

Si $C\subset E$, definim el primer temps d'entrada a C com la variable aleatòria

$T_{C}={\begin{cases}\min\{n>0|x_{n}\in C\}&{\text{si }}\{n>0|x_{n}\in C\}\neq \emptyset \\{\mathcal {1}}\,&{\text{si }}\{n>0|x_{n}\in C\}=\emptyset \end{cases}}$

és a dir, $T_{C}$ denota la primera vegada que la cadena entra al conjunt d'estats C.

Recurrència

En una cadena de Màrkov amb espai d'estats E , si x ∈ E es defineix $L_{x}=\mathbb {P} \,(x_{n}=x{\text{ per algun }}n\in \mathbb {N} \,|x_{0}=x)$ i direm que:

• X és estat recurrent si $L_{x}=1$.
• X és transitori si $L_{x}<1$
• X és absorbent si $p_{x,x}=1$
• Una classe de comunicació és classe recurrent si tots els seus estats són recurrents.

Sigui $\mu _{x}=\mathbb {E} \,(T_{x}|x_{0}=x)$, si x ∈ E direm que:

• X és zero-recurrent si $\mu _{x}={\mathcal {1}}\,$
• X és positiu-recurrent si $\mu _{x}<{\mathcal {1}}\,$

El reial $\mu _{x}$ s'interpreta com el temps mitjà de recurrència.

Periodicitat

• L' període d'un estat x ∈ E es defineix com:

$d(x)=mcd\{n:P_{x,x}^{(n)}>0\}$

on $mcd$ denota el màxim comú divisor.

• Si d (x) = 1 direm que x és un estat aperiòdic .

• Una cadena de Màrkov es diu aperiòdica si tots els seus estats són aperiòdics.

Tipus de cadenes de Màrkov

Cadenes irreductibles

Una cadena de Màrkov es diu irreductible si es compleix qualsevol de les següents condicions (equivalents entre si):

1. Des de qualsevol estat de E es pot accedir a qualsevol altre.

2. Tots els estats es comuniquen entre si.

3. C (x) = E per algun x ∈ E .

4. C (x) = E per a tot x ∈ E .

5. L'únic conjunt tancat és el total.

La cadena d'Ehrenfest o el camí aleatori sense barreres absorbents són exemples de cadenes de Màrkov irreductibles.

Cadenes positiu-recurrents

Una cadena de Màrkov es diu positiu-recurrent si tots els seus estats són positiu-recurrents. Si la cadena és més irreductible és possible demostrar que existeix un únic vector de probabilitat invariant i està donat per:

$\pi _{x}=1/\mu _{x}\,$

Cadenes regulars

Una cadena de Màrkov es diu regular (també primitiva o ergòdica ) si hi ha alguna potència positiva de la matriu de transició les entrades siguin totes estrictament majors que zero.

Quan l'espai d'estats E és finit, si P denota la matriu de transició de la cadena s'ha de:

$\lim _{n\to {1}\,}P^{n}=W$

on W és una matriu amb tots els seus línies iguals a un mateix vector de probabilitat w , que resulta ser el vector de probabilitat invariant de la cadena. En el cas de cadenes regulars, aquest vector invariant és únic.

Cadenes absorbents

Una cadena de Màrkov amb espai d'estats finit es diu absorbent si es compleixen les dues condicions següents:

1. La cadena té almenys un estat absorbent.

2. De qualsevol estat no absorbent s'accedeix a algun estat absorbent.

Si denotem com A al conjunt de tots els estats absorbents i al seu complement com D , tenim els següents resultats:

• La seva matriu de transició sempre es pot portar a una de la forma

$P={\begin{pmatrix}Q&R\\0&I\end{pmatrix}}$

on la submatriu Q correspon als estats del conjunt D, I és la matriu identitat, 0 és la matriu nul i R alguna submatriu.

• $P_{x}(T_{A}<{\mathcal {1}}\,)=1$, és a dir, no importa on es trobi la cadena, eventualment acabarà en un estat absorbent.

Cadenes de Màrkov en temps continu

Si en lloc de considerar una seqüència discreta X ₁ , X ₂ ,..., X _i , .. amb i indexat en el conjunt $\mathbb {N} \;\!$ de nombres naturals, es consideren les variables aleatòries X _t amb t que varia en un interval continu del conjunt $\mathbb {R} \;\!$ de nombres reals, tindrem una cadena en temps continu. Per a aquest tipus de cadenes en temps continu la propietat de Markov s'expressa de la següent manera:

$P(X(t_{n+1})=x_{n+1}|X(t_{n})=x_{n},\ldots ,X(t_{1})=x_{1})=P(X(t_{n+1})=x_{n+1}|X(t_{n})=x_{n})$ tal que $t_{n+1}>t_{n}>t_{n-1}>\dots >t_{1}$

Aplicacions

Física

Les cadenes de Màrkov són usades en molts problemes de la termodinàmica i la física estadística. Exemples importants es poden trobar a la Cadena de Ehrenfest o el model de difusió de Laplace.

Meteorologia

Si considerem el clima d'una regió a través de diferents dies, és clar que l'estat actual només depèn de l'últim estat i no de tota la història en si, de manera que es poden utilitzar cadenes de Markov per formular models climatològics bàsics.

Models epidemiològics

Una important aplicació de les cadenes de Màrkov es troba en el procés de Galton-Watson. Aquest és un procés de ramificació que es pot fer servir, entre altres coses, per modelar el desenvolupament d'una epidèmia (vegeu modelatge matemàtic d'epidèmies).

Internet

El pagerank d'una pàgina web (usat per google en els seus motors de cerca) es defineix a través d'una cadena de Markov, on la posició que tindrà una pàgina en el cercador serà determinada pel seu pes en la distribució estacionària de la cadena.

Jocs d'atzar

Són molts els jocs d'atzar que es poden modelar a través d'una cadena de Màrkov. El model de la ruïna del jugador, que estableix la probabilitat que una persona que aposta en un joc d'atzar eventualment acabi sense diners, és una de les aplicacions de les cadenes de Màrkov en aquest rubro.

Economia i Finances

Les cadenes de Màrkov es poden utilitzar en models simples de valoració d'opcions per determinar quan hi ha oportunitat d'arbitratge, així com en el model de col·lapses d'una borsa de valors o per determinar la volatilitat de preus.

Música

Diversos algorismes de composició musical fan servir cadenes de Màrkov, per exemple el programari Csound o Max.

Bibliografia

• A.A.A Markov. "Rasprostranenie zákona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fizik-matematicheskogo obschestva primer Kazanskom universitet , 2-ja seriya, tom 15, pp. 135-156, 1906.
• A.A.A Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B de: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains . John Wiley and Sons, 1971.
• Classical Text in Translation: A. A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains, trans. David Link. Science in Context 19.4 (2006): 591-600. Online: http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500
• Leo Breim. Probability . Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (Vegeu Capítol 7.)
• J.L. Doob. Stochastic Processes . New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.
• S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability . London: Springer-Verlag, 1993. ISBN 0-387-19832-6. línia: https://netfiles.uiuc.edu/Meyn/www/spm_files/book.html Arxivat 2010-06-19 a Wayback Machine.. Second edition to appear, Cambridge University Press, 2009.
• S. P. Meyn. Control Techniques for Complex Networks . Cambridge University Press, 2007. ISBN 978-0-521-88441-9. Appendix contains abridged Meyn & Tweedie. línia: https://netfiles.uiuc.edu/Meyn/www/spm_files/CTCN/CTCN.html Arxivat 2010-06-19 a Wayback Machine.
• Booth, Taylor L. Sequential Machines and Automata Theory. Nova York: John Wiley and Sons, Inc, 1967. Library of Congress Card Catalog Number 67-25924. Extensive, wide-ranging book meant for specialists, written for both theoretical computer scientists as well as electrical engineers. With detailed explanations of state minimization techniques, FSMs, Turing machines, Markov processes, and undecidability. Excellent treatment of Markov processes pp. 449ff. Discusses Z-transforms, D transforms in their context.
• Kemeny, John G.; Hazleton Mirkil, J. Laurie Snell, Gerald L. Thomas. Finite Mathematical Structures. Englewood Cliffs, NJ: Prentice-Hall, Inc, 1959. Library of Congress Card Catalog Number 59-12841. Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
• E. Nummelin. "General irreductible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X

Enllaços externs

• Cadenes de Markov en temps discret Arxivat 2010-01-31 a Wayback Machine. (castellà) [Consulta: 14 març 2020]
• Techniques to Understand Computer Simulations: Markov Chain Analysis (anglès) [Consulta: 14 març 2020]
• Markov Chains Explained Visually (anglès) [Consulta: 14 març 2020]