Cadena de Márkov

En la teoría de la probabilidad, se conoce como cadena de Márkov a un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende del evento inmediatamente anterior. En efecto, las cadenas de este tipo tienen memoria. "Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Márkov de las series de eventos independientes, como tirar una moneda al aire o un dado.

Reciben su nombre del matemático ruso Andrei Andreevitch Markov (1856-1922), que las introdujo en 1907.​

Estos modelos muestran una estructura de dependencia simple, pero muy útil en muchas aplicaciones.

Definición formal

En matemáticas, se define como un proceso estocástico discreto que cumple con la propiedad de Márkov, es decir, si se conoce la historia del sistema hasta su instante actual, su estado presente resume toda la información relevante para describir en probabilidad su estado futuro.

Una cadena de Márkov es una secuencia X₁, X₂, X₃,... de variables aleatorias. El rango de estas variables, es llamado espacio estado, el valor de X_n es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de X_n+1 en estados pasados es una función de X_n por sí sola, entonces:

$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}).\,$

Donde x_i es el estado del proceso en el instante i. La identidad mostrada es la propiedad de Márkov.

Notación útil

Cadenas homogéneas y no homogéneas

• Una cadena de Markov se dice homogénea si la probabilidad de ir del estado i al estado j en un paso no depende del tiempo en el que se encuentra la cadena, esto es:

$P(X_{n}=j|X_{n-1}=i)=P(X_{1}=j|X_{0}=i)\,$ para todo n y para cualquier i, j.

Si para alguna pareja de estados y para algún tiempo n la propiedad antes mencionada no se cumple diremos que la cadena de Markov es no homogénea.

Probabilidades de transición y matriz de transición

• La probabilidad de ir del estado i al estado j en n unidades de tiempo es

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

en la probabilidad de transición en un paso se omite el superíndice de modo que queda

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

• Un hecho importante es que las probabilidades de transición en n pasos satisfacen la ecuación de Chapman-Kolmogorov, esto es, para cualquier k tal que 0 < k < n se cumple que

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

donde E denota el espacio de estados.

• Cuando la cadena de Markov es homogénea, muchas de sus propiedades útiles se pueden obtener a través de su matriz de transición, definida entrada a entrada como $A_{i,j}=p_{ij}\,$

esto es, la entrada i, j corresponde a la probabilidad de ir del estado i a j en un paso.

Del mismo modo se puede obtener la matriz de transición en n pasos como:

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

Vector de probabilidad invariante

• Se define la distribución inicial $\pi (x)=P(X_{0}=x)\,$.

• Diremos que un vector de probabilidad (finito o infinito numerable) es invariante para una cadena de Markov si

$\nu P=\nu \,$

donde P denota la matriz de transición de la cadena de Markov. Al vector de probabilidad invariante también se le llama distribución estacionaria o distribución de equilibrio.

Clases de comunicación

• Para dos estados i,j en el espacio de estados E, diremos que de i se accede a j (y se denotará $i\rightarrow j$) si

$p_{ij}^{(n)}>0\,$ para algún n,

si $i\rightarrow j$ y $j\rightarrow i$ entonces diremos que i comunica con j y se denotará i↔j.

La propiedad "↔" es una relación de equivalencia. Esta relación induce una partición en el espacio de estados. A estas clases de equivalencia las llamaremos clases de comunicación.

Dado un estado x, denotaremos a su clase de comunicación como C(x).

• Diremos que un subconjunto C del espacio de estados (al que denotaremos E) es cerrado si ningún estado de E-C puede ser accedido desde un estado de C, es decir, si $p_{x,y}^{(m)}=0$ para todo x∈C, para todo y∈E-C y para todo natural m>0.

Tiempos de entrada

Si $C\subset E$, definimos el primer tiempo de entrada a C como la variable aleatoria

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

esto es, $T_{C}\,$ denota la primera vez que la cadena entra al conjunto de estados C.

Recurrencia

En una cadena de Markov con espacio de estados E, si x∈E se define $L_{x}=\mathbb {P} \,(X_{n}=x\ para\ algun\ n\in \mathbb {N} \,|X_{0}=x)$ y diremos que:

• x es estado recurrente si $L_{x}=1\,$.
• x es transitorio si $L_{x}<1\,$
• x es absorbente si $p_{x,x}=1\,$
• Una clase de comunicación es clase recurrente si todos sus estados son recurrentes.

Sea $\mu _{x}=\mathbb {E} \,(T_{x}|X_{0}=x)$, si x∈Ediremos que:

• x es cero-recurrente si $\mu _{x}={\mathcal {1}}\,$
• x es positivo-recurrente si $\mu _{x}<{\mathcal {1}}\,$

El real $\mu _{x}$ se interpreta como el tiempo promedio de recurrencia.

Periodicidad

• El periodo de un estado x∈E se define como:

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

donde $mcd\,$ denota el máximo común divisor.

• Si d(x)=1 diremos que x es un estado aperiódico.

• Una cadena de Markov se dice aperiódica si todos sus estados son aperiódicos.

Tipos de cadenas de Markov

Cadenas irreducibles

Una cadena de Markov se dice irreducible si se cumple cualquiera de las siguientes condiciones (equivalentes entre sí):

1. Desde cualquier estado de E se puede acceder a cualquier otro.
2. Todos los estados se comunican entre sí.
3. C(x)=E para algún x∈E.
4. C(x)=E para todo x∈E.
5. El único conjunto cerrado es el total.

La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de Markov irreducibles.

Cadenas positivo-recurrentes

Una cadena de Markov se dice positivo-recurrente si todos sus estados son positivo-recurrentes. Si la cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y está dado por:

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

Cadenas regulares

Una cadena de Markov se dice regular (también primitiva o ergódica) si existe alguna potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero.

Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena se tiene que:

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

donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, éste vector invariante es único.

Cadenas absorbentes

Una cadena de Markov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones siguientes:

1. La cadena tiene al menos un estado absorbente.
2. De cualquier estado no absorbente se accede a algún estado absorbente.

Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados:

• Su matriz de transición siempre se puede llevar a una de la forma

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

donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz.

• $P_{x}(T_{A}<{\mathcal {1}}\,)=1$, esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente.

Cadenas de Markov en tiempo continuo

Si en lugar de considerar una secuencia discreta X₁, X₂,..., X_i,.. con i indexado en el conjunto $\mathbb {N} \;\!$ de números naturales john es homo, se consideran las variables aleatorias X_t con t que varía en un intervalo continuo del conjunto $\mathbb {R} \;\!$ de números reales, tendremos una cadena en tiempo continuo. Para este tipo de cadenas en tiempo continuo la propiedad de Márkov se expresa de la siguiente 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}$

Aplicaciones

Física

Las cadenas de Markov son usadas en muchos problemas de la termodinámica y la física estadística. Ejemplos importantes se pueden encontrar en la Cadena de Ehrenfest o el modelo de difusión de Laplace.

Meteorología

Si consideramos el clima de una región a través de distintos días, es claro que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos.

Modelos epidemiológicos

Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Éste es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia (véase modelaje matemático de epidemias).

Internet

El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Markov, donde la posición que tendrá una página en el buscador será determinada por su peso en la distribución estacionaria de la cadena.

Simulación

Las cadenas de Markov son utilizadas para proveer una solución analítica a ciertos problemas de simulación tales como el Modelo M/M/1.

Juegos de azar

Son muchos los juegos de azar que se pueden modelar a través de una cadena de Markov. El modelo de la ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Markov en este rubro.

Economía y Finanzas

Las cadenas de Markov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de precios. En los negocios, las cadenas de Márkov se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades de personal y para analizar el reemplazo de equipo.

Música

Diversos algoritmos de composición musical usan cadenas de Markov, por ejemplo el software Csound o Max

Bibliografía

• A.A. Markov. "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. online: 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. online: https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html
• Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st edición). New York: John Wiley and Sons, Inc. 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. Thompson (1959). Finite Mathematical Structures (1st edición). Englewood Cliffs, N.J.: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841.  Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
• E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X

Enlaces externos

• Cadenas de Markov en tiempo discreto
• Techniques to Understand Computer Simulations: Markov Chain Analysis