Cadena de Màrkov

De Viquipèdia
Dreceres ràpides: navegació, cerca

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,[1] 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.


Definició formal[modifica | modifica el codi]

A matemàtica s, 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 1 , X 2 , X 3 , ... 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[modifica | modifica el codi]

Cadenes homogènies i no homogènies[modifica | modifica el codi]

  • Una cadena de Markov es diu homogènia si la probabilitat d'anar de l'estat i 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ó[modifica | modifica el codi]

  • 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).\,
  • 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[modifica | modifica el codi]

  • 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ó[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

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\}\ne\empty\\
 \mathcal{1}\, &\text{si }\{n> 0|x_n\in C\}=\empty
 \end{cases}

és a dir,  T_C denota la primera vegada que la cadena entra al conjunt d'estats C.

Recurrència[modifica | modifica el codi]

En una cadena de Màrkov amb espai d'estats E , si xE 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[modifica | modifica el codi]

  • 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[modifica | modifica el codi]

Cadenes irreductibles[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

Si en lloc de considerar una seqüència discreta X 1 , X 2 ,..., 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[modifica | modifica el codi]

Física[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

Una important aplicació de les cadenes de Màrkov es troba en el procés 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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

Música[modifica | modifica el codi]

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


Referències[modifica | modifica el codi]

  1. Basharin, Gely P. et al. «The Life and Work of A. A. Markov». Elsevier, 2.004.
  • 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. 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
  • Booth, Taylor L. Sequential Machines and Automata Theory. 1st. New 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. 1st. 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[modifica | modifica el codi]