Cadena de Márkov

Se dice que una Cadena de Markov es homogénea si la probabilidad de ir del estado ${\displaystyle i}$ al estado ${\displaystyle j}$ en un paso no depende del tiempo en el que se encuentra la cadena, esto es:

${\displaystyle P[X_{n+1}=j|X_{n}=i]=P[X_{1}=j|X_{0}=i]}$

para todo ${\displaystyle n\geq 0}$ y para cualquier ${\displaystyle i,j\in S}$.

Si para alguna pareja de estados y para algún tiempo ${\displaystyle n}$ la propiedad antes mencionada no se cumple entonces diremos que la Cadena de Markov es no homogénea.

Sean ${\displaystyle i}$ y ${\displaystyle j}$ dos estados de una Cadena de Markov. La probabilidad de ir del estado ${\displaystyle i}$ en el tiempo ${\displaystyle n}$ al estado ${\displaystyle j}$ en el tiempo ${\displaystyle n+1}$ se denota por

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

Cuando la cadena es homogénea, esta probabilidad se denota por

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

que representa la probabilidad de pasar del estado ${\displaystyle i}$ al estado ${\displaystyle j}$ en una unidad de tiempo.

Teniendo las probabilidades de transición en un paso ,${\displaystyle p_{ij}}$, si variamos los índices ${\displaystyle i,j}$ sobre el espacio de estados ${\displaystyle S=\{0,1,2,\dots \}}$ obtenemos la matriz ${\displaystyle P}$ llamada matriz de probabilidades de transición en un paso, es decir:

${\displaystyle P={\begin{bmatrix}p_{00}&p_{01}&p_{02}&\cdots \\p_{10}&p_{11}&p_{12}&\cdots \\p_{20}&p_{21}&p_{22}&\cdots \\\vdots &\vdots &\vdots \end{bmatrix}}}$

donde la entrada ${\displaystyle (i,j)}$ representa la probabilidad de pasar del estado ${\displaystyle i}$ al estado ${\displaystyle j}$ en un paso.

La matriz ${\displaystyle P}$ es una matriz estocástica pues satisface

• ${\displaystyle p_{ij}\geq 0}$
• ${\displaystyle \sum _{j\in S}p_{ij}=1}$

Similarmente se define la matriz de probabilidades de transición en ${\displaystyle n}$ pasos, esta se denota por ${\displaystyle P(n)}$ y está dada por

${\displaystyle P(n)={\begin{bmatrix}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 \\\vdots &\vdots &\vdots \end{bmatrix}}}$

donde la entrada ${\displaystyle (i,j)}$ representa la probabilidad de pasar del estado ${\displaystyle i}$ al estado ${\displaystyle j}$ en ${\displaystyle n}$ pasos.

Para cualesquiera ${\displaystyle r,n\in \mathbb {Z} }$ tales que ${\displaystyle 0\leq r\leq n}$ y para cualesquiera estados ${\displaystyle i,j\in S}$ se cumple

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

Como consecuencia de este resultado, la probabilidad de transición en ${\displaystyle n}$ pasos, ${\displaystyle p_{ij}(n)}$, está dada por la entrada ${\displaystyle (i,j)}$ de la ${\displaystyle n}$-ésima potencia de la matriz de probabilidades de transición en un paso, es decir

${\displaystyle p_{ij}(n)=(P^{n})_{ij}}$

Con lo anterior, el problema de calcular las probabilidades de transición en ${\displaystyle n}$ pasos se convierte en halla la ${\displaystyle n}$-ésima potencia de la matriz de probabilidades de transición en un paso, esto es

${\displaystyle {\begin{aligned}P(n)&={\begin{bmatrix}p_{00}(n)&p_{01}(n)&\cdots \\p_{10}(n)&p_{11}(n)&\cdots \\\vdots &\vdots \end{bmatrix}}\\&={\begin{bmatrix}p_{00}&p_{01}&\cdots \\p_{10}&p_{11}&\cdots \\\vdots &\vdots \end{bmatrix}}^{n}\\&=P^{n}\end{aligned}}}$

Para dos estados ${\displaystyle i}$ y ${\displaystyle j}$ en el espacio de estados ${\displaystyle S}$, diremos que el estado ${\displaystyle j}$ es accesible desde el estado ${\displaystyle i}$ y escribiremos ${\displaystyle i\rightarrow j}$ si ${\displaystyle \exists \,n\in \mathbb {Z} ^{+}}$ tal que

${\displaystyle p_{ij}(n)>0}$

si ${\displaystyle i\rightarrow j}$ y ${\displaystyle j\rightarrow i}$ entonces diremos que el estado ${\displaystyle i}$ se comunica con el estado ${\displaystyle j}$ y escribiremos ${\displaystyle i\longleftrightarrow j}$.

La propiedad "${\displaystyle \longleftrightarrow }$" es una relación de equivalencia. Esta relación induce una partición del espacio de estados. A estas clases de equivalencia las llamaremos clases de comunicación.

Dado un estado ${\displaystyle i\in S}$, denotaremos a su clase de comunicación como ${\displaystyle C(i)}$, por lo que ${\displaystyle i\longleftrightarrow j}$ si y sólo si ${\displaystyle C(i)=C(j)}$.

Si ${\displaystyle C(i)=S}$ entonces se dice que la cadena es irreducible.

El periodo de un estado ${\displaystyle i\in S}$ se define como:

${\displaystyle d(i)={\rm {mcd}}\{n\geq 1:p_{ii}(n)>0\}}$

donde ${\displaystyle {\rm {mcd}}}$ denota el máximo común divisor.

• Si ${\displaystyle d(i)=1}$ diremos que ${\displaystyle i}$ es un estado aperiódico.
• Si ${\displaystyle d(i)=k\geq 2}$ diremos que ${\displaystyle i}$ tiene periodo ${\displaystyle k}$.

Una cadena de Márkov se dice aperiódica si todos sus estados son aperiódicos, es decir, sí ${\displaystyle d(i)=1\quad \forall \;i\in S}$.

Si ${\displaystyle C\subset S}$, definimos el tiempo de primera visita a ${\displaystyle C}$ como la variable aleatoria

${\displaystyle \tau _{C}={\begin{cases}\min\{n>0|X_{n}\in C\}&{\mbox{si }}\{n>0|X_{n}\in C\}\neq \emptyset \\1&{\mbox{si }}\{n>0|X_{n}\in C\}=\emptyset \end{cases}}}$

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

Se define

${\displaystyle f_{ij}(n)=\operatorname {P} [X_{n}=j,X_{n-1}\neq j,\dots ,X_{1}\neq j|X_{0}=i]}$

como la probabilidad de que una cadena que inicia en el estado ${\displaystyle i}$ llegue al estado ${\displaystyle j}$ por primera vez en ${\displaystyle n}$ pasos, donde ${\displaystyle f_{ij}(0)=0}$.

En particular, cuando ${\displaystyle i=j}$, ${\displaystyle f_{ii}(n)}$ denota la probabilidad de regresar por primera vez al estado ${\displaystyle i}$ en ${\displaystyle n}$ pasos.

Y se definen

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

como la probabilidad de una eventual visita a partir del estado ${\displaystyle i}$ al estado ${\displaystyle j}$ y

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

como la probabilidad de partir del estado ${\displaystyle i}$ y regresar a él mismo en un tiempo finito.

En una cadena de Markov con espacio de estados ${\displaystyle S}$, diremos que:

• ${\displaystyle i}$ es un estado recurrente si ${\displaystyle f_{ii}=1}$.
• ${\displaystyle i}$ es transitorio si ${\displaystyle f_{ii}<1}$.

o utilizando las probabilidades de transición en ${\displaystyle n}$ pasos:

• ${\displaystyle i}$ es recurrente si ${\displaystyle \sum _{n=1}^{\infty }p_{ii}(n)=\infty }$
• ${\displaystyle i}$ es transitorio si ${\displaystyle \sum _{n=1}^{\infty }p_{ii}(n)<\infty }$

La recurrencia es una propiedad de clase pues

• Si ${\displaystyle i}$ es recurrente e ${\displaystyle i\longleftrightarrow j}$ entonces ${\displaystyle j}$ es recurrente.
• Si ${\displaystyle i}$ es transitorio e ${\displaystyle i\longleftrightarrow j}$ entonces ${\displaystyle j}$ es transitorio.

Se define como el tiempo medio de recurrencia de un estado recurrente ${\displaystyle j}$ a partir del estado ${\displaystyle i}$ como la esperanza de

${\displaystyle \tau _{ij}=\min\{n\geq 1:X_{n}=j|X_{0}=i\}}$

y se denota por ${\displaystyle \mu _{ij}}$

${\displaystyle \mu _{ij}=\operatorname {E} [\tau _{ij}]=\sum _{n=1}^{\infty }nf_{ij}(n)}$,

Esta esperanza representa el número de pasos promedio que a la cadena le toma regresar al estado recurrente ${\displaystyle j}$.

En particular, cuando ${\displaystyle i=j}$ escribimos ${\displaystyle \mu _{i}}$ en lugar de ${\displaystyle \mu _{ij}}$.

Se dice que un estado recurrente ${\displaystyle i}$ es

• recurrente nulo si ${\displaystyle \mu _{i}=\infty }$.
• recurrente positivo si ${\displaystyle \mu _{i}<\infty }$.

La recurrencia positiva es una propiedad de clase pues

• Si ${\displaystyle i}$ es recurrente positivo e ${\displaystyle i\longleftrightarrow j}$ entonces ${\displaystyle j}$ es recurrente positivo.
• Si ${\displaystyle i}$ es recurrente nulo e ${\displaystyle i\longleftrightarrow j}$ entonces ${\displaystyle j}$ es recurrente nulo.

Se dice que el vector ${\displaystyle \pi =(\pi _{0},\pi _{1},\dots )}$ es una distribución de probabilidad si

• ${\displaystyle \pi _{i}\geq 0}$
• ${\displaystyle \sum _{i}\pi _{i}=1}$

Se dice que una distribución de probabilidad ${\displaystyle \pi =(\pi _{0},\pi _{1},\dots )}$ es estacionaria para una Cadena de Markov con matriz de probabilidades de transición ${\displaystyle P=(p_{ij})}$ si

${\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}}$

En forma matricial lo anterior es equivalente a ${\displaystyle \pi =\pi P}$ y significa que si una variable aleatoria inicial ${\displaystyle X_{0}}$ tiene una distribución ${\displaystyle \pi }$ entonces la distribución de ${\displaystyle X_{n}}$ también es ${\displaystyle \pi }$, es decir, esta distribución no cambia con el paso del tiempo.

Para encontrar una posible distribución estacionaria de una cadena con matriz ${\displaystyle P}$, un método consiste en resolver el sistema de ecuaciones

${\displaystyle \left\{{\begin{array}{cc}\pi =\pi P\\{\text{Sujeto a:}}\\&\sum _{j\in S}\pi _{j}=1\\&\pi _{j}\geq 0\end{array}}\right.}$

La distribución estacionaria puede no ser única o incluso no existir.

Si una Cadena de Markov es irreducible y recurrente positiva entonces tiene una única distribución estacionaria y esta está dada por

${\displaystyle \pi _{j}={\frac {1}{\mu _{j}}}}$

donde ${\displaystyle \mu _{j}}$ es el tiempo medio de recurrencia del estado ${\displaystyle j}$.

Si una cadena de Markov es

• Irreducible
• Aperiódica
• Con distribución estacionaria ${\displaystyle \pi }$

entonces para cualesquiera ${\displaystyle i,j\in S}$

${\displaystyle \lim _{n\to \infty }p_{ij}(n)=\pi _{j}}$

Si una cadena de Markov es

• Irreducible
• Recurrente positiva
• Aperiódica

entonces las probabilidades límite

${\displaystyle \pi _{j}=\lim _{n\to \infty }p_{ij}(n)}$

existen, están dadas por

${\displaystyle \pi _{j}={\frac {1}{\mu _{j}}}}$

y constituyen la única solución al sistema de ecuaciones

${\displaystyle \left\{{\begin{array}{cc}\pi =\pi P\\{\text{Sujeto a:}}\\&\sum _{j\in S}\pi _{j}=1\\&\pi _{j}\geq 0\end{array}}\right.}$

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

1. Desde cualquier estado de ${\displaystyle S}$ se puede acceder a cualquier otro.
2. Todos los estados se comunican entre sí.
3. ${\displaystyle C(i)=S}$ para algún ${\displaystyle i\in S}$.
4. ${\displaystyle C(i)=S}$ para todo ${\displaystyle i\in S}$.
5. El único conjunto cerrado es el total.

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

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

${\displaystyle \pi _{j}={\frac {1}{\mu _{j}}}}$

Una cadena de Márkov 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 ${\displaystyle S}$ es finito, si ${\displaystyle P}$ denota la matriz de transición de la cadena se tiene que:

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

donde ${\displaystyle 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, este vector invariante es único.

Una cadena de Márkov 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

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

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

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

Si en lugar de considerar una secuencia discreta ${\displaystyle X_{1},X_{2},\dots ,X_{i},\dots }$ con ${\displaystyle i}$ indexado en el conjunto ${\displaystyle \mathbb {N} \;\!}$ de números naturales, se consideran las variables aleatorias ${\displaystyle X_{t}}$ con ${\displaystyle t}$ que varía en un intervalo continuo del conjunto ${\displaystyle \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:

${\displaystyle 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 ${\displaystyle t_{n+1}>t_{n}>t_{n-1}>\dots >t_{1}}$

Para una cadena de Márkov continua con un número finito de estados puede definirse una matriz estocástica dada por:

${\displaystyle \mathbf {P} (t_{1},t_{2})=[p_{ij}(t_{1},t_{2})]_{i,j=1,\dots ,N},\qquad p_{ij}(t_{1},t_{2})=P[X(t_{2})=j|X(t_{1})=i],\ 0\geq t_{1}<t_{2}}$

La cadena se denomina homogénea si ${\displaystyle \mathbf {P} (t_{1},t_{2})=\mathbf {P} (t_{2}-t_{1})}$. Para una cadena de Márkov en tiempo continuo homogénea y con un número finito de estados puede definirse el llamado generador infinitesimal como:[2]

${\displaystyle \mathbf {Q} =\lim _{h\to 0^{+}}{\frac {\mathbf {P} (h)-\mathbf {I} }{h}}}$

Y puede demostrarse que la matriz estocástica viene dada por:

${\displaystyle \mathbf {P} (t)=e^{\mathbf {Q} t}=\sum _{n=0}^{\infty }{\frac {\mathbf {Q} ^{n}t^{n}}{n!}}}$

Si consideramos el tiempo atmosférico de una región a través de distintos días, es posible asumir 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. Por ejemplo, se han desarrollado modelos de recurrencia de las lluvias basados en cadenas de Markov.[3]

Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Este 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).

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.

Las cadenas de Márkov son utilizadas para proveer una solución analítica a ciertos problemas de simulación, por ejemplo en teoría de colas el Modelo M/M/1[4] es de hecho un modelo de cadenas de Markov.

Son muchos los juegos de azar que se pueden modelar a través de una cadena de Márkov. El modelo de la ruina del jugador (Gambler's ruin), 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 Márkov en este rubro.

Las cadenas de Márkov 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 los 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.

Se emplean cadenas de Márkov en teoría de genética de poblaciones, para describir el cambio de frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética. Ha sido empleada en la construcción del modelo de difusión de Motō Kimura.

Diversos algoritmos de composición musical usan cadenas de Márkov, por ejemplo el software Csound o Max. Uno de los compositores que usó esta técnica en sus composiciones fue Iannis Xenakis con su obra Analoguique A et B (1958–59).

Se emplean cadenas de Márkov en inventarios, mantenimiento y flujo de proceso.

Se utilizan en las máquinas de Boltzmann.