Cadena de Márkov

En la teoria de la provabilitat, 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 provabilitat 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 $x_1,x_2,\mathrm{...},x_k,x_{k+1}$ de variables conectades de tal modo que $x_{k+1}$ per a qualsevol $k$ és independent de $x_1,x_2,\mathrm{...},x_k,x_{k-1}$, en el cas de que $x_k$ siga coneguda”. Markov va cridar a la cadena "homogénea" si la distribució condicional de $x_{k+1}$ dau $x_k$ 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".

Archiu:Markovkate 01.svg

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.

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 $\{X_n:n=0,1,2\dots \}$ en espai d'estats discret $S$ que per a qualsevol sancer $n\ge 0$ i per a qualssevol $x_0,x_1,\dots ,x_{n+1}\in S$ satisfà

$P[X_{n+1}=x_{n+1}|X_0=x_0,X_1=x_1,\dots ,X_n=x_n]=P[X_{n+1}=x_{n+1}|X_n=x_n]$

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 provabilitat 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[X_{n+1}=j|X_n=i]=P[X_1=j|X_0=i]$

para tot $n\ge 0$ i per a qualsevol $i,j\in 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ó

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

$p_{ij}(n,n+1)=\mathrm{P}[X_{n+1}=j|X_n=i]$.

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

$p_{ij}=\mathrm{P}[X_{n+1}=j|X_n=i]$,

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

Les provabilitats de transició solen vindre donades per mig d'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ó. Aixina, per eixemple, es poden estimar per mig d'intervals modals o per números borrosos.

Matriu de Provabilitats de Transició

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

$P=\left[\begin{array}{cccc}{p}_{00}& p_{01}& p_{02}& \cdots \\ p_{10}& p_{11}& p_{12}& \cdots \\ p_{20}& p_{21}& p_{22}& \cdots \\ ⋮& ⋮& ⋮\end{array}\right]$

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

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

• $p_{ij}\ge 0$
• $i\sum _{j\in S}{p}_{ij}=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)=\left[\begin{array}{cccc}{p}_{00}(n)& p_{01}(n)& p_{02}(n)& \cdots \\ p_{10}(n)& p_{11}(n)& p_{12}(n)& \cdots \\ p_{20}(n)& p_{21}(n)& p_{22}(n)& \cdots \\ ⋮& ⋮& ⋮\end{array}\right]$

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

Equació de Chapman-Kolmogorov

Per a qualssevol $r,n\in \mathbb{Z}$ tals que $0\le r\le n$ i per a qualssevol estats $i,j\in S$ es complix

$p_{ij}(n)=\sum _{k\in S}{p}_{ik}(r)p_{kj}(n-r)$

Com a conseqüència d'este resultat, la provabilitat de transició en $n$ passos, $p_{ij}(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

$p_{ij}(n)=(P^n{)}_{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

$\begin{array}{cc}P(n)& =\left[\begin{array}{ccc}{p}_{00}(n)& p_{01}(n)& \cdots \\ p_{10}(n)& p_{11}(n)& \cdots \\ ⋮& ⋮\end{array}\right]\\ & ={\left[\begin{array}{ccc}{p}_{00}& p_{01}& \cdots \\ p_{10}& p_{11}& \cdots \\ ⋮& ⋮\end{array}\right]}^n\\ & =P^n\end{array}$

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\to j$ si $\mathrm{\exists }n\in {\mathbb{Z}}^{+}$ tal que

$p_{ij}(n)>0$

si $i\to j$ i $j\to 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\in 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\in S$ es definix com:

$d(i)=\mathrm{m}\mathrm{c}\mathrm{d}\{n\ge 1:p_{ii}(n)>0\}$

a on $\mathrm{m}\mathrm{c}\mathrm{d}$ denota el màxim comú divisor.

• Si $d(i)=1$ direm que $i$ és un estat aperiódico.
• Si $d(i)=k\ge 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\mathrm{\forall }i\in S$.

Temps de Primera Visita

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

${\tau }_C=\{\begin{array}{cc}\min \{n>0|X_n\in C\}& \text{si }\{n>0|X_n\in C\}\ne \mathrm{\varnothing }\\ 1& \text{si }\{n>0|X_n\in C\}=\mathrm{\varnothing }\end{array}$

açò és, ${\tau }_C$ denota la primera volta que la cadena entra al conjunt d'estats $C$.

Provabilitat de Primera Visita

Es definix

$f_{ij}(n)=\mathrm{P}[X_n=j,X_{n-1}\ne j,\dots ,X_1\ne j|X_0=i]$

com la provabilitat de que una cadena que inicia en l'estat $i$ aplegue a l'estat $j$ per primera volta en $n$ passos, a on $f_{ij}(0)=0$.

En particular, quan $i=j$, $f_{ii}(n)$ denota la provabilitat de retornar per primera volta a l'estat $i$ en $n$ passos.

I es definixen

$f_{ij}=\sum _{n=1}^{\mathrm{\infty }}{f}_{ij}(n)$

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

$f_{ii}=\sum _{n=1}^{\mathrm{\infty }}{f}_{ii}(n)$

com la provabilitat de partir de l'estat $i$ i retornar a ell mateixa en un temps finito.

Recurrencia

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

• $i$ és un estat recurrent si $f_{ii}=1$.
• $i$ és transitori si $f_{ii}<1$.

o utilisant les provabilitats de transició en $n$ passos:

• $i$ és recurrent si $\sum _{n=1}^{\mathrm{\infty }}{p}_{ii}(n)=\mathrm{\infty }$
• $i$ és transitori si $\sum _{n=1}^{\mathrm{\infty }}{p}_{ii}(n)<\mathrm{\infty }$

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

${\tau }_{ij}=\min \{n\ge 1:X_n=j|X_0=i\}$

i es denota per ${\mu }_{ij}$

${\mu }_{ij}=\mathrm{E}[{\tau }_{ij}]=\sum _{n=1}^{\mathrm{\infty }}n{f}_{ij}(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 ${\mu }_i$ en lloc de ${\mu }_{ij}$.

Es diu que un estat recurrent $i$ és

• recurrent nul si ${\mu }_i=\mathrm{\infty }$.

recurrent positiu si ${\mu }_i<\mathrm{\infty }$.

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 Estacionarias

Es diu que el vector $\pi =({\pi }_0,{\pi }_1,\dots )$ és una distribució de provabilitat si

• ${\pi }_i\ge 0$
• $\sum _i{\pi }_i=1$

Es diu que una distribució de provabilitat $\pi =({\pi }_0,{\pi }_1,\dots )$ és estacionaria per a una Cadena de Markov en matriu de provabilitats de transició $P=(p_{ij})$ si

${\pi }_j=\sum _{i\in S}{\pi }_i{p}_{ij}$

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

Per a trobar una possible distribució estacionaria d'una cadena en matriu $P$, un método consistix en resoldre el sistema d'equacions

$\{\begin{array}{c}\pi =\pi P\\ \text{Sujeto a:}\\ & \sum _{j\in S}{\pi }_j=1\\ & {\pi }_j\ge 0\end{array}$

La distribució estacionaria 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ó estacionaria i esta està donada per

${\pi }_j=\frac{1}{{\mu }_j}$

a on ${\mu }_j$ és el temps mig de recurrencia de l'estat $j$.

Convergència a la distribució estacionaria

Si una cadena de Markov és

• Irreducible
• Aperiódica
• En distribució estacionaria $\pi$

llavors per a qualssevol $i,j\in S$

$\underset{n\to \mathrm{\infty }}{\lim }{p}_{ij}(n)={\pi }_j$

Convergència per a Cadenes de Markov

Si una cadena de Markov és

• Irreducible
• Recurrent positiva
• Aperiódica

llavors les provabilitats llímit

${\pi }_j=\underset{n\to \mathrm{\infty }}{\lim }{p}_{ij}(n)$

existixen, estan donades per

${\pi }_j=\frac{1}{{\mu }_j}$

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

$\{\begin{array}{c}\pi =\pi P\\ \text{Sujeto a:}\\ & \sum _{j\in S}{\pi }_j=1\\ & {\pi }_j\ge 0\end{array}$

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.; Thompson, {{{nom4}}} (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