Cadenas de Markov

Una cadena de Markov es un modelo estocástico que describe una secuencia de posibles hechos en los que la probabilidad de que estos sucedan depende solo del estado alcanzado en el hecho anterior. La transición entre estados cumple con lo que se denomina la Propiedad de Markov:

Cadenas de Markov

 

La probabilidad de transición a un estado concreto (futuro en secuencia) depende únicamente del estado actual y del tiempo transcurrido, y no de la secuencia del estado que la precedió.

 

esta característica hace que sea un modelo desmemoriado, no tiene historia.

 

Dentro del Modelo de Cadenas de Markov existen dos tipos:

  1. Cadenas Discretas o DTMC (Discrete Time Markov Chains). Son un conjunto de posibles valores de variables aleatorias que usando probabilidades operan con pasos de tiempo fijo T= {t0, t1, t2…tn}, T = , T = {0, 1, 2, . . . }, T = .  Los pasos no necesariamente tienen que referirse al tiempo, también podrían aplicarse a distancias físicas o cualquier otra medida discreta. Un ejemplo muy simple sería la acción de barajar cartas, o lo que hago cuando saco a pasear a «J» mi perro, deambular.
  2. Cadenas Continuas o CTMC (Continuous Time Markov Chains). Los cambios de estado pueden ocurrir en cualquier momento, T = [0, 1], T = [0, ∞), T = . Es el modelo más destacado para el estudio de rendimiento y fiabilidad de sistemas en tiempo real.

 

Representación.

Andrei Markov
Andrei Markov

El sistema puede representarse con un autómata probabilístico (diagrama de estado con una matriz de transición). Sería así:

 

  • DTE (Diagrama de transición de estados). El DTE es un gráfico con un nodo para cada estado y con una o varias flechas de dirección entre los nodos. En nuestro caso tenemos una secuencia de nodos con dirección que se etiquetan con las probabilidades de pasar de un estado a otro en el tiempo n, es decir, probabilidad de ir al estado En + 1 tomando el valor del estado En .
  • Matriz de transición (MT). Representa la misma información de tiempo n a tiempo n + 1. Cada estado se incluye en la matriz una vez como fila (i) y otra vez como columna (j) , cada celda (ij)  en la matriz, indica la probabilidad de pasar del estado fila al estado columna, de tal forma que tendríamos una matriz cuadrada N × N.
DTE (Diagrama de transición de estados) Markov
DTE – Markov
MT= ij 1 2 3 4 5 6 7 8 9 10
1 0,3 0,1 0,3 0,3
2 1,0
3 1,0
4 0,8 0,2
5 0,4 0,3 0,3
6 0,1 0,9
7 1.0
8 1,0
9 0,1 0,9
10 1,0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Con frecuencia encontraremos los estados denominados por números enteros positivos {0, 1, 2, . . . } y se dirá que En está en el estado i si En = i.  La probabilidad de que En + 1 esté en el estado j, estando En en el estado i, es la probabilidad de transición en un paso de i a j y se indica como:   Pnn+1ij

 

También lo podemos ver así: La cadena se representa como un triplete (E, A, π), donde:

E. Es un conjunto de orden n, cuyos elementos se corresponden a estados.

A. Es la matriz de transición, de forma cuadrada y dimensión n. Cada columna de A tiene suma 1.(probabilidades).

π = {π1, . . . , πn} es un vector de longitud n que representa la distribución inicial de los estados, cumpliendo que: ∑ πn = 1.

 

Ejemplo.

Cuando Mari Cruz está en día de descanso puede: ir de tiendas, dormir o ver a su familia (3 Estados).  Con datos históricos sabemos que:

Cadenas de Markov - DTE

  1. Si en un día de descanso fue de tiendas, en el siguiente día de descanso existen las siguientes probabilidades:
    1. 55% volverá a ir de tiendas
    2. 30% se quedará durmiendo
    3. 15% verá a su familia
  2. Cuando Durmió:
    1. 68% irá de tiendas
    2. 15% se quedará durmiendo
    3. 17% verá a su familia
  3. Cuando vio a su familia:
    1. 65% de ir de tiendas
    2. 23% se quedará durmiendo
    3. 12% volverá a ver a su familia
Matriz de Transición Estado Siguiente
 
Estado Actual Tiendas Dormir Familia
Tiendas 0,55 0,30 0,15 Distribución de Probabilidad
Dormir 0,68 0,15 0,17
Familia 0,65 0,23 0,12

 

Propiedades más importantes de los estados.

  • Absorbente. Un estado Xn se llama absorbente si es imposible abandonar este estado. Cualquier estado podría serlo sí después de cierto número de pasos, con probabilidad positiva, se vuelva a alcanzar a dicho estado.
  • «Ergódico». Es un término acuñado por L. E. Boltzmann que se relaciona con la probabilidad de que cualquier estado se repita aperiódicamente, es decir, con un intervalo suficiente de tiempo el sistema volverá a estados que son muy similares a anteriores.
  • Distribución estacionaria. Es una distribución de probabilidad que permanece sin cambios a medida que pasa el tiempo. Se suele representar como: Un vector de fila  cuyas entradas son probabilidades que suman 1 y dada la matriz de transición MT , satisface que
  • Irreductible. Una cadena de Markov es irreductible cuando existe la posibilidad de llegar a cualquier estado desde cualquier otro, no importa si uno u otro camino puedan alargarse en el tiempo, lo necesario es que sea posible. De otra forma, una cadena de Markov es Irreductible cuando para todo par de estados x, y es posible pasar de x a y en una cantidad finita de saltos.
  • Periódico. Cada estado en la cadena tiene un período que se define como el mcd (Máximo Común Divisor) de la cantidad de pasos necesarios para regresar a ese estado. En el supuesto de que todos los estados en una cadena tiengan período 1, a esa cadena la denominamos aperiódica.
  • Recurrente. Un estado es recurrente si no es transitorio.
  • Transitorio. Un estado es transitorio si comenzamos en ese estado y existe una probabilidad <> 0 de que nunca volvamos a él.