Cadena de Márkov

En la teoría de la probabilidad, se conoce como cadena de Márkov o modelo de Márkov a un tipo especial de proceso estocástico discreto en el que la probabilidad de que ocurra un evento depende solamente del evento inmediatamente anterior. Esta característica de falta de memoria recibe el nombre de propiedad de Markov.

Cadena simple biestable de Markov.

Recibe su nombre del matemático ruso Andréi Márkov (1856-1922), que lo introdujo en 1907.[1]

Estos modelos estadísticos cuentan con un gran número de aplicaciones reales.

Definición formal

En matemática 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 X1, X2, X3,... de variables aleatorias. El dominio de estas variables es llamado espacio estado; el valor de Xn es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de Xn+1 en estados pasados es una función de Xn 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 xi 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

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 Márkov es no homogénea.

Probabilidades de transición y matriz de transición

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). \,
p_{ij}^{(n)} = \sum_{r \in E} p_{ir}^{(k)} p_{rj}^{(n-k)}

donde E denota el espacio de estados.

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_{i j}^{(n)}, donde P_{i j}^{(n)}=P(X_n=j|X_0=i).

Vector de probabilidad invariante

\nu P = \nu \, ;importante

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

Clases de comunicación

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).

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

esto es, T_C\, denota la primera vez que la cadena entra al conjunto de estados C.

Recurrencia

En una cadena de Márkov con espacio de estados E, si xE se define L_x = \mathbb{P} \,(X_n = x \ para \ algun \ n \in \mathbb{N} \, | X_0=x) y diremos que:

Sea \mu_x = \mathbb{E} \, (T_x|X_0 = x) , si x∈Ediremos que:

El real \mu_x se interpreta como el tiempo promedio de recurrencia.

Periodicidad

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

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

Tipos de cadenas de Márkov

Cadenas irreducibles

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

Cadenas positivo-recurrentes

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

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.

Cadenas de Márkov en tiempo continuo

Si en lugar de considerar una secuencia discreta X1, X2,..., Xi,.. con i indexado en el conjunto \mathbb{N}\;\! de números naturales, se consideran las variables aleatorias Xt 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

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

\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\ge t_1< t_2

La cadena se denomina homogénea si \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]

\mathbf{Q}= \lim_{h\to 0^+} \frac{\mathbf{P}(h)-\mathbf{I}}{h}

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

\mathbf{P}(t)= e^{\mathbf{Q}t} = \sum_{n=0}^\infty \frac{\mathbf{Q}^n t^n}{n!}


Aplicaciones

Meteorología

Si consideramos el tiempo atmosférico 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 Márkov para formular modelos climatológicos básicos. Por ejemplo se han desarrollado modelos de recurrencia de las lluvias basados en cadenas de Márkov.[3]

Modelos epidemiológicos

Una importante aplicación de las cadenas de Márkov 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 Márkov, 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 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 Márkov.

Juegos de azar

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, 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.

Economía y finanzas

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.

Genética

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.

Música

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

Operaciones

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

Redes Neuronales

Se utilizan en las máquinas de Boltzmann (redes neuronales)

Referencias

  1. Basharin, Gely P.; Langville, Amy N.; Naumov, Valeriy A. (2004). «The Life and Work of A. A. Markov». Linear Algebra and its Applications (en inglés) 386: 3–26. Consultado el 31 de marzo de 2010.
  2. Masaki Kijima, 1997, p. 175
  3. R. Gabriel & J. Neumann (2006): A Markov chain model for daily rainfall occurrence at Tel Aviv
  4. Masaki Kijima, 1997, pp. 287-290.

Bibliografía

Enlaces externos

This article is issued from Wikipedia - version of the Saturday, February 06, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.