Anar al contingut

Cadena de Màrkov

De L'Enciclopèdia, la wikipedia en valencià

En la teoria de la probabilitat, es coneix com a cadena de Màrkov o model de Màrkov a un tipo especial de procés estocàstic discret en el que la probabilitat de que ocórrega un event depén solament de l'event immediatament anterior. Esta característica d'incloure una memòria recent rep el nom de propietat de Markov en contrast en els events independents que no tenen memòria de cap event anterior. En un primer artícul de 1906 A. A. Markov va definir la "cadena simple" com "una seqüència infinita x1,x2,...,xk,xk+1 de variables conectades de tal modo que xk+1 per a qualsevol k és independent de x1,x2,...,xk,xk−1, en el cas de que xk siga coneguda”. Markov va cridar a la cadena "homogénea" si la distribució condicional de xk+1 dau xk fora independent de k. També va considerar cadenes "complexes (complex en anglés)" en les que "cada número està conectat directament no només en un, sino en varis números anteriors".[1]

Cadena simple biestable de Markov

Rep el seu nom del matemàtic rus Andréi Màrkov (1856-1922), que ho va introduir en 1906.[1]

Estos models estadístics conten en un gran número d'aplicacions reals.

Definició

En matemàtiques, una Cadena de Markov és un procés estocàstic a temps discret {Xn:n=0,1,2…} en espai d'estats discret S que per a qualsevol sancer n≥0 i per a qualssevol x0,x1,…,xn+1∈S satisfà

P[Xn+1=xn+1|X0=x0,X1=x1,…,Xn=xn]=P[Xn+1=xn+1|Xn=xn]

a esta propietat se li coneix com propietat de Markov.

Característiques

Cadenes homogénees i no homogénees

Es diu que una Cadena de Markov és homogénea si la probabilitat d'anar de l'estat i a l'estat j en un pas no depén del temps en el que es troba la cadena, açò és:

P[Xn+1=j|Xn=i]=P[X1=j|X0=i]

para tot n≥0 i per a qualsevol i,j∈S.

Si per a alguna parella d'estats i per a algun temps n la propietat abans mencionada no es complix llavors direm que la Cadena de Markov és no homogénea.

Provabilitats de Transició

Siguen i i j dos estats d'una Cadena de Markov. La probabilitat d'anar de l'estat i en el temps n a l'estat j en el temps n+1 es denota per

pij(n,n+1)=P⁡[Xn+1=j|Xn=i].

Quan la cadena és homogénea, esta probabilitat es denota per

pij=P⁡[Xn+1=j|Xn=i],

que representa la probabilitat de passar de l'estat i a l'estat j en una unitat de temps.

Les provabilitats de transició solen vindre donades per mig de número real. Si estes provabilitats no es coneixen de forma precisa, és necessari estimar-les d'alguna manera en l'incertitut que implica qualsevol procediment d'estimació.[2][3] Aixina, per eixemple, es poden estimar per mig d'intervals modals[4] o per números borrosos.[5]

Matriu de Provabilitats de Transició

Tenint les provabilitats de transició en un pas ,pij, si variem els índexs i,j sobre l'espai d'estats S={0,1,2,…} obtenim la matriu P cridada matriu de provabilitats de transició en un pas, és dir:

P=[p00p01p02⋯p10p11p12⋯p20p21p22⋯⋮⋮⋮]

a on l'entrada (i,j) representa la probabilitat de passar de l'estat i a l'estat j en un pas.

La matriu P és una matriu estocàstica puix satisfà

  • pij≥0
  • i∑j∈Spij=1

Similarment es definix la matriu de provabilitats de transició en n passos, esta es denota per P(n) i està donada per

P(n)=[p00(n)p01(n)p02(n)⋯p10(n)p11(n)p12(n)⋯p20(n)p21(n)p22(n)⋯⋮⋮⋮]

a on l'entrada (i,j) representa la probabilitat de passar de l'estat i a l'estat j en n passos.

Equació de Chapman-Kolmogorov

Per a qualssevol r,n∈ℤ tals que 0≤r≤n i per a qualssevol estats i,j∈S es complix

pij(n)=∑k∈Spik(r)pkj(n−r)

Com a conseqüència d'este resultat, la probabilitat de transició en n passos, pij(n), està donada per l'entrada (i,j) de la n-ésima potencia de la matriu de provabilitats de transició en un pas, és dir

pij(n)=(Pn)ij

En lo anterior, el problema de calcular les provabilitats de transició en n passos es convertix en trobar la n-ésima potencia de la matriu de provabilitats de transició en un pas, açò és

P(n)=[p00(n)p01(n)⋯p10(n)p11(n)⋯⋮⋮]=[p00p01⋯p10p11⋯⋮⋮]n=Pn

Classes de comunicació

Per a dos estats i i j en l'espai d'estats S, direm que l'estat j és accessible des de l'estat i i escriurem i→j si ∃n∈ℤ+ tal que

pij(n)>0

si i→j i j→i llavors direm que l'estat i es comunica en l'estat j i escriurem i⟷j.

La propietat "⟷" és una relació d'equivalència. Esta relació induïx una partició de l'espai d'estats. A estes classes d'equivalència les cridarem classes de comunicació.

Donat un estat i∈S, denotarem a la seua classe de comunicació com C(i), per lo que i⟷j si i només si C(i)=C(j).

Si C(i)=S llavors es diu que la cadena és irreducible.

Periodicitat

El periodo d'un estat i∈S es definix com:

d(i)=mcd{n≥1:pii(n)>0}

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

  • Si d(i)=1 direm que i és un estat aperiódico.
  • Si d(i)=k≥2 direm que i té periodo k.

Una cadena de Màrkov es diu aperiódica si tots els seus estats són aperiódicos, és dir, sí d(i)=1∀i∈S.

Temps de Primera Visita

Si C⊂S, definim el temps de primera visita a C com la variable aleatòria

τC={min⁡{n>0|Xn∈C}si {n>0|Xn∈C}≠∅1si {n>0|Xn∈C}=∅

açò és, τC denota la primera volta que la cadena entra al conjunt d'estats C.

Provabilitat de Primera Visita

Es definix

fij(n)=P⁡[Xn=j,Xn−1≠j,…,X1≠j|X0=i]

com la probabilitat de que una cadena que inicia en l'estat i aplegue a l'estat j per primera volta en n passos, a on fij(0)=0.


En particular, quan i=j, fii(n) denota la probabilitat de retornar per primera volta a l'estat i en n passos.

I es definixen

fij=∑n=1∞fij(n)

com la probabilitat d'una eventual visita a partir de l'estat i a l'estat j i

fii=∑n=1∞fii(n)

com la probabilitat de partir de l'estat i i retornar a ell mateixa en un temps finit.

Recurrencia

En una cadena de Markov en espai d'estats S, direm que:

  • i és un estat recurrent si fii=1.
  • i és transitori si fii<1.

o utilisant les provabilitats de transició en n passos:

  • i és recurrent si ∑n=1∞pii(n)=∞
  • i és transitori si ∑n=1∞pii(n)<∞

La recurrencia és una propietat de classe puix

  • Si i és recurrent i i⟷j llavors j és recurrent.
  • Si i és transitori i i⟷j llavors j és transitori.

Temps Mig de Recurrencia

Es definix com el temps mig de recurrencia d'un estat recurrent j a partir de l'estat i com l'esperança de

τij=min⁡{n≥1:Xn=j|X0=i}

i es denota per μij

μij=E⁡[τij]=∑n=1∞nfij(n),

Esta esperança representa el número de passos promig que a la cadena li pren retornar a l'estat recurrent j.

En particular, quan i=j escrivim μi en lloc de μij.

Es diu que un estat recurrent i és

  • recurrent nul si μi=∞.

recurrent positiu si μi<∞.

La recurrencia positiva és una propietat de classe puix

  • Si i és recurrent positiu i i⟷j llavors j és recurrent positiu.
  • Si i és recurrent nul i i⟷j llavors j és recurrent nul.

Distribucions Estacionàries

Es diu que el vector π=(π0,π1,…) és una distribució de probabilitat si

  • πi≥0
  • ∑iπi=1

Es diu que una distribució de probabilitat π=(π0,π1,…) és estacionària per a una Cadena de Markov en matriu de provabilitats de transició P=(pij) si

πj=∑i∈Sπipij

En forma matricial lo anterior és equivalent a π=πP i significa que si una variable aleatòria inicial X0 té una distribució π llavors la distribució de Xn també és π, és dir, esta distribució no canvia en el pas del temps.

Per a trobar una possible distribució estacionària d'una cadena en matriu P, un mètoto consistix en resoldre el sistema d'equacions

{π=πPSujeto a:∑j∈Sπj=1πj≥0

La distribució estacionària pugues no ser única o inclús no existir.

Existència i Unicitat

Si una Cadena de Markov és irreducible i recurrent positiva llavors té una única distribució estacionària i esta està donada per

πj=1μj

a on μj és el temps mig de recurrencia de l'estat j.

Convergència a la distribució estacionària

Si una cadena de Markov és

  • Irreducible
  • Aperiódica
  • En distribució estacionària π

llavors per a qualssevol i,j∈S

limn→∞pij(n)=πj

Convergència per a Cadenes de Markov

Si una cadena de Markov és

  • Irreducible
  • Recurrent positiva
  • Aperiódica

llavors les provabilitats llímit

πj=limn→∞pij(n)

existixen, estan donades per

πj=1μj

i constituïxen l'única solució al sistema d'equacions

{π=πPSujeto a:∑j∈Sπj=1πj≥0

Referències

  1. ↑ 1,0 1,1 Basharin, Gely P.; Langville, Amy N.; Naumov, Valeriy A.(2004).«The Life and Work of A. A. Markov».Linear Algebra and its Applications.386: 3-26.Consultat el 31 de març de 2010.(en anglés)
  2. ↑ Buckley, J.J.; Eslami, E. (2002). Fuzzy Markov Chains: Uncertain Probabilities. Mathware and Soft Computing 9, 33–41.
  3. ↑ Villacorta, P.J.; Verdegay, J.L. FuzzyStatProb: An R Package for the Estimation of Fuzzy Stationary Probabilities from a Sequence of Observations of an Unknown Markov Chain. Journal of Statistical Software 2016, 71, 1–27, https://doi.org/10.18637/jss.v071.i08
  4. ↑ Adillon, R.; Lambert, J.; Marbre, M. (2020). Modal interval probability: Application to Bonus-Malus Systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 28, 837–851, https://doi.org.10.1142/S0218488520500361
  5. ↑ Villacorta Iglésies, P.J.; González-Vila Puchades, L. and Andrés-Sánchez, J.de. (2021). Fuzzy Markovian Bonus-Malus Systems in Senar-Life Insurance. Mathematics, 9(4), 347, https://doi.org/10.3390/math9040347

Bibliografia

  • A.A. Màrkov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156, 1906.
  • A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: 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 Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (See Chapter 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. en llínea: [1] . 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. en llínea: https://web.archive.org/web/20100619011046/https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html
  • Booth, Taylor L. (1967). Sequential Machines and Automata Theory, 1st edició, Nova York: John Wiley and Sons, Inc.. 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.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). Finite Mathematical Structures, 1st edició, Englewood Cliffs, N.J.: Prentice-Hall, Inc.. Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
  • Kijima, Masaaki (1997). Markov Processes for Stochastic Modeling, 1st edició, Cambridge: Chapman & Hall. ISBN 0 412 60660 7.
  • E. Nummelin. "General irreducible Markov chains and senar-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X